Tail-Recursive List Reversal Function in OCaml Example

Implement the function rev : 'a list -> 'a list such that rev [x1; x2; ...; xn] is [xn; ...; x2; x1]. Make sure that the function is tail-recursive so that large input lists are supported.

Solution

The function to implement is List.rev from the standard library. We proceed recursively based on how the list is constructed.

If we attempt this problem naively, in the case where the list matches the pattern x :: xs, we would recursively reverse xs, and then append x to it. However, since lists in OCaml are built like stacks, this append operation has linear time complexity with respect to the list length.

Instead, we first define a tail-recursive helper function rev_tl : 'a list -> 'a list -> 'a list such that rev_tl l1 l2 is the reverse of l1 prepended onto l2. Here, l2 is effectively an accumulator for the result of reversing the input list. To implement rev using rev_tl, we then use the empty list as initial value for the accumulator.

let rec rev_tl : 'a list -> 'a list -> 'a list =
  fun l acc ->
    match l with
    | [] -> acc
    | x :: xs -> rev_tl xs (x :: acc)

let rev : 'a list -> 'a list =
  fun l ->
    rev_tl l []