=> 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, 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)
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
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)
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) )
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
def fibonacci(): return Stream().unfold( (0, 1), lambda state: ( state, (state, state + state) ) )
We can also refactor
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
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
__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
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
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.