[MLton-user] Stream Fusion

[Vesa Karvonen]

On 5/8/07, Stephen Weeks <sweeks at sweeks.com> wrote:
> Another standard way to hide existentials is to use a ref cell hidden
> in a closure.
[...]
> datatype 'a step =
>    DONE
>  | GIVE of 'a
>  | SKIP
>
> datatype 'a t = T of unit -> 'a step
>
> val unfold : 's * ('s -> ('a * 's) option) -> 'a t =
>    fn (s, f) => let
>       val r = ref s
>    in T (fn () =>
>          case f (!r) of
>             NONE => DONE
>           | SOME (a, s) => (r := s; GIVE a))
>    end

[I meant to sent this note much earlier, but never got around to it.]

Note that this gives a different semantics.  A stream using the above
implementation is ephemeral and can be iterated (folded) only once.
Of course, in most cases one only wants to iterate a stream once.
However, it is possible to implement streams using a universal type
(http://mlton.org/UniversalType) and the universal type can be
implemented using either exceptions or refs and closures.

In fact, the Extended Basis library now includes a scaled down
implementation of streams using a universal type:

  http://mlton.org/cgi-bin/viewsvn.cgi/mltonlib/trunk/com/ssh/extended-basis/unstable/public/sequence/stream.sig?view=auto
  http://mlton.org/cgi-bin/viewsvn.cgi/mltonlib/trunk/com/ssh/extended-basis/unstable/detail/sequence/stream.sml?view=auto

The stream module implemented in the EB can be compiled with either a
ref+closure or exn based universal type.

-Vesa Karvonen