Following up from Laziness and Streams - Part 1 and inspired by Jeremy Fairbank’s function streams in JavaScript I wanted to try to implement a lazy Stream in Python. The problem is that Python does not have non-strict arguments like Scala does with the => operator. Python does have a lambda keyword which you can use to define functions in a single line expression. The lambda keyword doesn’t need to take arguments, so it can be used as a non-strictness operator hack. This adds a lot of extra syntax, but it allows us to simulate non-strictness and build the same lazy stream implementation that we had in Scala. Here is the code to do the basic Stream construction with map and filter.
class Stream(object):
@staticmethod
def create(*args):
if not args:
return Stream()
return Stream(
lambda: args[0],
lambda: Stream.create(*(args[1:]))
)
def __init__(self, head=None, tail=None):
self.head = head
self.tail = tail
@property
def empty(self):
return self.head is None
def __str__(self):
value = "%s" % self.head() if not self.empty else ""
return "Stream(%s" % value + (", %s" % self.tail() if self.tail else "") + ")"
def fold_right(self, acc, f):
if self.empty:
return acc
return f(
self.head(),
lambda: self.tail().fold_right(acc, f)
)
def map(self, f):
return self.fold_right(
Stream(),
lambda a, b: Stream(lambda: f(a), b)
)
def filter(self, f):
return self.fold_right(
Stream(),
lambda a, b: (Stream(lambda: a, b) if f(a) else b())
)
We can do the same lazy mapping and filtering as we did in Scala:
s = Stream.create(lambda: 1, lambda: 2, lambda: 3).map(lambda i: i + 1).filter(lambda i: i % 2 == 0)
print(s)
We get Stream(2, Stream(4, Stream())).
If we wanted to create a stream from another iterable, we could write a create_from_iterator method which lazily iterates over the data to create a Stream.
@staticmethod
def create_from_iterator(iterable):
iterator = iter(iterable)
try:
value = iterator.__next__()
except StopIteration:
return Stream()
return Stream(
lambda: value,
lambda: Stream.create_from_iterator(iterator)
)
No we can do:
s = Stream.create_from_iterator(range(1, 4)).map(lambda i: i + 1).filter(lambda i: i % 2 == 0)
print(s)
The result is the same as before: Stream(2, Stream(4, Stream())).
However, calling next on an iterator is not pure since it changes the state of the iterator. This side effect makes evaluating the stream more than once return different results.
If we call print(s) again the result is Stream(2, Stream()).
So using iterators to create streams is not ideal because we’re forced to mutate state which leads to inconsistent results. We need a different way to create streams.
Purely generating streams
To generate the sequence 1, 2, 3 we could write a function like:
def range_stream(start, end):
def loop(current):
if current == end:
return Stream()
return Stream(
lambda: current,
lambda: loop(current + 1)
)
return loop(start)
Running print(range_stream(1, 4)) will print Stream(1, Stream(2, Stream(3, Stream()))).
Now let’s say we wanted a never ending stream of the fibonacci numbers. We can write another recursive function.
def fibonacci():
def loop(n_minus_1, n):
return Stream(
lambda: n_minus_1,
lambda: loop(n, n_minus_1 + n)
)
return loop(0, 1)
If we call fibonacci it will give us a Stream that never terminates. So we can’t actually use any of the values right now. But if we implement a take function on Stream we can take n fibonacci numbers into a new Stream and evaluate that.
def take(self, n):
if n == 0:
return Stream()
return Stream(
lambda: self.head(),
lambda: self.tail().take(n - 1)
)
Running print(fibonacci().take(5)) gives Stream(0, Stream(1, Stream(1, Stream(2, Stream(3, Stream()))))).
The pattern in generating streams is that we always need a recursive function. There is a function called unfold that allows us to simplify generating a stream.
def unfold(self, state, f):
"""
Takes a state and a function f which is passed a state
and returns either None or a (value, state) pair
"""
result = f(state)
if not result:
return Stream()
value, next_state = result
return Stream(
lambda: value,
lambda: self.unfold(next_state, f)
)
We can now implement fibonacci using unfold:
def fibonacci():
return Stream().unfold(
(0, 1),
lambda state: (
state[0],
(state[1], state[0] + state[1])
)
)
We can also refactor take using unfold:
def take_unfold(self, n):
def unfolder(state):
remaining, stream = state
if not remaining:
return
return (stream.head(), (remaining - 1, stream.tail()))
return self.unfold((n, self), unfolder)
Now if we wanted to implement Python’s range function, we could do it using unfold:
def stream_range(start, end=None):
if end is None:
end = start
start = 0
def create_range_stream(i):
if i == end:
return
return (i, i + 1)
return Stream().unfold(start, create_range_stream)
To make our Stream data type play nice with the rest of Python where you may want to use a for loop or a comprehension we can implement __iter__ and __next__ in a type that wraps a Stream.
If we want to be able to use streams in for loops we can do so by implementing __iter__ and __next__
def __iter__(self):
"""On the Stream type
"""
return StreamIterator(self)
class StreamIterator(object):
def __init__(self, stream):
self.stream = stream
def __next__(self):
if self.stream.empty:
raise StopIteration
value = self.stream.head()
self.stream = self.stream.tail()
return value
We have to implement a container class for the stream iterator because Stream is an immutable data structure while the iterator needs to be mutated to keep track of what value to return next.
It’s handy to iterate over a stream in a for loop or comprehension.
for i in stream_range(5, 10):
print(i)
[i for i in stream_range(5, 10)]
Here’s a python fiddle with all the code: https://pyfiddle.io/fiddle/5029d21b-34f4-4a34-929d-ce69d8e954dd/?i=true
Conclusion
Using the property of non-strictness which we faked in Python using lambda, we were able to write a purely functional Stream data structure that can be lazily constructed or evaluated. We saw that when we used a stateful iterator in create_from_iterator, it broke the referential transparency of our Stream data type and returned inconsistent results. So instead we wrote a pure helper function called unfold which can aid in constructing streams like the fibonacci numbers.
There is a big caveat with Python that we’ve ignored here so far, which is that if we try to evaluate too large of a Stream in Python, we’ll exceed the max call stack size and get an error. Since Python does not have tail cail optimization, it can’t re-interpret recursive code into a loop the same way that Scala does. So unfortunately this makes Python a bad fit for implementing purely functional data structures. It looks like someone has found a way to write a tail recursive decorator. I might explore that in another follow up post.