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

[Gabriel Scherer <gabriel.scherer@gmail.com>]

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

>
> Please, don't do that hack ! The compiler assumes immutable data are not
> mutated and optimise knowing that.
>

My understanding was that it is unsafe to Obj.magic an immutable data
structure into a mutable one (one mental model is that immutable data
might be allocated in read-only memory, although that's not what the
current implementation does), but that on the contrary it is safe to
Obj.magic a mutable data-structure into an immutable one. The
Obj.magic-using code for List.map, implemented in Extlib and inherited by
Batteries, is careful to use an unsafe cast in exactly the second
situation. This is a feature that other languages (eg. Mezzo) safely
provide.

If this last technique became invalid because of compiler optimization in
the future, that would need to be clearly exposed and justified. Could you
confirm that this is not the case today?

(I think this is also the way immutable recursive value work, with a
tying-the-knot mutation followed by a conceptual "freeze" of the resulting
structure.)

On Mon, Sep 29, 2014 at 4:02 PM, Pierre Chambart <
pierre.chambart@laposte.net> 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
>
>
> --
> 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: 3064 bytes --]