Appending two lists

Question

So this is one way to append two lists:

let rec append l1 l2 =
  match l1 with
  | h :: t -> h :: append t l2
  | [] -> l2

But I am trying to write a tail-recursive version of append. (solve the problem before calling the recursive function).

This is my code so far, but when I try to add append in the first if statement the code becomes faulty for weird reasons.

let list1 = [1;2;3;4]
let list2 = [5;6;7;8]



let rec append lista listb =
  match listb with
  | h :: taillist -> if taillist != []  then 
  begin 
    lista @ [h];
    (* I cant put an append recursive call here because it causes error*)
  end else
  append lista taillist;
 | [] -> lista;;


append list1 list2;;

Solution 1

The easiest way to transform a non tail-recursive list algorithm into a tail-recursive one, is to use an accumulator. Consider rewriting your code using a third list, that will accumulate the result. Use cons (i.e., ::) to prepend new elements to the third list, finally you will have a result of concatenation. Next, you need just to reverse it with List.rev et voila.

Solution 2

For the sake of completeness, there is a tail-recursive append:

let append l1 l2 =
  let rec loop acc l1 l2 =
    match l1, l2 with
    | [], [] -> List.rev acc
    | [], h :: t -> loop (h :: acc) [] t
    | h :: t, l -> loop (h :: acc) t l
    in
    loop [] l1 l2

I would recommend to solve 99 problems to learn this idiom.

Solution 3

A couple of comments on your code:

1. It seems like cheating to define a list append function using @, since this is already a function that appends two lists :-)

2. Your code is written as if OCaml were an imperative language; i.e., you seem to expect the expression lista @ [h] to modify the value of lista. But OCaml doesn't work that way. Lists in OCaml are immutable, and lista @ [h] just calculates a new value without changing any previous values. You would need to pass this new value in your recursive call.

As @ivg says, the most straightforward way to solve your problem is using an accumulator, with a list reversal at the end. This is a common idiom in a language with immutable lists.

Solution 4

A version using constant stack space, implemented with a couple of standard functions (you'll get a tail-recursive solution after unfolding the definitions):

let append xs ys = List.rev_append (List.rev xs) ys

Incidentally, some OCaml libraries implement the append function in a pretty sophisticated way: (1) see core_list0.ml in the Core_kernel library: search for "slow_append" and "count_append" (2) or batList.mlv in the Batteries library.

View more solutions

Comments

[PatJ]

That != shouldn't be used as it's a "physical" comparison. You want to do a structural comparison using <>. Also, this kind of test could be put directly in the pattern matching.

[nima]

While this code may answer the question, providing additional context regarding how and/or why it solves the problem would improve the answer's long-term value. You can find more information on how to write good answers in the help center: stackoverflow.com/help/how-to-answer . Good luck 🙂