Version française
Home     About     Download     Resources     Contact us    
Browse thread
tip for tail recursive map
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Damien Doligez <damien.doligez@i...>
Subject: Re: [Caml-list] tip for tail recursive map

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