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

[Anthony Tavener <anthony.tavener@gmail.com>]

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

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.

On Sun, Sep 28, 2014 at 8:31 PM, Shuai Wang <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>
> 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>
>> 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> 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
>>
>
>

[-- Attachment #2: Type: text/html, Size: 5282 bytes --]