Re: [Caml-list] Why List.map does not be implemented tail-recursively?

[Martin Jambon <martin.jambon@ens-lyon.org>]

On Sun 28 Sep 2014 09:09:48 PM PDT, Anthony Tavener wrote:
> A remark about the "reverse" list operations... I find that it often
> turns out that I'll have an even number of these reverse operations.
> So even if I need to maintain the final list order, it can be for free.
>
> For example, List.rev_map, followed by a List.rev_append... everything
> is tail-recursive without adding extra list-reversals, and the final
> order is maintained.

I also was obsessed with this when I started using OCaml a long time 
ago and was worried that list operations would double the cost of my 
algorithms (do the math: this is not how it works).

Unfortunately the practice obfuscates the source code. It makes it 
tricky to add or remove an operation in the chain, and overall it's an 
unnecessary cognitive burden for anyone reading the code. These 
optimizations should be done outside of the application code, either in 
the list library or by the compiler; most of the time they are 
absolutely needless anyway.


Martin

> On Sun, Sep 28, 2014 at 8:31 PM, Shuai Wang <wangshuai901@gmail.com
> <mailto:wangshuai901@gmail.com>> wrote:
>
>     Wow, List.rev_map f (List.rev li) looks very elegant, thank you
>     all for the helpful materials! I should definitely try Core lib soon.
>
>     I have been working on a binary program analysis project for over
>     half a year in OCaml, and it is really enjoyable to write OCaml code!
>     hope I can open source the analysis tool eventually and contribute
>     to the community :)
>
>     Best,
>     Shuai
>
>
>
>     On Sun, Sep 28, 2014 at 4:26 PM, Yaron Minsky
>     <yminsky@janestreet.com <mailto:yminsky@janestreet.com>> wrote:
>
>         Indeed, the implementation from that post did make it into
>         Core_kernel.  Here's the link:
>
>         https://github.com/janestreet/core_kernel/blob/release-112.01.00/lib/core_list.ml#L380
>
>         y
>
>         On Sun, Sep 28, 2014 at 3:45 PM, Malcolm Matalka
>         <mmatalka@gmail.com <mailto:mmatalka@gmail.com>> wrote:
>         > https://blogs.janestreet.com/optimizing-list-map/
>         >
>         > And from the horse's mouth:
>         >
>         >
>         https://groups.google.com/forum/#!msg/fa.caml/YaLYqkpn928/1jdo8a0K6AEJ
>         >
>         > Shuai Wang <wangshuai901@gmail.com
>         <mailto:wangshuai901@gmail.com>> writes:
>         >
>         >> Hello list,
>         >>
>         >>
>         >> I am working on some stack_overflow exception in our recent
>         project written
>         >> in OCaml
>         >> and eventually it turns out that this exception is thrown
>         by List.map
>         >> function.
>         >>
>         >> By seeing the source code of OCaml's List module
>         >>
>         <https://code.ohloh.net/file?fid=P5Us_txNCMHIhpdfML6OZ8QN4Zs&cid=Jigg8RAfQdg&s=ocaml%20list.ml&pp=0&fp=305967&fe=ml&ff=1&filterChecked=true&mp=1&ml=1&me=1&md=1#L3>,
>         >> it seems that map function
>         >> does not be implemented tail-recursively:
>         >>
>         >> let rec map f = function
>         >>     [] -> []
>         >>   | a::l -> let r = f a in r :: map f l
>         >>
>         >>
>         >>
>         >> So my question is:
>         >>
>         >> *Why would OCaml's implementation List.map like this?  *
>         >>
>         >> In my humble option, it definitely should be written in a
>         tail-recursive
>         >> way,
>         >> and it not, stack_overflow would be unavoidable.
>         >> For example in order to handle the exception,
>         >> I abandon the code using List.map and rewrite it into a
>         tail-recursive help
>         >> function.
>         >>
>         >> Best,
>         >> Shuai
>         >
>         > --
>         > Caml-list mailing list.  Subscription management and archives:
>         >https://sympa.inria.fr/sympa/arc/caml-list
>         > Beginner's list:http://groups.yahoo.com/group/ocaml_beginners
>         > Bug reports:http://caml.inria.fr/bin/caml-bugs
>
>
>