[MLton] Monadic MLton.Vector.create with update

[Stephen Weeks]

> It wouldn't help much for the growing case, but one thing that could
> be implemented would be a kind of array shrink primitive.  You would
> have to make sure that none of the now unused space at the end
> didn't contain pointers, and the next GC would view it as garbage.

It's pretty easy to trick the runtime -- one just needs to put an
appropriate header at the beginning of the unused space to say that
here some non-pointer bytes.  Nothing would point at it so it would go
at the next GC.  The only issue I can think of is the situation where
there is only one word of unused data -- I think we have a minimum
object size of two words.  But, that may only be necessary for objects
that can be forwarded.  So perhaps we could get by with a special
header.

Telling MLton's optimizer about arrays whose size changes is more
difficult.  The analyses certainly take advantage of the fact that
size doesn't change (e.g. to eliminate common-subexp Array.length
calls).  I suspect the right way to go there is to create a new
primitive type, 'a arrayS, which is like an array but has the shrink
primitive and its size may change.  Then, generalize the optimizer so
that the internal array type has a flag that indicates which kind of
array it is.  That way, most of the code can be shared between both
kinds of array, and only the few special cases need be different.s

Not a quick hack, that's for sure.

> I guess one could then implement the unknown size thing by doubling
> on full, and finally doing the in-place shrink.

True.  This has the same benefit of the current Vector.create --
namely it could avoid the copying of a very large array.  But I would
think in most such situations the clearer win is to compute the size
in advance.