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