[MLton] Monadic MLton.Vector.create with update

Vesa Karvonen vesa.karvonen@cs.helsinki.fi
Thu, 30 Mar 2006 10:04:19 +0300


Quoting Stephen Weeks <sweeks@sweeks.com>:
[...]
> A subtle difference between this monadic code and Vesa's is the bounds
> checks on subscript and update operations.  This code (as well as the
> non-monadic version) dynamically changes the limit as the tabulator
> fills in more elements in the array.  Vesa's bakes in the limit to
> each monadic operation, allowing manipulation only of lower-indexed
> vector elements.  A baked-in limit makes perfect sense, if the entire
> computation for the index is going to be done right then, as the
> monadic approach guarantees.  However, it also hints at a weakness of the
> monadic approach -- it doesn't allow subscripts and updates to occur
> after the tabulator is finished.  This seems weaker than the
> non-monadic approach.
> 
> As far as I can tell, the monadic approach treats subscripts and
> updates the same.  That is, just as it disallows updates after the
> vector has been created, it also disallows subscripts (in the
> tabulator functions, not via Vector.sub, obviously).  This doesn't
> work so well in the situation I mentioned earlier, where one wants to
> create a vector of promises, where the promises can refer to other
> elements in the vector.
[...]

The following is just a quick comment.  I haven't yet read your entire
article carefully and might not have the time to do so until much later
today.

I think that the kind of computations that you are describing are handled
in Haskell by using the implicit recursion that lazy evaluation allows.
In a lazy ML you could simply write

 val rec fib = V.tabulate (n,
                           fn i => if i <= 1 then i
                                   else V.sub (fib, i-1) + V.sub (fib, i-2))

What I'm thinking is that perhaps one shouldn't attempt to make the create
interface too "general".  Using a suitable fixpoint combinator and explicit
lazy evaluation, one should be able to do similar computations even in a
strict ML.  Allowing imperative updates to occure during the initial
construction of an immutable vector already makes it seem a little ad hoc to
me.  The monadic approach (even without updates) already allows "complete
induction" to be used and that seems powerful enough to me.

-Vesa Karvonen