[MLton] Monadic MLton.Vector.create with update

[Daniel C. Wang]

Perhaps, vector create is too ambitious. I'd be happier with an unfold 
operation. It's a relatively simple generalization of Vector.tabulate, 
that lets you do a lot more. (Not random access but I think for a lot of 
situations  that's okay). It also avoids the need for a dummy initial 
value too. I'd like to see this in addition to any MLton.Vector.create

functor Test (val unfold_vec : ('b -> ('b * 'a)) -> 'b -> int -> 'a  
vector) =
  struct
    fun fib_unfold {fibsub2,fibsub1,n} =
      if n < 2 then
        ({fibsub2=fibsub2,
          fibsub1=fibsub1,
          n=n+1},fibsub1)
        else let
          val fibn = fibsub1 + fibsub2
        in ({fibsub2=fibsub1,
             fibsub1=fibn,
             n=n+1},fibn)
        end
     val fibv = unfold_vec fib_unfold {fibsub1=1,fibsub2=1,n=0} 35
     fun tabulate (len,f) =
       unfold_vec (fn n => (n+1,f n)) 0 len
  end

fun unfold_vec gen seed len = let
  val array = Array.array (len, NONE)
  fun loop (i,seed) =
    if i < len then let
      val (seed,v) = gen seed
    in Array.update(array,i,SOME v);
      loop(i+1,seed)
    end
  else Vector.tabulate(len,(fn i => Option.valOf (Array.sub(array,i))))
in loop(0,seed)
end
structure T = Test(val unfold_vec = unfold_vec);


Vesa Karvonen wrote:
> 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
>
> _______________________________________________
> MLton mailing list
> MLton@mlton.org
> http://mlton.org/mailman/listinfo/mlton
>