我尝试通过迭代一个带有空 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]
您的模式匹配与三种模式相匹配:
[]
a :: (b :: c)
考虑一下当我们评估您的示例时会发生什么:
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”值。在本例中,这是另一个列表,我们可以对该列表进行模式匹配。
如果它不为空并且第一个元素等于我们正在查看的当前元素,则不要将其添加到结果列表中。否则,请添加它。这也处理累加器为空的第一个元素的情况。
感谢为这个问题创建尾递归解决方案!
这里代码的问题主要是最后一部分,它对应于列表中的最后一个元素,所以这里[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]
希望它可以帮助您更好地理解自己的错误。
有关评论的注意事项: 您应该保留 [] 大小写,因为虽然它只能在一种情况下发生,但它仍然是有效的输入,意味着必须保留它!.