Is List.rev the acting weird way?

Question

I am new to OCaml and trying to implement List.append as an exercise. This is what I have:

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

This seems to work until the argument a contains more than two elements. Example:

 # 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] 

What's going on here? I checked, and List.rev [1;2;3] returns int list = [3; 2; 1] int list = [3; 2; 1] int list = [3; 2; 1] . I know that my implementation is naive and not (yet) lazy, but it seems like it should work.

Answer 1

If you think about it, you change your first list several times. Probably more than you wanted.

You can see what happens if you follow the steps in the example.

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