We've provided a set of starter files with skeleton code for the exercises in the lab. You can get them in the following places:
Remember the for
loop? (We really hope so.) The object that the
for
loop iterates over is required to be an iterable!
for elem in iterable:
# do something
for
loops only work with iterables, and that means that the object
you want to use a for
loop on must implement the iterable
interface. In particular, a for
loop makes use of two methods:
__iter__
and __next__
. In other words, an object that implements
the iterable interface must implement an __iter__
method that returns
an object that implements the __next__
method.
This object that implements the __next__
method is called an
iterator. While the iterator interface also requires that the object
implement the __next__
and __iter__
methods, it does not require
the __iter__
method to return a new object.
Here is an example of a class definition for an object that implements the iterator interface:
class AnIterator(object):
def __init__(self):
self.current = 0
def __next__(self):
if self.current > 5:
raise StopIteration
self.current += 1
return self.current
def __iter__(self):
return self
Let's go ahead and try out our new toy.
>>> for i in AnIterator():
... print(i)
...
1
2
3
4
5
This is somewhat equivalent to running:
t = AnIterator()
t = t.__iter__()
try:
while True:
print(t.__next__())
except StopIteration as e:
pass
Try running each of the given iterators in a for
loop. Why does each
work or not work?
class IteratorA(object):
def __init__(self):
self.start = 5
def __next__(self):
if self.start == 100:
raise StopIteration
self.start += 5
return self.start
def __iter__(self):
return self
class IteratorB(object):
def __init__(self):
self.start = 5
def __iter__(self):
return self
class IteratorC(object):
def __init__(self):
self.start = 5
def __next__(self):
if self.start == 10:
raise StopIteration
self.start += 1
return self.start
class IteratorD(object):
def __init__(self):
self.start = 1
def __next__(self):
self.start += 1
return self.start
def __iter__(self):
return self
Watch out on this one. The amount of output might scare you.
For one of the above iterators that works, try this:
>>> i = IteratorA()
>>> for item in i:
... print(item)
Then again:
>>> for item in i:
... print(item)
With that in mind, try writing an iterator that "restarts" every time
it is run through a for
loop.
>>> i = IteratorRestart(2, 7)
>>> for item in i:
... print(item)
2
3
4
5
6
7
>>> for item in i:
... print(item)
2
3
4
5
6
7
A generator is a special type of iterator that can be written using a yield
statement:
def <generator_function>():
<somevariable> = <something>
while <predicate>:
yield <something>
<increment variable>
A generator function can also be run through a for
loop:
def generator():
i = 0
while i < 6:
yield i
i += 1
for i in generator():
print(i)
To better figure out what is happening, try this:
def generator():
print("Starting here")
i = 0
while i < 6:
print("Before yield")
yield i
print("After yield")
i += 1
>>> g = generator()
>>> g
___ # what is this thing?
>>> g.__iter__()
___
>>> g.__next__()
___
>>> g.__next__()
____
Trace through the code and make sure you know where and why each statement is printed.
You might have noticed from the Iterators section that the Iterator
defined without a __next__
method failed to run in the for
loop.
However, this is not always the case.
class IterGen(object):
def __init__(self):
self.start = 5
def __iter__(self):
while self.start < 10:
self.start += 1
yield self.start
for i in IterGen():
print(i)
Think for a moment about why that works.
Think more.
Longer.
Okay, I'll tell you.
The for
loop only expects the object returned by __iter__
to have a
__next__
method, and the __iter__
method is a generator function in
this case. Therefore, when __iter__
is called, it returns a
generator object, which you can call __next__
on.
Write a generator that counts down to 0.
Write it in both ways: using a generator function on its own, and
within the __iter__
method of a class.
def countdown(n):
"""
>>> for number in countdown(5):
... print(number)
...
5
4
3
2
1
0
"""
class Countdown(object):
Write a generator that outputs the hailstone sequence from homework 1.
def hailstone(n):
"""
>>> for num in hailstone(10):
... print(num)
...
10
5
16
8
4
2
1
"""
And now you know how for
loops work! Or more importantly, you have
become a better computer scientist.
A stream is another example of a lazy sequence. A stream is a lazily evaluated RList. In other words, the stream's elements (except for the first element) are only evaluated when the values are needed.
Take a look at the following code:
class Stream(object):
class empty(object):
def __repr__(self):
return 'Stream.empty'
empty = empty()
def __init__(self, first, compute_rest, empty= False):
self.first = first
self._compute_rest = compute_rest
self.empty = empty
self._rest = None
self._computed = False
@property
def rest(self):
assert not self.empty, 'Empty streams have no rest.'
if not self._computed:
self._rest = self._compute_rest()
self._computed = True
return self._rest
def __repr__(self):
return 'Stream({0}, <...>)'.format(repr(self.first))
We represent Streams using Python objects, similar to the way we defined RLists. We nest streams inside one another, and compute one element of the sequence at a time.
Note that instead of specifying all of the elements in __init__
, we
provide a function, compute_rest
, that encapsulates the algorithm
used to calculate the remaining elements of the stream. Remember that
the code in the function body is not evaluated until it is called,
which lets us implement the desired evaluation behavior.
This implementation of streams also uses memoization. The first time
a program asks a Stream
for its rest
field, the Stream
code
computes the required value using compute_rest
, saves the resulting
value, and then returns it. After that, every time the rest
field is
referenced, the stored value is simply returned and it is not computed
again.
Here is an example:
def make_integer_stream(first=1):
def compute_rest():
return make_integer_stream(first+1)
return Stream(first, compute_rest)
Notice what is happening here. We start out with a stream whose first
element is 1, and whose compute_rest
function creates another stream.
So when we do compute the rest
, we get another stream whose first
element is one greater than the previous element, and whose
compute_rest
creates another stream. Hence, we effectively get an
infinite stream of integers, computed one at a time. This is almost
like an infinite recursion, but one which can be viewed one step at a
time, and so does not crash.
Write a procedure add_streams
that takes in two streams s1
, s2
,
and returns a new stream that is the result of adding elements
from s1
by elements from s2
. For instance, if s1
was (1, 2, 3,
...)
and s2
was (2, 4, 6, ...)
, then the output would be the
stream (3, 6, 9, ...)
. You can assume that both Streams are
infinite.
def add_streams(s1, s2):
Write a procedure make_fib_stream()
that creates an infinite stream
of Fibonacci Numbers. Make the first two elements of the stream 0 and
1.
Hint: Consider using a helper procedure that can take two arguments, then think about how to start calling that procedure.
def make_fib_stream():
Naturally, as the theme has always been in this class, we can abstract
our stream procedures to be higher order. Take a look at
filter_stream
:
def filter_stream(filter_func, stream):
def make_filtered_rest():
return filter_stream(filter_func, stream.rest)
if Stream.empty:
return stream
elif filter_func(stream.first):
return Stream(stream.first, make_filtered_rest)
else:
return filter_stream(filter_funct, stream.rest)
You can see how this function might be useful. Notice how the Stream we
create has as its compute_rest
function a procedure that promises
to filter out the rest of the Stream when asked. So at any one point,
the entire stream has not been filtered. Instead, only the part of the
stream that has been referenced has been filtered, but the rest will be
filtered when asked. We can model other higher order Stream procedures
after this one, and we can combine our higher order Stream procedures
to do incredible things!
In a similar model to filter_stream
, let's recreate the
procedure stream_map
from lecture, that given a stream stream
and
a one-argument function func
, returns a new stream that is the result of
applying func
on every element in stream
.
def stream_map(func, stream):
What does the following Stream output? Try writing out the first few values of the stream to see the pattern.
def my_stream():
def compute_rest():
return add_streams(map_stream(double,
my_stream()),
my_stream())
return Stream(1, compute_rest)
Define a function interleave
, which takes in two streams:
a1, a2, a3, ...
b1, b2, b3, ...
and returns the new stream
a1, b1, a2, b2, a3, b3, ...
If either of the inputs is finite, the output stream should be finite as well, terminating just at the point where it would be impossible to go on. If both of the inputs are infinite, the output stream should be infinite as well.