Streams as lazily evaluated lists.
Because the discussion popped up on the social media.
Structure and Interpretation of Computer Programs, Section 3.5 has an explanation on how you can encapsulate state in streams. Now not everyone is familiar with Scheme, therefore it's sometimes useful to express things in a language that's closer to pseudocode: Python.
Let's align on terminology
First of all, linked lists:
A linked list consists of tuples (head, tail). head is the first list element, tail is the remainder of the list. If there is no remainder, tail is a special symbol representing the empty list, often NULL/nil/None.
Iterating through linked lists is easy. Just use the head and tail of each tuple to navigate your way through the list. When encountering nil, stop the iteration. This lends itself well for functional programming.
Delayed linked lists
Delayed linked lists are almost the same, but with a twist: Instead of storing the tail directly, they store a procedure that evaluates to the tail. This may sound silly, but has the interesting application of allowing to model lists of infinite size.
The following implementation in Python also caches the results of each calculation in the linked tuples:
class Stream(object): def __init__(self, head, delayed_tail): self._head = head self._delayed_tail = delayed_tail @property def head(self): return self._head @property def tail(self): if not hasattr(self, "_tail"): self._tail = self._delayed_tail() del self._delayed_tail return self._tail # The following two methods are just for easier debugging. def take(self, n): if n > 0: tail = self.tail if tail: return [self.head] + self.tail.take(n - 1) else: return [self.head] else: return  def __repr__(self): return "[%s...]" % (", ".join(map(repr, self.take(10))))
Examples: Infinite streams of integers
For example, this is the infinite list that contains only ones:
>>> ones = streams.Stream(1, lambda: ones) >>> ones [1, 1, 1, 1, 1, 1, 1, 1, 1, 1...]
You can also create helper functions to do componentwise operations:
>>> streams.add_streams(ones, ones) [2, 2, 2, 2, 2, 2, 2, 2, 2, 2...]
"add_streams" is defined like this:
def add_streams(a, b): if a and b: return Stream(a.head + b.head, lambda: add_streams(a.tail, b.tail)) else: return None
This is a definition of the natural numbers:
>>> N = Stream(0, lambda: add_streams(ones, N)) >>> N [0, 1, 2, 3, 4, 5, 6, 7, 8, 9...]
Encapsulating state from unknown sources
And finally, you can use this to encapsulate state that comes from an unknown source, like a network socket, into a delayed list of tuples with an immutable interface to users.
The following function creates a stream from a Python generator (or any other stateful Python iterable1). The trick here is that we rely on the lazy stream caching its results, so that we can guarantee the iterator is called exactly once for each stream element.
def stream_from_generator(g): try: item = g.next() return Stream(item, lambda: stream_from_generator(g)) except StopIteration: return None
1. A Python iterable is an object that you can call
obj.next() on. It will return something else on every call, and eventually raise a
StopIteration exception, when it's out of elements.