Tail recursive List.map

Question

The typical List.map function in OCaml is pretty simple, it takes a function and a list, and applies the function to each items of the list recursively. I now need to convert List.map into a tail recursive function, how can this be done? What should the accumulator accumulate?

Answer 1

Arguably the simplest approach is to implement map in terms of an tail-recursive auxiliary function map_aux that traverses the list while accumulating an already mapped prefix:

let map f l =
  let rec map_aux acc = function
    | [] -> acc
    | x :: xs -> map_aux (acc @ [f x]) xs
  in
  map_aux [] l

However, as the list-catenation operator @ takes time linear in the length of its first argument, this yields a quadratic-time traversal. Moreover, list catenation is itself not tail-recursive.

Hence, we want to avoid the use of @. This solution does not use list catenation, but accumulates by prepending newly mapped arguments to the accumulator:

let map f l =
  let rec map_aux acc = function
    | [] -> List.rev acc
    | x :: xs -> map_aux (f x :: acc) xs
  in
  map_aux [] l

To restore the mapped elements in their right order, we then simply have to reverse the accumulator in the case for the empty list. Note that List.rev is tail-recursive.

This approach, finally, avoids both recursive list-catenation and list reversal by accumulating a so-called difference list:

let map f l =
  let rec map_aux acc = function
    | [] -> acc []
    | x :: xs -> map_aux (fun ys -> acc (f x :: ys)) xs
  in
  map_aux (fun ys -> ys) l

This idea is to have the accumulated prefix list be represented by a function acc that, when applied to an argument list ys, returns the prefix list prepended to ys. Hence, as an initial value of the accumulator we have fun ys -> ys, representing an empty prefix, and in the case for [] we simply apply acc to [] to obtain the mapped prefix.

Answer 2

(I'll take your word that this isn't homework.)

The answer is one of the classic patterns in functional programming, the cons/reverse idiom. First you cons up your list in reverse order, which is easy to do in a tail recursive way. At the end, you reverse the list. Reversing is also a tail-recursive operation, so that doesn't pose a problem for stack safety.

The downside is extra allocation and somewhat more clumsy code.

let map f list =
  let rec loop acc = function
    | [] -> List.rev acc
    | x::xs -> loop (f x::acc) xs in
  loop [] list

A good exercise is to (re)implement a bunch of the 'standard' list functions (append, rev_append, fold_left, fold_right, filter, forall, etc), using this style to make them tail-recursive where necessary.