SICP-Notes-Lecture 11 Iterators & Generators

诸葛皓

2023-12-01

Lecture 11 Iterators & Generators

These are my notes for SICP(Structure and Interpretation of Computer Programs). Hope they’ll be of some help to you.

Iterators

Definitions

Lazy evalution - Delays evaluation of an expression until its value is needed
Iterable - An object capable of returning its members one at a time.
- Examples include all sequences(lists, strings, tuples) and some non-sequence types(dictionaries).
Iterator - An object that provides sequential access to values, one by one.
- All iterators are iterables. Not all iterables are iterators.
Metaphor: Iterables are books & Iterators are bookmarks.

How do we cerate iterators?

A container can provide an iterator that provides access to its elements in order.

iter(iterable): Return an iterator over the elements of an iterable value
- This method creates a bookmark from a book starting at the front.
next(iterator): Return the next element in an iterator
- Returns the current page and moves the bookmark to the next page.
- The iterator remembers where you left off. If the current page is the end of the book, error.

>>> s = [3, 4, 5] #the book
>>> t = iter(s) #create bookmark t
>>> next(t) #move bookmark t
3
>>> next(t) #move bookmark t
4
>>> u = iter(s) #create bookmark u
>>> next(u) #move bookmark u
3
>>> next(t) #move bookmerk t
5
>>> next(u) #move bookmark u
4

Dictionary Iteration

An iterable value is any value that can be passed to iter to produce an iterator.

An iterator is returned from iter and can be passed to next; all iterators are mutable.

Views of dictionary

A dictionary, its keys, its values, and its items are all iterable values

The order of items in a dictionary is the order in which they were added(Python3.6+)
Historically, items appeared in an arbitrary order(Python 3.5 and earlier)

For Statements

Iterator is also iterable, which can be used in for statements, but only once.

Built-In Iterator Functions

Many built-in Python sequence operations return iterators that compute results lasily
- map(func, iterable): Iterate over func(x) for x in iterable
- filter(func, iterable): Iterate over x in iterable if func(x)
- zip(first_iter, second_iter): Iterate over co_indexed(x, y) pairs
- reversed(sequence): Iterate over x in a sequence inreverse order
To view the contents of an iterator, place the resulting elements into a container
- list(iterable): Create a list containing all x in iterable
- tuple(iterable): Create a tuple containing all x in iterable
- sorted(iterable): Create a sorted list containing x in iterable

Exceptions / Errors

Today’s topic: handling errors

Sometimes, computer programs behave in non-standard ways

A function receives an argument value of an improper type
Some resource (such as a file) is not available
A network connection is lost in the middle of data transmission

Raise Exceptions

Exceptions are raised with a raise statement: raise <expression>

must be an Exception, which is created like so:

E.g. TypeError(‘Error message’)

TypeError - A function was passed the wrong number/type of argument
NameError - A name wasn’t found
KeyError - A key wasn’t found in a dictionary
RuntimeError - Catch-all for troubles during interpretation

Try statements

Try statements handle exceptions

try:
    <try suite>
except <exception class> as <name>:
    <except suit>

Execution rule

The is executed first
If, during the course of executing the , an exception is raised that is not handled otherwise, then the is executed with bound to the exeception.

>>>try:
... x = 1/0
... except ZeroDivisionError as e:
...	print('Except a', type(e))
...	x = 0
Except a <class ‘ZeroDivisionError’>
>>> x
0

Back to iterators - The for statement

When executing a for statement, iter returns an iterator and next provides each item:

>>> counts = [1, 2, 3]
>>> for item in counts:... 	print(item)
1
2
3

>>> counts = [1, 2, 3]
>>> items = iter(counts)
>>> try:
...   while True:
... 	item = next(items)
...	print(item)
... except StopIteration: #StopIteration is raised whenever next is called on an empty iterator
...		pass
1
2
3

The two code squares above are equivalent!

Generators

Definitions and rules

Some definitions:
- Generator: An iterator created automatically by calling a generator function.
- Generator function: A function that contains the keyword yield anywhere in the body.
When a generator function is called, it returns a generator instead of going into the body of the function. The only way to go into the body of a generator function is by calling next on the returned generator.
Yielding values are the same as returning values except yield remembers where it left off.

Generators and generator functions

>>> def plus_minus(x):
... 	yield x
... 	yield -x
...
>>> t = plus_minus(3)
>>> next(t)
3
>>> next(t)
-3
>>> t
<generator object plus_minus ...>

We are allowed to call next on generators because generators are a type of iterator.
Calling next on a generator goes into the function and evaluates to the first yield statement.
The next time we call next on that generator, it resumes where it left off(just like calling next on any iterator!)
Once the generator hits on a return statement, it raises a StopIteration.

Generators to Represent Infinite Sequences

Iterators are used to represent infinite sequences. In this course, when we ask you to write an iterator, we want you to write a generator.

>>> def naturals():
...		x = 0
...		while True:
...			yield x
...			x += 1

>>> nats = naturals()
>>> next(nats)
0
>>> next(nats)
1
>>> nats1, nats2 = naturals(), naturals()
>>> [next(nats1) * next(nats2) for _ in range(5)]
[0, 1, 4, 9, 16] # Squares the first 5 natural numbers

Generators can yield from iterators

A yield from statement yields all values from an iterable.

def a_then_b(a, b):
    for x in a:
        yield x
    for x in b:
        yield x

def a_then_b(a, b):
    yield from a
    yield from b

The above two code squares are equivalent.

More example:

def countdown(k):
    if k == 0:
        yield 'Blast off'
    else:
        yield k
        yield from countdown(k - 1)

Summary

Iterators (bookmarks) are used to iterate over iterables (books).
- We use the iter method to turn iterables into iterators and we use the next method to get the next element.
Exceptions can be raised and handled.
Generators are how we implement iterators in this course and use yield statements.
- We can use yield from to yield multiple values from an iterable.