share/lib/std/control/iterator.flx

  Class of data structures supporting streaming.
  The container type just needs an iterator method.
  The iterator method returns a generator which
  yields the values stored in the container.
  class Iterable [C1, V] {
    virtual fun iterator : C1 -> 1 -> opt[V];
  }
  
  class Streamable[C1, V] {
    inherit Iterable[C1,V];
  
    // check if a streamable x is a subset of a set y.
    virtual fun \(\subseteq\)[C2 with Set[C2,V]] (x:C1, y:C2) = 
    {
      for v in x do
        if not (v \(\in\) y) goto bad;
      done
      return true;
  bad:>
      return false;
    }
  
    // subset or equal: variant equality bar
    fun \(\subseteqq\) [C2 with Set[C2,V], Streamable[C2,V]] 
      (x:C1, y:C2) => x \(\subseteq\) y
    ;
  
    // congruence (equality as sets)
    virtual fun \(\cong\)[C2 with Set[C2,V], Streamable[C2,V], Set[C1,V]] 
      (x:C1, y:C2) => x \(\subseteq\) y and y \(\subseteq\) x
    ;
  
    // negated congruence
    fun \(\ncong\)[C2 with Set[C2,V], Streamable[C2,V], Set[C1,V]] 
      (x:C1, y:C2) => not (x \(\cong\) y)
    ;
  
    // proper subset
    virtual fun \(\subset\) [C2 with Set[C2,V], Streamable[C2,V], Set[C1,V]] 
      (x:C1, y:C2) => x \(\subseteq\) y and x \(\ncong\) y
    ;
  
    // variant proper relations with strke-through on equality bar
    fun \(\subsetneq\) [C2 with Set[C2,V], Streamable[C2,V], Set[C1,V]] 
      (x:C1, y:C2) => x \(\subset\) y
    ;
    fun \(\subsetneqq\) [C2 with Set[C2,V], Streamable[C2,V], Set[C1,V]] 
      (x:C1, y:C2) => x \(\subset\) y
    ;
  
    // reversed relations, super set
    fun \(\supset\) [C2 with Set[C2,V], Streamable[C2,V], Set[C1,V]] 
      (x:C1, y:C2) => y \(\subset\) x
    ;
  
    fun \(\supseteq\) [C2 with Set[C2,V], Streamable[C2,V]] 
      (x:C1, y:C2) => y \(\subseteq\) x
    ;
  
    fun \(\supseteqq\) [C2 with Set[C2,V], Streamable[C2,V]] 
      (x:C1, y:C2) => y \(\subseteq\) x
    ;
    // variant proper relations with strke-through on equality bar
    fun \(\supsetneq\) [C2 with Set[C2,V], Streamable[C2,V], Set[C1,V]] 
      (x:C1, y:C2) => x \(\supset\) y
    ;
    fun \(\supsetneqq\) [C2 with Set[C2,V], Streamable[C2,V], Set[C1,V]] 
      (x:C1, y:C2) => x \(\supset\) y
    ;
  
  
    // negated operators, strike-through
    fun \(\nsubseteq\) [C2 with Set[C2,V], Streamable[C2,V]] 
      (x:C1, y:C2) => not (x \(\subseteq\) y)
    ;
  
    fun \(\nsubseteqq\) [C2 with Set[C2,V], Streamable[C2,V]] 
      (x:C1, y:C2) => not (x \(\subseteq\) y)
    ;
  
    // negated reversed operators, strike-through
    fun \(\nsupseteq\) [C2 with Set[C2,V], Streamable[C2,V], Set[C1,V]] 
      (x:C1, y:C2) => not (x \(\supseteq\) y)
    ;
  
    fun \(\nsupseteqq\) [C2 with Set[C2,V], Streamable[C2,V], Set[C1,V]] 
      (x:C1, y:C2) => not (x \(\supseteq\) y)
    ;
  
  }
  
  

A functional stream is a coinductive data type dual to a list: it is a function

   uncons: S -> T * S.

First here is the class based definition of a stream. It has some problems as do all such definitions:

share/lib/std/datatype/stream.flx

  class Fstream[T,S] {
    virtual fun uncons: S -> T * S;
  };

And now, we have a stream example. It is suprising? An integer is a stream.

share/lib/std/datatype/stream.flx

  instance Fstream [int,int] {
    fun uncons(x:int) => x, x + 1;
  }

An obvious problem: the stream is ascending. A descending stream is obvious:

fun uncons(x:int) => x, x - 1

and clearly there are rather a LOT of streams that can be defined on an integer.

A stream is the dual of a list, some say it is an infinite list. Here is a stream of optional ints built from a list of ints.

share/lib/std/datatype/stream.flx

  instance Fstream [opt[int], list[int]] {
    fun uncons: list[int] -> opt[int] * list[int] =
    | Cons (h,t) => Some h, t
    | #Empty => None[int], Empty[int]
    ;
  }

The option type is a good way to provide a trailing infinite sequence of values mandated by the definition of a stream.

This function converts an arbitrary stream into a generator. This hides the state type and state value from clients, however the forward iterator we previously had is now degraded to an input iterator (where I use iterator in the C++ sense)

share/lib/std/datatype/stream.flx

  class Stream 
  {
  fun make_generator [T,S with Fstream[T,S]] 
    (var state:S) 
  =>
    gen () : T = {
      var v,s = uncons state;
      state = s;
      return v;
    }
  ;

Felix already has an interesting construction called an iterator, it is a generator function of type

   1 -> opt[T]

We build such iterator out of a stream of optional values

share/lib/std/datatype/stream.flx

  fun make_iterator [T,S with Fstream[opt[T],S]] 
    (var state:S) 
  =>
    make_generator[opt[T],S] state
  ;

Our definition is bad, because so far there is only ONE kind of fstream for every type.

What we really want is that, given some uncons function, we can make a fstream object out of it.

here's our stream object: it has an uncons function and an initial state value. The uncons function is called uncons_f to avoid ambiguities

share/lib/std/datatype/stream.flx

  typedef stream[T,S] = ( state:S, uncons_f: S -> T * S );

Now, instantiate it. The critical thing we're doing is translating the internal uncons_f function, to one that returns a stream object

share/lib/std/datatype/stream.flx

  instance[T,S] Fstream[T, stream[T,S]] {
    fun uncons (x:stream[T,S]) : T * stream[T,S] =>
      let head,tail = x.uncons_f x.state in
      head, (state=tail, uncons_f = x.uncons_f)
    ;
  }
  inherit [T,S] Fstream[T,stream[T,S]];
  }
  open Stream;