tabulators

[Matthew Fluet]

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

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

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 =
	 (S.fold (v, fn e => e, fn (x, b) =>
		  fn e => b (Iter (fn () => SOME (x, e)))))
	 (Iter (fn () => NONE))
   end

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

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 = U of unit -> 'a * 'a u
	    val error = U (fn () => raise Fail "UtoC")
	    fun mkCons (i, b) =
	       if i >= n
		  then Done (S.unfold (n, b error, fn U f => f ()))
	       else More (fn x => mkCons (i + 1, fn e => 
					  b (U (fn () => (x, e)))))
	 in
	    mkCons (0, fn e => e)
	 end
   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

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.