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

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

On Mon, Sep 29, 2014 at 04:02:11PM +0200, Pierre Chambart wrote:
> On 29/09/2014 14:08, Goswin von Brederlow wrote:
> > 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
> >
> Please, don't do that hack ! The compiler assumes immutable data are not
> mutated and optimise knowing that.
> -- 
> Pierre
> 

I didn't describe the hack. The hack would be to build the result as
mutable list (so the compiler uses write barriers when mutating and
such). But you only mutate once every 1000 items so the cost is
minimal. And at the end you cast the mutable list to an immutable list
(the actual list type).

While still a huge hack I believe going from mutable to immutable is
safe.

MfG
	Goswin