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

[oleg@okmij.org]

Gabriel Scherer wrote
> My intuition would be that the mutation should not be observable in this
> case, as it is only done on "private" data that the List.map function
> allocate, owns, and which never escapes in its immutable form.

Let me explain, on the example of the simplest Hansei function
        val flip : float -> bool
that flips (a possibly unfair) coin; flip 0.5 flips the fair coin.
A good way to understand the meaning of this function is to take the
frequentist approach. There are two ways the function call (flip 0.5)
can return: it can return with true or with false. There are total two
choices, in one of them the function returns true, in another
false. So, the probability of returning true is 1/2. In general, the
complete distribution -- which is the meaning of the program 
(flip 0.5) -- is as follows

# exact_reify (fun () -> flip 0.5);;
- : bool Ptypes.pV = [(0.5, Ptypes.V true); (0.5, Ptypes.V false)]

which is what Hansei computes. Let's take a more complex example,
closer to the topic: two independent coin flips

# let model () = List.map flip [0.5; 0.5]
val model : unit -> bool list = <fun>

# exact_reify model;;
- : bool list Ptypes.pV =
[(0.25, Ptypes.V [true; true]); (0.25, Ptypes.V [true; false]);
 (0.25, Ptypes.V [false; true]); (0.25, Ptypes.V [false; false])]

The result correctly tells that there are four possible choices.

Let us consider the function map from the Batteries. After desugaring,
it has the following form

type 'a mut_list = {
    hd: 'a;
    mutable tl: 'a list
  }

let map : ('a -> 'b) -> 'a list -> 'b list = fun f -> function
  | [] -> []
  | h :: t ->
      let rec loop dst = function
        | [] -> ()
        | h :: t ->
            let cell = {hd = f h; tl = []} in
            dst.tl <- Obj.magic cell;
            loop cell t
      in
      let r = {hd = f h; tl = []} in
      loop r t;
      Obj.magic r

Using this function, we obtain

# let model1 () = map flip [0.5; 0.5]
val model1 : unit -> bool list = <fun>

# exact_reify model1
- : bool list Ptypes.pV =
[(0.5, Ptypes.V [true; false]); (0.5, Ptypes.V [false; false])]

Something went wrong, didn't it? Where are the other two possible
choices -- with true for the second flip -- for the list of two
independent coin flips?

To understand the problem, let us recall the main principle stated
earlier: ``There are two ways the function call (flip 0.5)
can return: it can return with true or with false.'' That is, the
function call (flip 0.5) returns *twice*. Therefore, the call (f h)
in the let cell statement returns twice. Therefore, the assignment
            dst.tl <- Obj.magic cell;
will be executed twice. And the second execution of that assignment
will be with a different cell, which will override and destroy the
result of the first assignment. That is how the "true" choices became
lost.