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 iterable¹). 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.