list - List.rev 行为奇怪吗？

Question

我是 OCaml 的新手，并试图将 List.append 实现为一种学习练习。这就是我所拥有的:

let rec append a b =
    match (List.rev a) with
       []       -> b
       | x:: xs -> append xs (x::b)

这似乎有效，直到参数 a 有两个以上的元素。例子:

# append [1;2] [3;4] 
- : int list = [1; 2; 3; 4]
# append [1;2;3] [4;5;6]
- : int list = [2; 1; 3; 4; 5; 6]

这里发生了什么？我检查过， List.rev [1;2;3] 返回 int list = [3; 2; 1] 。我知道我的实现是幼稚的，而不是(还)懒惰的，但它似乎应该有效。

Answer 1

如果您考虑一下，您会多次颠倒您的第一个列表。可能比你想要的更多。

如果您按照示例的步骤操作，您可以看到发生了什么。

append [1; 2; 3] []
(* match binds x to 3, xs to [2; 1] *)
append [2; 1] [3]
(* match binds x to 1, xs to [2] *)
append [2] [1; 3]
(* match binds x to 2, xs to [] *)
append [] [2; 1; 3]
(* done *)