Re: [Caml-list] Tail Recursion on Map, Append, etc.

[Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>]

From: Tyson Whitehead <twhitehe@uwo.ca>

> I was wondering about the status of map and friends with regard to tail
> recursion.  There was a big discussion back in 2003 about specific solutions 
> (implementation of the those functions using Obj) and more general compiler 
> support for holes/destination passing.  It started with the following 
> message:
> 
> http://caml.inria.fr/pub/ml-archives/caml-list/2003/01/4a9754e53ff07723caf21b4496d1d267.en.html
> 
> It sounded to me like the general consensus was to immediately implement the 
> specific tail recursive versions of these functions for List and friends 
> (which were provided in the discusion), and then improve the compiler by 
> adding support for advanced hole/destination passing solutions.

The result of this consensus is the extlib library. It provides those
tail-recursive functions.
               http://ocaml-lib.sourceforge.net/
There is no project to include specific support in the compiler, but
the extlib implementation shows that this is not required if a bit of
magic is permitted.

Note that this list is not the core developers list, so the result of
discussions here does not imply anything on the ocaml distribution
itself.

> Looking at the list implementation in the OCaml Debian unstable source, it 
> doesn't look like the more efficient version has been implemented.  Further, 
> looking at the assembler emitted for the code it doesn't look like the 
> compiler supports holes/destination passing either.

To correct a misunderstanding: tail-recursive versions are not
necessarily more efficient (at least on short lists; short meaning
less than 10000 elements), but they are safer.
Non tail-recursive functions are carefully marked in the list module,
and alternative functions are included.
For instance:
  let safe_map f l = List.rev (List.rev_map f l)
  let safe_append l1 l2 = List.rev_append (List.rev l1) l2
provide you with tail recursive versions of map and append.
In practice they perform relatively well, if you don't want to
download extlib.

Jacques Garrigue