在 OCaml 中递归删除重复尾部

Question

我尝试通过迭代一个带有空列表的列表来编写complst自己的解决方案，其中所有非重复项都被插入然后返回。在查找解决方案后，我知道这是一种过于复杂的方法，但仍然想了解为什么模式匹配不能按预期工作：

let compress list =
  let rec aux complst lst =
    match lst with 
    | [] -> complst
    | a :: (b :: c) -> if a = b then aux complst (b::c) else aux (a::complst) (b::c)
    | x -> x  
  in aux [] list;;
val comp : 'a list -> 'a list = <fun>

无论输入如何，输出始终是一个仅包含最后一个元素的列表：

 compress [1;1;2;2;3];;
- : int list = [3]

 compress [1;2;3];;
- : int list = [3]

Answer 1

模式匹配

您的模式匹配匹配三种模式：

1. 空列表：[]
2. 至少包含两个元素的列表：a :: (b :: c)
3. 一个包罗万象的东西，它必须通过消除过程成为具有单个元素的列表。

考虑一下当我们评估您的示例时会发生什么：

compress [1; 1; 2; 2; 3]
aux [] [1; 1; 2; 2; 3]
aux [] [1; 2; 2; 3]
aux [1] [2; 2; 3]
aux [1] [2; 3]
aux [2; 1] [3]
[3]

哎呀，一击中lst它就[3]返回了。

让我们通过添加到 来重写您的函数来处理该单个元素列表complst。

let compress lst =
  let rec aux complst lst =
    match lst with 
    | [] -> complst
    | [x] -> aux (x::complst) []
    | a :: (b :: c) -> 
      if a = b then aux complst (b::c) 
      else aux (a::complst) (b::c)
  in 
  aux [] list

现在：

let compress lst =
  let rec aux complst lst =
    match lst with 
    | [] -> complst
    | [x] -> aux (x::complst) []
    | a :: (b :: c) -> 
      if a = b then aux complst (b::c) 
      else aux (a::complst) (b::c)
  in 
  aux [] list

清理并反转结果列表

当然，还有一些方法可以使用条件保护来稍微清理代码，并且_对于不需要绑定名称的值。您可能还想反转累加器。

let compress lst =
  let rec aux complst lst =
    match lst with 
    | [] -> List.rev complst
    | [x] -> aux (x::complst) []
    | a :: (b :: _ as tl) when a = b -> aux complst tl
    | a :: (_ :: _ as tl) -> aux (a::complst) tl   
  in
  aux [] lst

折叠

当您看到这种一次迭代一个列表元素并累积一个新值的模式时，您通常可以很好地将其映射到List.fold_left.

let compress lst =
  List.(
    lst 
    |> fold_left 
         (fun i x -> 
            match i with 
            | (x'::_) when x = x' -> i 
            | _ -> x::i) 
         [] 
    |> rev
  )

因为List.fold_left一次只能知道列表中的一个元素，所以我们作为第一个参数传递的函数无法知道列表中的下一个元素。但它知道累加器或“init”值。在本例中，这是另一个列表，我们可以对该列表进行模式匹配。

如果它不为空并且第一个元素等于我们正在查看的当前元素，则不要将其添加到结果列表中。否则，请添加它。这也处理累加器为空的第一个元素的情况。

感谢您为这个问题创建了尾递归解决方案！

tail_mod_cons

从 OCaml 4.14.0 及更高版本开始，我们可以使用tail 模块构造函数使此尾递归，而无需跳过任何循环。

一个简单的非尾递归解决方案：

let rec compress = function
  | ([] | [_]) as lst -> lst
  | a::(b::_ as tl) when a = b -> compress tl
  | a::tl -> a :: compress tl

这是可行的，但显然不是尾递归。

let[@tail_mod_cons] rec compress = function
  | ([] | [_]) as lst -> lst
  | a::(b::_ as tl) when a = b -> compress tl
  | a::tl -> a :: compress tl

现在它是！