在 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

现在：

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]
aux [3; 2; 1] []
[3; 2; 1]

清理并反转结果列表

当然，还有一些方法可以使用条件保护来稍微清理代码，并使用

_

来处理不需要绑定名称的值。您可能还想反转您的累加器。

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

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

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

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

Answer 2

这里代码的问题主要是最后一部分，它对应于列表中的最后一个元素，所以这里[3]，并且您使用这个单个元素返回该列表。 您需要做的是将其附加到 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::e -> x::complst 
  in aux [] list;;
val comp : 'a list -> 'a list = <fun>

现在您可以检查给定的示例：

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

希望它可以帮助您更好地理解自己的错误。

有关评论的注意事项： 您应该保留 [] 大小写，因为虽然它只能在一种情况下发生，但它仍然是有效的输入，意味着必须保留它！.