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.
 类似资料: