list - SML - 查找列表中的出现次数以形成有序对

Question

我正在尝试用 SML 编写一个函数，它接受一个整数列表，并输出一个有序的整数对列表。有序对中的第一个 int 是在输入列表中出现的 int，有序对中的第二个 int 是它在输入列表中出现的次数。此外，返回的列表应根据有序对中的第一个 int 升序排列。

例如输入列表 [1, 1, 1, 2, 3, 3, 5] 将输出为 [(1,3), (2, 1), (3 , 2), (5, 1)].

到目前为止，我有一个使用 foldl 的函数

---

自原始帖子以来已更新代码。

fun turnIntoPairs l = foldl (fn (e, a) => if List.exists (fn (x, _) => x = e) a then x + 1 else a @ [(e, 1)]) [] l;

我在更新列表时遇到问题，我发现列表中已经存在有序对 - 我想将一个添加到仍在列表中找到的有序对中的第二个 int 中。

任何帮助将不胜感激!

C:\Program Files (x86)\SMLNJ\\bin\.run\run.x86-win32.exe: Fatal error -- Uncaught exception Error with 0
raised at ../compiler/TopLevel/interact/evalloop.sml:66.19-66.27

[autoloading done]
C:\Users\Localadmin\Desktop\CS 671\Program 3\commonFactors.sml:1.87 Error: unbound variable or constructor: x
C:\Users\Localadmin\Desktop\CS 671\Program 3\commonFactors.sml:1.44-1.110 Error: types of if branches do not agree [literal]
then branch: int
else branch: (''Z * int) list
in expression:
    if (List.exists (fn <pat> => <exp>)) a
    then <errorvar> + 1
    else a @ (e,1) :: nil
[Finished in 0.5s with exit code 1]

Answer 1

不太确定如何修复当前的程序，但您可以通过将其一分为二来解决此问题:将相等的元素分组，然后对列表进行排序。

(* Groups successive equal elements into a tuples (value, count) *)
fun group (l as (x :: _)) = 
    let val (firstGroup, rest) = List.partition (fn y => x = y) l
    in 
        (x, List.length firstGroup) :: (group rest)
    end
  | group [] = []

(* Now that we have our elements grouped, what's left is to order
   them as required. *)
fun turnIntoPairs xs =
    ListMergeSort.sort (fn ((x, _), (y, _)) => x >= y) (group xs)