tabulators

[Stephen Weeks]

> > As you showed, it is easy to convert from iterate to fold, just as it
> > is easy to convert from construct to unfold.
> 
> This initially struck me as surprising; arguing by duals would seem to
> suggest the opposite.

The analogy I was using is that it's easy to go from something that
doesn't require the stack to something that does (pretends to).

> Although, it's not that hard to go from a fold to an iterate:

Your solution is easier for me to understand if I defunctionalize it.

------------------------------------------------------------
functor FtoI (S: FOLD): ITERATE =
   struct
      type 'a t = 'a S.t
      datatype 'a iter = Iter of unit -> ('a * 'a iter) option

      datatype 'a f =
	 F1
       | F2 of 'a * 'a f

      fun apply (f, e) =
	 case f of
	    F1 => e
	  | F2 (x, b) => apply (b, Iter (fn () => SOME (x, e)))
	    
      fun iterate v =
	 apply (S.fold (v, F1, F2), Iter (fn () => NONE))
   end  
------------------------------------------------------------

Now we can see that dataype 'a f is isomorphic to lists, so your
solution is equivalent to the following.

------------------------------------------------------------
functor FtoI (S: FOLD): ITERATE =
   struct
      type 'a t = 'a S.t
      datatype 'a iter = Iter of unit -> ('a * 'a iter) option

      fun apply (f, e) =
	 case f of
	    [] => e
	  | x :: b => apply (b, Iter (fn () => SOME (x, e)))
	    
      fun iterate v =
	 apply (S.fold (v, [], op ::), Iter (fn () => NONE))
   end      
------------------------------------------------------------

Now we can see that apply is just a foldl, so your solution is
equivalent to the following.

------------------------------------------------------------
functor FtoI (S: FOLD): ITERATE =
   struct
      type 'a t = 'a S.t
      datatype 'a iter = Iter of unit -> ('a * 'a iter) option

      fun iterate v =
	 List.foldl
	 (fn (x, i) => Iter (fn () => SOME (x, i)))
	 (Iter (fn () => NONE))
	 (S.fold (v, [], op ::))
   end      
------------------------------------------------------------

So, your solution reverses the input into a list, then folds over the
(reversed) list to build the iterator.  I agree that this is correct,
but don't really like it for performance reasons.  The ItoF direction
doesn't require any reversals, so I think it is still fair to say that
ITERATE is "more powerful" than FOLD.

> So, why is it so hard to go from an unfold to a construct? 
> Maybe it's not that hard:

Using defunctionalization again ...

------------------------------------------------------------
functor UtoC (S: UNFOLD): CONSTRUCT =
   struct
      type 'a t = 'a S.t
      datatype 'a cons = Done of 'a t | More of 'a -> 'a cons

      fun construct n =
	 let
	    datatype 'a u =
	       EmptyU
	     | ConsU of 'a * 'a u

	    fun applyU u =
	       case u of
		  EmptyU => raise Fail "UtoC"
		| ConsU (x, e) => (x, e)

	    datatype 'a f =
	       EmptyF
	      | ConsF of 'a * 'a f

	    fun applyF (f, e) =
	       case f of
		  EmptyF => e
		| ConsF (x, b) => applyF (b, ConsU (x, e))
		     
	    fun mkCons (i, b) =
	       if i >= n
		  then Done (S.unfold (n, applyF (b, EmptyU), applyU))
	       else More (fn x => mkCons (i + 1, ConsF (x, b)))
	 in
	    mkCons (0, EmptyF)
	 end
   end
------------------------------------------------------------

Notice that datatype 'a f is isomorphic to datatype 'a list.

------------------------------------------------------------
functor UtoC (S: UNFOLD): CONSTRUCT =
   struct
      type 'a t = 'a S.t
      datatype 'a cons = Done of 'a t | More of 'a -> 'a cons

      fun construct n =
	 let
	    datatype 'a u =
	       EmptyU
	     | ConsU of 'a * 'a u

	    fun applyU u =
	       case u of
		  EmptyU => raise Fail "UtoC"
		| ConsU (x, e) => (x, e)

	    fun mkCons (i, b) =
	       if i >= n
		  then Done (S.unfold (n, List.foldl ConsU EmptyU b, applyU))
	       else More (fn x => mkCons (i + 1, x :: b))
	 in
	    mkCons (0, [])
	 end
   end
------------------------------------------------------------

Notice that datatype 'a u is isomorphic to datatype 'a list.

------------------------------------------------------------
functor UtoC (S: UNFOLD): CONSTRUCT =
   struct
      type 'a t = 'a S.t
      datatype 'a cons = Done of 'a t | More of 'a -> 'a cons

      fun construct n =
	 let
	    fun mkCons (i, b) =
	       if i >= n
		  then Done (S.unfold (n, List.rev b,
				       fn [] => raise Fail "UtoC"
					| x :: e => (x, e)))
	       else More (fn x => mkCons (i + 1, x :: b))
	 in
	    mkCons (0, [])
	 end
   end
------------------------------------------------------------

So, your solution accumulates the results in a list, and at the end
reverses the list then calls unfold.  Makes sense, but is slow, and is
again using lists as the universal intermediate format.

It would be interesting to compare both of your solutions using list
reversals to solutions using coroutines.  I would guess that yours are
faster given the current thread switching in MLton, although they
would probably allocate more.  But, if we could improve thread
switching so it is closer in cost to a procedure call, then the
coroutine solution will almost certainly be faster.

> > signature ITERATE2 =
> >    sig
> >       type 'a t
> >       type 'a state
> >       val iterate: 'a t -> {next: 'a state -> ('a * 'a state) option,
> > 			      start: 'a state}
> >    end
> 
> I still don't get why this (or CONSTRUCT2) is useful?  If you build it up
> using C7to2, then you don't seem to have any choice in the state.  

You don't.  It's just that CONSTRUCT2 and ITERATE2 can be implemented
purely functionally, while CONSTRUCT1 and ITERATE1 can't.