[MLton] MLton.Vector.create

[Stephen Weeks]

There is a weakness in the basis library with regard to directly
creating vectors.  Vector.tabulate is useful in some situations, but
often one needs something more flexible.  In the basis, if
Vector.tabulate isn't sufficient, one must resort to creating an array
and then calling Array.vector, which copies the entire array.  This is
obviously wasteful, and can be especially problematic if the
array/vector is huge, in which case copying might not even be possible
in RAM.

Henry and I were talking yesterday about a possible alternative
interface, and came up with the following, which I propose to add to
the MLton.Vector structure.

  val create:
    int * 'a * ({sub: int -> 'a, update: int * 'a -> unit} -> unit) 
    -> 'a vector

The idea of create (n, x, f) is to create an array of size n,
initially filled with x for every element.  Then, pass "sub" and
"update" functions to f, which can do as much computation and mutation
of the array in any manner that it likes.  Then, when f is finished,
we, in constant time convert the array to a vector, using our (in
general unsafe) array->vector conversion function.  Once create has
returned the vector, calls to update will raise an exception.

Here's a proposed implementation of create.  The code lives in
basis-library/arrays-and-vectors/vector.sml.

      fun create (n, x, f) =
         let
            val a = Primitive.Array.array n
            val () =
               Util.naturalForeach (n, fn i => Primitive.Array.update (a, i, x))
            fun sub i =
               if Primitive.safe andalso Primitive.Int.geu (i, n) then
                  raise Subscript
               else
                  Primitive.Array.sub (a, i)
            val isFrozen = ref false
            val max = ref n
            fun update (i, x) =
               if Primitive.safe andalso Primitive.Int.geu (i, !max) then
                  if !isFrozen then
                     raise Fail "attempt to mutate frozen vector"
                  else
                     raise Subscript
               else
                  Primitive.Array.update (a, i, x)
            val () = f {sub = sub, update = update}
            val () = max := 0
            val () = isFrozen := true
         in
            fromArray a
         end