Append a list on to another in oCaml

Question

I need a tail recursive function that appends a list1 infront of list2.

I tried it this way

let rec append lst1 lst2 acc = 
  match lst1 with 
  | [] -> acc @ lst2
  | hd::tl -> append lst1 tl (hd::acc);;

append [1;3;4] [3;4;2] [];;

But the result is "time out" every time

Answer 1

You have unbounded recursion because you're not updating lst1 when you evaluate your test case:

append [1;3;4] [3;4;2] []
append [1;3;4] [3;4] (1 :: [])
append [1;3;4] [3;4] (1 :: 1 :: [])

This will run forever, which explains your "time out" issue.

You need to update lst1. E.g.

let rec append lst1 lst2 acc = 
  match lst1 with 
  | [] -> acc @ lst2
  | hd::tl -> append tl lst2 (hd::acc)

append [1;3;4] [3;4;2] []
append [3;4] [3;4;2] (1 :: [])
append [4] [3;4;2] (3 :: 1 :: [])
append [] [3;4;2] (4 :: 3 :: 1 :: [])
[4;3;1] @ [3;4;2]
[4;3;1;3;4;2]

But that's not right. You need to think about your logic. Lists in OCaml are singly-linked lists. [1; 3; 4] is equivalent to 1 :: 3 :: 4 :: [] and [1; 3; 4; 3; 4; 2] is 1 :: 3 :: 4 :: 3 :: 4 :: 2 :: [].

You just need to replace [] in the first list with [3; 4; 2]. The basic form for this is going to look like:

let rec append lst1 lst2 =
  match lst1 with
  | [] -> ...
  | hd::tl -> hd :: append ... ...