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 *)