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

[Goswin von Brederlow <goswin-v-b@web.de>]

And I'll will do the same, reply anyway.

You can't write List.map tail recursive unless:

1) You use List.rev (List.rev_map fn list).

or

2) Use hacks to create a mutable list so you can grow it head to tail
instead of tail to head.

The fastest code seems to be when you do List.map recursively up to
some limit (say 1000 items) and return the remainder. Repeat and glue
the lists together into one large list using hacks.

MfG
	Mrvn

On Sun, Sep 28, 2014 at 01:45:41PM -0600, Anthony Tavener wrote:
> (Oh, Gabriel beat me to the punch, but I'll add my reply anyway.)
> 
> The standard library is a fairly minimal library of basic features. Not a
> high-level full-featured library which helps you make good choices. :)
> 
> However, the documentation (in .mli files) is fairly clear about what is
> tail-recursive or not. And there is rev_map:
> 
> val rev_map : ('a -> 'b) -> 'a list -> 'b list
> (** [List.rev_map f l] gives the same result as
>    {!List.rev}[ (]{!List.map}[ f l)], but is tail-recursive and
>    more efficient. *)
> 
> 
> On Sun, Sep 28, 2014 at 1:31 PM, Shuai Wang <wangshuai901@gmail.com> wrote:
> 
> > 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