如何在 SML/NJ 中编写一个函数，在给定列表中计算连续相等的元素和 returns 对列表（值，计数）？

Question

我必须在 SML/NJ 中编写一个函数，在给定列表中计算连续相等的元素和 returns 对列表（值，计数）。函数应如下所示：

fun group (xs: ''a list): (''a * int) list

我只能使用匿名函数和结构 List、ListPair 和 Math。

我不知道该怎么做。有人可以帮我吗？

Answer 1

一个简单但低效的方法是写this version of group:

val group : ''a list -> ''a list list

并将输出进一步转换为：

val group_count : ''a list -> (''a * int) list

通过以下方式：

fun group_count xss = map (fn xs => (hd xs, length xs)) xss

但更有效的方法是编写函数 span_count:

fun span_count p x [] count = (count, [])
  | span_count p x (y::xs) count =
    if p (x, y)
    then span_count p x xs (count+1)
    else (count, y::xs)

并递归使用它：

fun group_count [] = []
  | group_count (x::xs) =
    case span_count op= x xs 1 of
      (count, ys) => (x, count) :: group_count ys

如何在 SML/NJ 中编写一个函数，在给定列表中计算连续相等的元素和 returns 对列表（值，计数）？

How to write a function in SML/NJ that in a given list, counts successive equal elements and returns a list of pairs (value, count)?

sml

smlnj