2009/11/2 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

_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs