[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