tabulators

[Matthew Fluet]

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

Random thought that occured to me.  CONSTRUCT and ITERATE (when
implemented from within the basis) allow efficient implementations of
"multiple mappers" like

val mapTo2: 'a t * ('a -> ('b * 'c)) -> ('b t * 'c t)

which is something I've often been irked by when writing SSA passes when I
need to make wrapper/router functions where I alpha-vary an argument list
and then need to extract just the Var.t's for a Goto.

E.g., in the SSA restore pass, when I need to introduce new
HandlerPush/Pop's, I need a new handler block with the same type as the
original handler block, that does the new HandlerPush, and then passes all
of it's arguments unchanged to the original handler block:

val newArgs = Vector.map(args, fn (x, ty) => (Var.new (), ty))
val gotoArgs = Vector.map(newArgs, #1)

or

val newgotoArgs = Vector.map(args, fn (x, ty) => let val y = Var.new ()
                                                 in ((y, ty), y)
                                                 end)
val (newArgs, gotoArgs) = Vector.unzip args

both of which obviously need two passes over a vector.  But

val (newArgs, gotoArgs) = Vector.mapTo2
                          (args, fn (x, ty) => let val y = Var.new ()
                                               in ((y, ty), y)
                                               end)

could be done with one pass.

As a side comment, while we could certainly add mapTo2 to the Vector
structure as things exist now, I actually think that from a design
stand-point it doesn't belong there.  A quick look at the signature
suggests that just about everything there can be done with exactly one
pass over the input vector and directly accumulate the result (as in a
fold) or simultaneously produce the result vector (using unfoldi).  So,
adding something like mapTo2 gives the "illusion" that it is more
efficient than it really is.


Even further afield, I am somewhat irked by the fact that I can't write a
signature like:

val map{N}To{M} : ('a1 t * ... * 'a{N} t * 'a -> ('b1 * ... * 'b{M})) ->
                  ('bt t * ... * 'b{M} t)

and be able to use map1To3 and map10To2 without changing the library
and/or making some "arbitrary" choice of what functions should be provided
by the library.