tabulators
Matthew Fluet
Matthew Fluet <fluet@CS.Cornell.EDU>
Thu, 24 Jan 2002 18:16:00 -0500 (EST)
> Here is what we've got for those
>
> stack not
> ------ ---------
> construct unfold tabulator
> destruct fold iterate
>
> --------------------------------------------------------------------------------
signature FOLD =
sig
type 'a t
val fold: 'a t * 'b * ('a * 'b -> 'b) -> 'b
end
O.k. Then I would guess that an ITERATOR looks something like:
signature ITERATOR =
sig
type 'a t
datatype ('a, 'b) iter =
Done of 'b | More of ('a * 'b -> 'b) -> ('a, 'b) iter
val iterator: 'a t -> ('a, 'b) iter
end
with:
structure VectorIterator : ITERATOR =
struct
type 'a t = 'a vector
datatype ('a, 'b) iter =
Done of 'b | More of ('a * 'b -> 'b) -> ('a, 'b) iter
fun ('a, 'b) iterator (v, b) : ('a, 'b) iter =
let
val n = Vector.length v
fun mkIter (b, i) : ('a, 'b) iter =
if i >= n
then Done b
else More (fn f => mkIter (f (Vector.sub (v, i), b), i + 1))
in
mkIter (b, 0)
end
end
functor ItoF (S: ITERATOR) : FOLD =
struct
type 'a t = 'a S.t
fun fold (v, b, f) =
let
fun loop i =
case i of
S.Done b => b
| S.More g => loop (g f)
in
loop (S.iterator (v, b))
end
end
Or, possibly like
signature ITERATOR =
sig
type 'a t
datatype ('a, 'b) iter =
Done of 'b | More of ('a * 'b -> 'b) -> ('a, 'b) iter * 'b
val iterator: 'a t * 'b -> ('a, 'b) iter
end
structure VectorIterator : ITERATOR =
struct
type 'a t = 'a vector
datatype ('a, 'b) iter =
Done of 'b | More of ('a * 'b -> 'b) -> ('a, 'b) iter * 'b
fun ('a, 'b) iterator (v, b) : ('a, 'b) iter =
let
val n = Vector.length v
fun mkIter (b, i) : ('a, 'b) iter =
if i >= n
then Done b
else More (fn f =>
let val b = f (Vector.sub (v, i), b)
in (mkIter (b, i + 1), b)
end)
in
mkIter (b, 0)
end
end
functor ItoF (S: ITERATOR) : FOLD =
struct
type 'a t = 'a S.t
fun fold (v, b, f) =
let
fun loop i =
case i of
S.Done b => b
| S.More g => let
val (i, b) = g f
in
loop i
end
in
loop (S.iterator (v, b))
end
end
I think the advantage of the second is that by getting the partial state
back at each More application, you could pass state between two iterators.
For example, I can't write foreach2 just using FOLD (*), but I can with
the second ITERATE:
functor MkFE2 (S: ITERATOR) : FOREACH2 =
struct
type 'a t = 'a S.t
fun error _ = raise (Fail "foreach2")
fun foreach2 (v1, v2, f) =
let
fun loop (i1, i2) =
case (i1, i2) of
(S.Done _, S.Done b) => b
| (S.More g1, S.More g2) =>
let
val (i1, h) = g1 (fn (x, _) => fn (y, _) => f (x, y))
val (i2, ()) = g2 h
in
loop (i1, i2)
end
| _ => error ()
in
loop (S.iterator (v1, error), S.iterator (v2, ()))
end
end
(*) Actually, I guess you could by folding over the first sequence with
part of the state being the index, via which one could Vector.sub into the
other vector to get the corresponding element. But, that doesn't work for
arbitrary sequences, like plain lists where you don't have constant time
access to elements.