streams - lazy streams abstraction tightly integrated with iterators

Beni Cherniavsky
Tue, 15 Jul 2003 19:48:55 +0300 (IDT)

As a result of the thread about "Snapshottable iterators" on I
decided to separate lazy linked lists from the iterators over them.
The API now looks much more elegant.  Here__ is the result.


This module exposes the duality between linked lists and iterators:

- Simple linked lists have the drawback that their tail must be known and
  finite.  This can be fixed by overloading head/tail access and making it
  lazy; the result is popular in functional programming languages [1]_ under
  the name ''stream''.  This is implemented by the `Stream` class.

- Iterators have the drawback that advancing them is destructive but there is
  no way to capture the ''remaining future'' of an iterator at some moment.
  This can be fixed by making an iterator explicitly point to a stream and
  allow separate iterators to be forked from it.  This is implemented by the
  `StreamIter` class.

Another useful thing about linked lists is that you can non-destructively cons
in front of them.  This is implemented by the `Cons` class (which is also used
to represent the part of stream that has already been computed) and is also
accessible through the `StreamIter.unyield()` method.

A `__stream__()` protocol is defined, paralleling `__iter__()`.  Object can
implement it to provide special implementaion of streams over them (but
normally you would simply implement `__iter__()` and `Stream` will know to
wrap it).  On stream objects this method returns self.

A convenince subscripting interface is provided for streams.

.. [1] See also:

   - The `Streams chapter of SICP`__ shows how streams with a lazy tail can be
     a very powerful abstraction.


   - `SRFI 40: A Library of Streams`__ specifies streams whose head is lazy
     too, which is more elegant and predictable.  It's also a better parallel
     for iterators.  This is the flavour implemented by this module.


   - `STREAM_IO layer`__ of the standard ML basic library seems to provide a
     similar abstration but with buffering.  I don't know ML enough to say


Beni Cherniavsky <>

If I don't hack on it, who will?  And if I don't GPL it, what am I?
And if it itches, why not now?  [With apologies to Hilel ;]