如何统计 OCaml 中任意元素类型的列表中连续出现的次数？

Question

在 OCaml 中，假设我有一个字符串列表，如下所示：

let ls : string list = ["A"; "A"; "B"; "B"; "A"; "Y"; "Y"; "Y"] ;;

我在编写一个函数来计算一个元素连续出现的次数并将该元素与其频率配对时遇到了麻烦。例如，将上面的列表作为输入，该函数应返回

[("A", 2); ("B", 2), ("A", 1), ("Y", 3)]

。

我尝试在其他地方寻找一些提示，但几乎所有其他类似的操作都是使用

int list

完成的，在这里很容易简单地将数字相加。但在这里，我们无法添加字符串。

我的直觉是使用类似

fold_left

的类似方式，如下所示：

let lis : int list = [1;2;3;4;5]
let count (lis : int list) = List.fold_left (fun x y -> x + y) (0) (lis)

本质上是从左到右对所有元素进行累加求和。但是，就我而言，我不想对所有元素进行累积求和，我只需要计算一个元素连续出现的次数。一些建议将不胜感激！

Answer 1

这显然是一项家庭作业，所以我只会给出一些提示。

当您的代码运行时，它不会将字符串（或任何其他类型）添加在一起。它将把整数加在一起。所以你可能想再次回顾一下网上的那些例子:-)

您绝对可以使用

fold_left

来获得答案。首先，请注意 resultl 是一个对的列表。每对的第一个元素可以是任何类型，具体取决于原始列表的类型。每对中的第二个元素是 int。所以你有一个正在使用的基本类型：

('a * int) list

。

想象一下你有办法“增加”这样一个列表：

let increment (list: ('a * int) list) value =
     (* This is one way to think of your problem *)

该函数在列表中查找第一个元素等于 value 的对。如果找到它，它将返回一个新列表，其中关联的 int 比以前大 1。如果没有找到，它会返回一个带有额外元素的新列表

(value, 1)

。

这是您想要折叠列表的基本操作，而不是示例代码的

+

操作。

Answer 2

您正在进行游程长度编码。 本质上，您需要迭代列表，如果找到连续的元素，则增加计数。如果我们使用累加器，这会变得更容易。为了提高效率，我们向后构建它，然后在到达列表末尾时反转它。

但是采取这一步是为了提高效率，也意味着可以很容易地访问我们添加的最后一个元素。

我们需要担心三种情况：当列表为空时，我们返回累加器（相反）。如果列表和累加器都not为空，我们将当前元素

x

与结果中的顶部元组

(y, c)

进行比较。如果

x

和

y

相等，我们需要递归调用，更新列表中的顶部元组。如果它们不相等，我们只需要用

(x, 1)

将一个元组添加到结果中。

# let rec rle lst acc =
    match lst, acc with
    | [], _ -> List.rev acc
    | x::xs, (y, c)::ys when x = y -> rle xs @@ (y, c + 1) :: ys
    | x::xs, _ -> rle xs @@ (x, 1) :: acc;;
val rle : 'a list -> ('a * int) list -> ('a * int) list = <fun>
# rle ["A"; "A"; "B"; "B"; "A"; "Y"; "Y"; "Y"] [];;
- : (string * int) list = [("A", 2); ("B", 2); ("A", 1); ("Y", 3)]

如果我们看看这对于您的示例是如何工作的：

rle ["A"; "A"; "B"; "B"; "A"; "Y"; "Y"; "Y"] []
rle ["A"; "B"; "B"; "A"; "Y"; "Y"; "Y"]      [("A", 1)]
rle ["B"; "B"; "A"; "Y"; "Y"; "Y"]           [("A", 2)]
rle ["B"; "A"; "Y"; "Y"; "Y"]                [("B", 1); ("A", 2)]
rle ["A"; "Y"; "Y"; "Y"]                     [("B", 2); ("A", 2)]
rle ["Y"; "Y"; "Y"]                          [("A", 1); ("B", 2); ("A", 2)]
rle ["Y"; "Y"]                               [("Y", 1); ("A", 1); ("B", 2); ("A", 2)]
rle ["Y"]                                    [("Y", 2); ("A", 1); ("B", 2); ("A", 2)]
rle []                                       [("Y", 3); ("A", 1); ("B", 2); ("A", 2)]
List.rev [("Y", 3); ("A", 1); ("B", 2); ("A", 2)]
[("A", 2); ("B", 2); ("A", 1); ("Y", 3)]

更进一步，您可以使用 sequences 来延迟生成运行时编码，不仅在列表上，而且在任何可以转换为序列的东西上。

let rle_seq seq =
  let rec aux ?(acc=None) seq () =
    Seq.(
      match seq (), acc with
      | Nil, None -> Nil
      | Nil, Some acc' -> 
        Cons (acc', empty)
      | Cons (x, seq'), None -> 
        aux ~acc: (Some (x, 1)) seq' ()
      | Cons (x, seq'), Some (last, count) when x = last -> 
        aux ~acc: (Some (last, count+1)) seq' ()
      | Cons (x, seq'), Some acc' -> 
        Cons (acc', aux ~acc: (Some (x, 1)) seq')
    )
  in
  aux seq

# [|1; 3; 3; 5; 7; 8; 9; 1; 1; 1; 2|]
  |> Array.to_seq
  |> rle_seq
  |> List.of_seq;;
- : (int * int) list =
[(1, 1); (3, 2); (5, 1); (7, 1); (8, 1); (9, 1); (1, 3); (2, 1)]