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

[Christophe Raffalli <christophe.raffalli@univ-savoie.fr>]

[-- Attachment #1: Type: text/plain, Size: 2752 bytes --]

Julien Verlaguet a écrit :
> Thanks for the tip !
> 
> I used this trick on every function of the List module and didn't try to
> go a step further in specific cases.
> Main problem being List.fold_right ... I couldn't figure out a way to
> encode a more efficient continuation encoding
> than the good old CPS, any ideas ?

reverse the list before and then to a fold_left ?

Cheers,
Christophe

> 
> Thanks
> 
> 2009/11/2 Damien Doligez <damien.doligez@inria.fr
> <mailto: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
> 
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> 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

-- 
Christophe Raffalli
Universite de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tel: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 260 bytes --]