(So that's how you say "tail-recursive" in French...) Xavier Leroy <xavier.le...@inria.fr> wrote in article <49cb9854.1020...@inria.fr> in gmane.comp.lang.caml.inria: > A technique that always works is to convert your function to > continuation-passing style. The resulting code is hard to read and > not particularly efficient, though. > > It is possible to do better in a number of specific cases. Functions > operating over lists can often be made tail-rec by adding an > "accumulator" parameter and reversing the accumulator at the end. > For instance, List.map f l (not tail-rec) can be rewritten as > List.rev (List.rev_map f l) (tail-rec).
In fact, it is always possible to do better in the sense above: the accumulator parameter arises mechanically as the result of defunctionalizing the continuation in a CPS program. For example, if we transform "List.map f l (not tail-rec)" into CPS then defunctionalize it, we get essentially "List.rev (List.rev_map f l) (tail-rec)". Sometimes we can improve upon the first-order representation of continuations chosen mechanically by defunctionalization. The factorial function is an example: defunctionalization represents a continuation by a list of numbers, but we can replace the list by the product of the numbers. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 100 Days to close Guantanamo and end torture http://100dayscampaign.org/ http://www.avaaz.org/en/end_the_war_on_terror/ _______________________________________________ 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
