Re: [Caml-list] tip for tail recursive map

[Damien Doligez <damien.doligez@inria.fr>]

On 2009-10-23, at 21:55, pikatchou pokemon wrote:

> I know this topic has been discussed several times, but I don't  
> think I have seen the solution I use for functions of the List  
> module which are not tail recursive.
> I thought sharing the tip could be nice.
> I will take an example, List.map.
> When rewritten in CPS map becomes:
>
> let rec map k f = function
>   | []    -> k []
>   | x :: rl -> map (fun res -> k ((f x) :: res)) f rl

You can do better with an ad-hoc encoding of the continuation
instead of using closures:

let rec map k f = function
   | [] -> List.rev k
   | x :: rl -> map (f x :: k) f rl
;;

The memory footprint is smaller, and you spend much less time
invoking closures.

Note that I haven't bothered benchmarking these two functions.

-- Damien