tabulators

[Matthew Fluet]

> Because S7 can not raise any exceptions and is more powerful than all
> the others, it is, I believe the right interface to use for
> Vector.tabulator.  It also has the nice property that it can be
> implemented without any side-effects, while hiding the type of its
> internal state inside the closure.

Do you really mean without any side-effects (array updates, ref cells,
etc.)?  And the other question is whether you mean inside the Basis
Library (where you've got unsafe array and vector operations) or outside
the Basis Library?

For outside the Basis, I came up with the following with no side effects:

structure VectorTabulator : S7 =
   struct
      type 'a t = 'a vector
      datatype 'a tab = Done of 'a t | More of 'a -> 'a tab
      fun 'a tabulator n =
	 let
	    fun mkTab (l, i) : 'a tab =
	       if i >= n
		  then Done (Vector.fromList (List.rev l))
	       else More (fn x => mkTab (x::l, i - 1))
	 in
	    mkTab ([], 0)
	 end
   end

But, the Vector.fromList seems to somewhat defeat the purpose of a more
general tabulator -- namely, that we don't require building the structure
up from a list.  (Or, maybe I'm missing the point; see my other comments
at the end.)

Outside the Basis, but with side effects, I came up with:

structure VectorTabulator : S7 =
   struct
      type 'a t = 'a vector
      datatype 'a tab = Done of 'a t | More of 'a -> 'a tab
      fun 'a tabulator n =
	 let
	    fun mkTab (a, i) : 'a tab =
	       if i >= n
		  then Done (Array.extract (a, 0, NONE))
	       else More (fn x =>
			  let val _ = Array.update (a, i, x)
			  in mkTab (a, i - 1)
			  end)
	 in
	    if n = 0
	       then Done (Vector.fromList [])
	    else More (fn x =>
		       let val a = Array.array (n, x)
		       in mkTab (a, n - 1)
		       end)
	 end
   end

That's a little better in terms of space, but not much in terms of time;
the Array.extract will still be linear in size of the final vector.

Inside the basis (i.e., when you have access to unsafe operations), you
could do even better, where the Array.extract could be replaced by an
array to vector cast.

> Once we have S7, all the rest are easily implemented using the above
> functors.  The question is, which others should be exported.

Here's a direct conversion from S7 to S1 (rather than 7->6->3->2->1
(introduces 2 refs) or 7->6->5->2->1 (introduces 1 ref)).

functor C7to1 (S: S7): S1 =
   struct
      type 'a t = 'a S.t

      fun tabulator (n, f) =
	 let
	    val r = ref (S.tabulator n)
	    val _ = f (fn x => r := (case !r of
				        S.Done v => tooMany ()
				      | S.More g => g x))
	 in
	    case !r of
	       S.Done v => v
	     | S.More _ => tooFew ()
	 end
   end

A direct S7 to S2 should also be easy.

> S7    tabulator  
> S6	tabulatorDN
> S2	tabulatorFold
> S1	tabulatorSetEach

Those all seem fine to me.  Although, I'm still not quite clear on the
advantages of a tabulator over an unfolder, and how one is supposed to
recognize the right place to use a tabultor.