fold/unfold and friends (Henry, do not read before CVS)

Stephen Weeks MLton@sourcelight.com
Thu, 27 Sep 2001 14:29:14 -0700


Henry, can you remember the discussion we had in Italy about a new version of
fold (or was it unfold) that let the caller of fold be in charge of the stack?
The best that I can regenerate is the following signature.

signature SEQUENCE =
   sig
      type 'a t

      (* These are what we're used to. *)
      val fold: 'a t * 'b * ('a * 'b -> 'b) -> 'b
      val unfold: 'a * ('a -> ('b * 'a) option) -> 'b t
      val unfoldi: int * 'a * (int * 'a -> 'b * 'a) -> 'b t
      val unfoldr: 'a * ('a -> ('b * 'a) option) -> 'b t
      val unfoldri: int * 'a * (int * 'a -> 'b * 'a) -> 'b t

      (* toGen is a folder that lets the caller control the stack. *)
      datatype 'a gen = Gen of unit -> ('a * 'a t) option
      val toGen: 'a t -> 'a gen

      (* These are variants of unfold that let the caller "fill in" the
       * elements.
       *)
      val unfold': (('a -> unit) -> unit) -> 'a t
      val unfoldi': int * (('a -> unit) -> unit) -> 'a t
      val unfolr': (('a -> unit) -> unit) -> 'a t
      val unfoldri': int * (('a -> unit) -> unit) -> 'a t

      (* fromGen is easily implemented in terms of unfold' *)
      val fromGen: 'a gen -> 'a t
   end