tabulators

[Stephen Weeks]

> O.k.  Then I would guess that an ITERATOR looks something like:
> 
> signature ITERATOR =
...
> with:
> 
> structure VectorIterator : ITERATOR =
...

Your code doesn't pass the type checker (maybe you cut and pasted
wrong)!  Anyways, I don't see any need to include the 'b in the
iterator type.  I was thinking of something more like

------------------------------------------------------------
signature ITERATE =
   sig
      type 'a t
      datatype 'a iter = Iter of unit -> ('a * 'a iter) option
      val iterate: 'a t -> 'a iter
      val length: 'a t -> int   (* for later *)
   end
------------------------------------------------------------

This is still completely stateless, and lets you handle multiple
sequences simultaneously.  For example, 

------------------------------------------------------------
functor Fold2 (I: ITERATE):
   sig
      val fold2: 'a I.t * 'b I.t * 'c * ('a * 'b * 'c -> 'c) -> 'c
   end =
   struct
      fun fold2 (va, vb, c, f) =
	 let
	    fun loop (ia, ib, c) =
	       let
		  val I.Iter ga = ia
		  val I.Iter gb = ib
	       in
		  case (ga (), gb ()) of
		     (NONE, NONE) => c
		   | (SOME (a, ia), SOME (b, ib)) => loop (ia, ib, f (a, b, c))
		   | _ => raise Fail "foreach2"
	       end
	 in
	    loop (I.iterate va, I.iterate vb, c)
	 end
   end
------------------------------------------------------------

Actually, I think the right thing to do is to have a single ITER
structure matching the signature 

signature ITER =
   sig
      datatype 'a t = T of unit -> ('a * 'a t) option
   end	

and then have all other signatures that expose an iterate function
export

      val iterate: 'a t -> 'a Iter.t

Rounding out the rest of the signatures in the four boxes, we have.

		stack	no
                ------  ---------
construct	unfold	construct
destruct	fold	iterate

------------------------------------------------------------
signature CONSTRUCT =
   sig
      type 'a t
      datatype 'a cons = Done of 'a t | More of 'a -> 'a cons
      val construct: int -> 'a cons
   end

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

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

As you showed, it is easy to convert from iterate to fold, just as it
is easy to convert from construct to unfold.

------------------------------------------------------------
functor ItoF (S: ITERATE): FOLD =
   struct
      type 'a t = 'a S.t

      fun fold (v, b, f) =
	 let
	    fun loop (S.Iter g, b) =
	       case g () of
		  NONE => b
		| SOME (a, i) => loop (i, f (a, b))
	 in
	    loop (S.iterate v, b)
	 end
   end
------------------------------------------------------------

By analogy with my earlier mail on constructors (tabulators at the
time), here are a couple of special cases of iterators.  I have used
the same numbering scheme so you can see the analogy.

------------------------------------------------------------
signature ITERATE7 = ITERATE

signature ITERATE1 =
   sig
      type 'a t
	 
      val iterate: 'a t -> unit -> 'a
   end

signature ITERATE2 =
   sig
      type 'a t
      type 'a state
      val iterate: 'a t -> {next: 'a state -> ('a * 'a state) option,
			    start: 'a state}
   end

fun tooFew () = raise Fail "too few"
fun tooMany () = raise Fail "too many"

functor C7to1 (S: ITERATE7): ITERATE1 =
   struct
      type 'a t = 'a S.t

      fun iterate v =
	 let
	    val r = ref (S.iterate v)
	 in
	    fn () => let
			val S.Iter g = !r
		     in
			case g () of
			   NONE => tooFew ()
			 | SOME (a, i) => (r := i; a)
		     end
	 end
   end

functor C7to2 (S: ITERATE7): ITERATE2 =
   struct
      type 'a t = 'a S.t

      type 'a state = 'a S.iter

      fun iterate v =
	 {next = fn S.Iter g => g (),
	  start = S.iterate v}
   end
------------------------------------------------------------

Here is how to pair up an iterator (which needs no stack) with an
unfolder (which needs the stack) to convert from one type to another.

------------------------------------------------------------
functor ConvIU (structure I: ITERATE
		structure U: UNFOLD)
   : sig
	val conv: 'a I.t -> 'a U.t
     end =
     struct
	fun conv v =
	   U.unfold (I.length v, I.iterate v,
		     fn I.Iter f =>
		     case f () of
			NONE => tooFew ()
		      | SOME (a, i) => (a, i))
     end
------------------------------------------------------------

There is a similar pairing of folders (which need the stack) with
constructors (which do not).

------------------------------------------------------------
functor ConvFC (structure C: CONSTRUCT
		structure F: FOLD):
   sig
      val conv: 'a F.t -> 'a C.t
   end =
   struct
      fun conv v =
	 case F.fold (v, C.construct (F.length v),
		      fn (a, c) =>
		      case c of
			 C.Done _ => tooMany ()
		       | C.More g => g a) of
	    C.Done v' => v'
	  | C.More _ => tooFew ()
   end
------------------------------------------------------------

Finally, one can form a converter by pairing up both boxes that don't
need the stack, but then, of course, one must do the looping oneself.

------------------------------------------------------------
functor ConvIC (structure C: CONSTRUCT
		structure I: ITERATE)
   : sig
	val conv: 'a I.t -> 'a C.t
     end =
     struct
	fun conv v =
	   let
	      fun loop (c, i) =
		 case c of
		    C.Done v => v
		  | C.More f =>
		       let
			  val I.Iter g = i
		       in
			  case g () of
			     NONE => raise Fail "length mistmatch"
			   | SOME (a, i) => loop (f a, i)
		       end
	   in
	      loop (C.construct (I.length v), I.iterate v)
	   end
     end
------------------------------------------------------------