tabulators

[Stephen Weeks]

> 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?

I don't have any better ideas than your code.
	outside the basis, with no side effects:
		use a list and reverse at the end
		(although it would be better to do
			Vector.rev o Vector.fromList
		instead of 
			Vector.fromList o List.rev)
	outside the basis, with side effects:
		use an array, convert to a vector at the end
	inside the basis, with side effects and unsafe ops
		use an array, coerce to a vector at the end

> Here's a direct conversion from S7 to S1

Makes sense.

> 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.

There are two orthogonal choices.

1. Whether to construct or destruct the vector.
2. Whether the vector library controls the stack or not.

Here is what we've got for those

		stack	not
		------	---------
construct	unfold	tabulator
destruct	fold	iterate

We don't have iterate yet, but I'm thinking about it.  The advantage
of a tabulator over an unfolder is that the tabulator allows someone
else to control the stack while the vector is being constructed.  So,
for example, if you want to convert a tree in preorder traversal to a
vector, it is easy with a tabulator, but not with an unfolder, because
you must reify the tree traversal stack into state.

Another way to see the difference is that it is easy to convert from
an implementation of tabulators to unfolders, but not vice versa.

--------------------------------------------------------------------------------
signature TABULATOR =
   sig
      type 'a t
      datatype 'a tab = Done of 'a t | More of 'a -> 'a tab
      val tabulator: int -> 'a tab
   end

signature UNFOLD =
   sig
      type 'a t
      val unfold: int * 'b * ('b -> 'a * 'b) -> 'a t
   end

functor TtoU (S: TABULATOR): UNFOLD =
   struct
      type 'a t = 'a S.t

      fun unfold (n, b, f) =
	 let
	    fun loop (t, b) =
	       case t of
		  S.Done v => v
		| S.More g =>
		     let
			val (a, b) = f b
		     in
			loop (g a, b)
		     end
	 in
	    loop (S.tabulator n, b)
	 end
   end
--------------------------------------------------------------------------------

The only way I know how to go the other direction in general is to use
coroutines.

BTW, I dislike the name "tabulator", since it is too close to
"tabulate", which we use for a special case of unfold.  I would be
happy to hear suggestions for another name.  Maybe just "construct",
since it is the most general kind of constructor (that I know of)?