CS61A(15): Iterators

Posted on | In |

This is the lecture note of CS61A - Lecture 15.

Iterators

Iterators are common interface in many programming languages, and they're used in Python as a way to access the elements of lots of different containers. A container can provide an iterator which in turn provides access to its elements in order.

Two built-in functions:

  • iter(iterable): Return an iterator over the elements of an iterable value
  • next(iterator): Return the next element in an iterator
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
>>> s = [[1, 2], 3, 4, 5]
>>> t = iter(s)
>>> t
<list_iterator object at 0x000002050E878B80>
>>>
>>>
>>> next(t)
[1, 2]
>>> next(t)
3
>>> list(t)
[4, 5]
>>>
>>>
>>> next(t)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Dictionary Iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# dictionary iteration demo

>>> d = {'one': 1, 'two': 2}
>>> k = iter(d)
>>> next(k)
'one'
>>> d['zero'] = 0   # change the size of dictionary, then the original iterator becomes invalid
>>> next(k)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: dictionary changed size during iteration
>>> k = iter(d)
>>> next(k)
'one'
>>> next(k)
'two'
>>> d['one'] = 8  # it's ok if just change the value instead of changing size
>>> next(k)
'zero'

For Statements

For statements iterate over iterable values. They can also iterate over iterators themselves.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
>>> r = range(3, 6)
>>> for i in r:         # iterate over iterable values
...   print(i)
...
3
4
5

>>> ri = iter(r)
>>> ri
<range_iterator object at 0x0000021880BFD9B0>
>>> next(ri)
3
>>> for i in ri:        # iterate over iterators
...   print(i)
...
4
5
>>> for i in ri:        # cannot use iterator again
...    print(i)
...
>>>

Built-in Iterator Functions

  • lazy computation: means the result is only computed when it has been requested

Map Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
>>> bcd = ['b', 'c', 'd']
>>> [x.upper() for x in bcd]
['B', 'C', 'D']
>>> bcd
['b', 'c', 'd']
>>>
>>>
>>> m = map(lambda x: x.upper(), bcd)   # return an iterator
>>> m
<map object at 0x000001C6BE11A630>      # an iterator object
>>> next(m)
'B'
>>> next(m)
'C'
>>> next(m)
'D'
>>> next(m)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Filter Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
>>> def double(x):
...   print('**', x, '=>', 2*x, '**')
...   return 2 * x
...
>>> m = map(double, range(3, 7))
>>>
>>>
>>> f = lambda y: y >= 10
>>> t = filter(f, m)        # pass into another sequence processing function
>>> t
<filter object at 0x000001C6BDE8A2B0>
>>>
>>> next(t)
** 3 => 6 **
** 4 => 8 **
** 5 => 10 **
10
>>> list(t)
** 6 => 12 **
[12]
>>>
>>>
>>> list(filter(f, map(double, range(3, 7))))
** 3 => 6 **
** 4 => 8 **
** 5 => 10 **
** 6 => 12 **
[10, 12]

Zip Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# example: zip

>>> d = {'a': 1, 'b': 2}
>>> d
{'a': 1, 'b': 2}
>>> items = zip(d.keys(), d.values())  # return an iterator
>>> next(items) 
('a', 1)
>>> next(items)
('b', 2)
>>> next(items)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# demo: palindrome

def palindrome(s):
    """Return whether s is the same sequence backward and forward.

    >>> palindrome([3, 1, 4, 1, 5])
    False
    >>> palindrome([3, 1, 4, 1, 3])
    True
    >>> palindrome('seveneves')
    True
    >>> palindrome('seven eves')
    False
    """
    # return s == reversed(s)  # This version doesn't work, since list != iterator
    return all([a == b for a, b in zip(s, reversed(s))])
    # or: return list(s) == list(reversed(s))

Generators

A gernerator is a special kind of iterator. The special thing is that a generator is returned from a generator function.

A generator function is a function that yields values instead of returning values.

  • normal function returns once;
  • generator function yield multiple times;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
>>> def plus_minus(x):
...   yield x
...   yield -x
...
>>> t = plus_minus(3)
>>> t
<generator object plus_minus at 0x000002050E807C10>
>>> next(t)
3
>>> next(t)
-3
>>> next(t)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Generator functions can return generators. But they often process iterators in the course of their execution.

Let's finish today's lecture with the following examples.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def prefixes(s):
    """
    >>> list(prefixes("both"))
    ['b', 'bo', 'bot', 'both']
    """
    if s:
        # for x in prefixes(s[:-1]):
        #     yield x
        yield from prefixes(s[:-1])     # shortcut above the two lines
        yield s

def substrings(s):
    """
    >>> list(substrings('tops'))
    ['t', 'to', 'top', 'tops', 'o', 'op', 'ops', 'p', 'ps', 's']
    """
    if s:
        yield from prefixes(s)
        yield from substrings(s[1:])