将连续重复的列表元素打包到 Ocaml 中的子列表中

Question

我在网站ocaml中发现了99个问题。经过一番思考，我通过将问题分解为几个较小的子问题来解决它。这是我的代码：

let rec frequency x l=
match l with 
|[]-> 0
|h::t-> if x=[h] then 1+(frequency x t)
else frequency x t
;;

let rec expand x n=
match n with
|0->[]
|1-> x
|_-> (expand x (n-1)) @ x
;;


let rec deduct a b=
match b with 
|[]-> []
|h::t -> if a=[h] then (deduct a t)
else [h]@ (deduct a t)
;;

let rec pack l=
match l with
|[]-> []
|h::t -> [(expand [h] (frequency [h] l))]@ (pack (deduct [h] t))
;;

很明显，这个实现有点矫枉过正，因为我必须计算列表中每个元素的频率，展开它并从列表中删除相同的元素，然后重复该过程。算法复杂度大约为 O(N*(N+N+N))=O(N^2) 并且不适用于大型列表，即使它达到了所需的目的。我试着阅读网站上的官方解决方案，上面写着：

# let pack list =
    let rec aux current acc = function
      | [] -> []    (* Can only be reached if original list is empty *)
      | [x] -> (x :: current) :: acc
      | a :: (b :: _ as t) ->
         if a = b then aux (a :: current) acc t
         else aux [] ((a :: current) :: acc) t  in
    List.rev (aux [] [] list);;
val pack : 'a list -> 'a list list = <fun>

代码应该更好，因为它更简洁并且做同样的事情。但是我对里面使用"aux current acc"感到困惑。在我看来，作者在 "pack" 函数内部创建了一个新函数，经过一些精心设计的过程后，能够使用 List.rev 反转列表来获得所需的结果。我不明白的是：

1) 使用这个的意义何在，它让代码乍一看很难阅读？

2) 在另一个需要 3 个输入的函数中使用累加器和辅助函数有什么好处？作者是否隐含地使用了尾递归之类的东西？

3) 有没有办法修改程序，使其可以像我的程序一样打包 all 重复项？

Answer 1

这些问题主要是观点而非事实。

1) 在我看来，您的代码更难理解。

2a) 在OCaml和其他函数式语言中使用辅助函数是很常见的。你应该把它想象成类 C 语言中的嵌套花括号，而不是奇怪的东西。

2b) 是的，代码使用了尾递归，而你的代码没有。您可以尝试为您的代码提供一个包含（比方说）200,000 个不同元素的列表。然后尝试使用官方解决方案。您可能会尝试确定您的代码可以处理的最长的不同值列表，然后尝试为该长度对两种不同的实现进行计时。

2c) 为了编写尾递归函数，有时需要在最后反转结果。这只是增加了线性成本，这往往不足以引起注意。

3) 我怀疑您的代码没有解决给定的问题。如果您只应压缩 adjacent 元素，则您的代码不会执行此操作。如果你想做你的代码对官方解决方案所做的事情，你可以事先对列表进行排序。或者您可以使用地图或哈希表来保持计数。

总的来说，官方的方案在很多方面都比你的好很多。再说一遍，你是在征求意见，这是我的意见。

更新

官方的方案是用了一个辅助函数aux，它有三个参数：当前累加的子列表（相同值的重复次数）、当前累加的结果（倒序）、剩余输入待处理。

不变量是第一个参数（名为current）中的所有值都与未处理列表的头部值相同。最初这是真的，因为 current 是空的。

该函数查看未处理列表的前两个元素。如果它们相同，它将第一个添加到 current 的开头并继续列表的尾部（除了第一个）。如果它们不同，它想开始在 current 中累积不同的值。它通过将 current（将一个额外的值添加到前面）添加到累加结果，然后继续处理带有空 current 值的尾部来实现这一点。请注意，这两者都保持不变。

将连续重复的列表元素打包到 Ocaml 中的子列表中

Pack consecutive duplicates of list elements into sublists in Ocaml

ocaml