tabulators

[Matthew Fluet]

> Here is what we've got for those
> 
> 		stack	not
> 		------	---------
> construct	unfold	tabulator
> destruct	fold	iterate
> 
> --------------------------------------------------------------------------------

signature FOLD =
   sig
      type 'a t
      val fold: 'a t * 'b * ('a * 'b -> 'b) -> 'b
   end

O.k.  Then I would guess that an ITERATOR looks something like:

signature ITERATOR =
   sig
      type 'a t
      datatype ('a, 'b) iter = 
         Done of 'b | More of ('a * 'b -> 'b) -> ('a, 'b) iter
      val iterator: 'a t -> ('a, 'b) iter
   end

with:

structure VectorIterator : ITERATOR =
   struct
      type 'a t = 'a vector
      datatype ('a, 'b) iter =
	 Done of 'b | More of ('a * 'b -> 'b) -> ('a, 'b) iter
      fun ('a, 'b) iterator (v, b) : ('a, 'b) iter =
	 let
	    val n = Vector.length v
	    fun mkIter (b, i) : ('a, 'b) iter =
	       if i >= n
		  then Done b
	       else More (fn f => mkIter (f (Vector.sub (v, i), b), i + 1))
	 in
	    mkIter (b, 0)
	 end
   end

functor ItoF (S: ITERATOR) : FOLD =
   struct
      type 'a t = 'a S.t
      fun fold (v, b, f) =
	 let
	    fun loop i =
	       case i of
		  S.Done b => b
		| S.More g => loop (g f)
	 in
	    loop (S.iterator (v, b))
	 end
   end

Or, possibly like

signature ITERATOR =
   sig
      type 'a t
      datatype ('a, 'b) iter =
         Done of 'b | More of ('a * 'b -> 'b) -> ('a, 'b) iter * 'b
      val iterator: 'a t * 'b -> ('a, 'b) iter
   end

structure VectorIterator : ITERATOR =
   struct
      type 'a t = 'a vector
      datatype ('a, 'b) iter =
	 Done of 'b | More of ('a * 'b -> 'b) -> ('a, 'b) iter * 'b
      fun ('a, 'b) iterator (v, b) : ('a, 'b) iter =
	 let
	    val n = Vector.length v
	    fun mkIter (b, i) : ('a, 'b) iter =
	       if i >= n
		  then Done b
	       else More (fn f => 
			  let val b = f (Vector.sub (v, i), b)
			  in (mkIter (b, i + 1), b)
			  end)
	 in
	    mkIter (b, 0)
	 end
   end

functor ItoF (S: ITERATOR) : FOLD =
   struct
      type 'a t = 'a S.t
      fun fold (v, b, f) =
	 let
	    fun loop i =
	       case i of
		  S.Done b => b
		| S.More g => let 
				val (i, b) = g f
			      in 
				loop i
			      end
	 in
	    loop (S.iterator (v, b))
	 end
   end


I think the advantage of the second is that by getting the partial state
back at each More application, you could pass state between two iterators.
For example, I can't write foreach2 just using FOLD (*), but I can with
the second ITERATE:

functor MkFE2 (S: ITERATOR) : FOREACH2 = 
   struct
      type 'a t = 'a S.t

      fun error _ = raise (Fail "foreach2")
      fun foreach2 (v1, v2, f) =
	 let
	    fun loop (i1, i2) =
	       case (i1, i2) of
		  (S.Done _, S.Done b) => b
		| (S.More g1, S.More g2) => 
		     let
		        val (i1, h) = g1 (fn (x, _) => fn (y, _) => f (x, y))
			val (i2, ()) = g2 h
		     in
		        loop (i1, i2)
		     end
		| _ => error ()
	 in
	    loop (S.iterator (v1, error), S.iterator (v2, ()))
	 end
   end


(*) Actually, I guess you could by folding over the first sequence with
part of the state being the index, via which one could Vector.sub into the
other vector to get the corresponding element.  But, that doesn't work for
arbitrary sequences, like plain lists where you don't have constant time
access to elements.