CS61A(10): Containers

Posted on | In |

This is the lecture note of CS61A - Lecture 10.

Lists

List is a built-in data type in Python.

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
# Lists

>>> odds = [41, 43, 47, 49]
[41, 43, 47, 49]
>>> len(odds)
4
>>> odds[1]
43
>>> odds[0] - odds[3] + len(odds)
-4
>>> odds[odds[3]-odds[2]]
47

>>> from operator import getitem
>>> getitem(odds, 2)
47

>>> [2, 7] + odds * 2   # NOTICE THIS OPERATION
[2, 7, 41, 43, 47, 49, 41, 43, 47, 49]

>>> pairs = [[10, 20], 30]
>>> pairs[0]
[10, 20]
>>> pairs[0][0]
10

Lists are containers which can contain other values, and their values can represent collections of other values.

You can use built-in operators in to test whether an element appears in a compound value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Containers

>>> digits = [1, 8, 2, 8]
>>> 1 in digits
True
>>> 5 in digits
False
>>> '1' not in digits
True
>>> [1, 8] in digits
False
>>> [1, 2] in [[1, 2], 3]
True
>>> [1, 2] in [[[1, 2]], 3, 4]
False

For Statements

We've written lots of code using while loops. Now, it's time to turn to an alternative way of iteration structure —— for loops.

The for statement is a way of iterating over sequences.

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
29
30
# while statement
def count_while(s, value):
    """Count the number of occurrences of value in sequence s.

    >>> digits = [1, 8, 2, 8]
    >>> count_while(digits, 8)
    2
    """
    total, index = 0, 0
    while index < len(s):
        element = s[index]      # element at "index" postion
        if element == value:
            total = total + 1
        index = index + 1
    return total


# for statement
def count_for(s, value):
    """Count the number of occurrences of value in sequence s.

    >>> digits = [1, 8, 2, 8]
    >>> count_for(digits, 8)
    2
    """
    total = 0
    for element in s:   # s is iterable
        if element == value:
            total = total + 1
    return total

Sequence Unpacking

There is a cool feature in Python's for statement: sequence unpacking.

Here is an example:

1
2
3
4
5
6
7
8
9
10
11
12
def count_same(pairs):
    """Return how many pairs have the same element repeated.

    >>> pairs = [[1, 2], [2, 2], [2, 3], [4, 4]]
    >>> count_same(pairs)
    2
    """
    same_count = 0
    for x, y in pairs:
        if x == y:
            same_count = same_count + 1
    return same_count

⚠️ Attention: This feature only works for a sequence of fixed-length sequences, such as sequence pairs.

Ranges

Range is another sequence type.

Let's see two examples of range usage.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Example 1

def sum_below(n):
    total = 0
    for i in range(n):
        total += i
    return total


# Example 2

def cheer():
    for _ in range(3):
        print('Go Bears!')

# Here, we use _ instead of x or i to hightlight the fact that we don't care what is it.

List Comprehensions

List comprehension is a powerful form of combination in the Python language.

1
2
3
4
5
6
7
# List comprehensions

>>> odds = [1, 3, 5, 7, 9]
>>> [x+1 for x in odds]
[2, 4, 6, 8, 10]
>>> [x for x in odds if 25 % x == 0]
[1, 5]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def divisors(n):
    """Return the integers that evenly divide n.

    >>> divisors(1)
    [1]
    >>> divisors(4)
    [1, 2]
    >>> divisors(12)
    [1, 2, 3, 4, 6]
    >>> [n for n in range(1, 1000) if sum(divisors(n)) == n]
    [1, 6, 28, 496]
    """
    return [1] + [x for x in range(2, n) if n % x == 0]

# list comprehension makes our code concisely !!!

Strings

For String, you can use either single quotation mark or double quotation mark. The only difference is that double quoted String can have multiple lines, while single quoted String can only have one line.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
>>> 'curry = lambda f: lambda x: lambda y: f(x, y)'
'curry = lambda f: lambda x: lambda y: f(x, y)'
>>> exec('curry = lambda f: lambda x: lambda y: f(x, y)')
>>> curry
<function <lambda> at 0x000001FF95D32EA0>

>>> exec('print("Hello World")')
Hello World

>>> city = 'Beijing'
>>> len(city)
7
>>> city[2]     # String can be indexed like List
'i'
>>> 'iji' in city
True
>>> 'B ' not in city
True

Slicing

Slicing is an operation that you can perform on sequences such as lists and ranges.

1
2
3
4
5
6
7
8
9
10
11
# examples of slicing

>>> odds = [3, 5, 7, 9, 11]
>>> [odds[i] for i in range(1, 3)]
[5, 7]
>>> odds[1: 3]
[5, 7]
>>> odds[: 3]
[3, 5, 7]
>>> odds[1:]
[5, 7, 9, 11]

Examples

  • Question 1: Recursive Sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def my_sum(L):
    """Return the sum of all numbers in list L, using recursion.

    >>> my_sum([2, 4, 1, 5])
    12
    """
    if len(L) == 0:
        return 0
    return L[0] + my_sum(L[1:])


# drill
# Write a recursive function that takes as input integer "n", and returns the sum
# of the first "n" integers, such as sum(5) returns 1 + 2 + 3 + 4 + 5 = 15

def sum(n):
    if n == 1:
        return 1
    return n + sum(n - 1)
  • Question 2: String Reversal
1
2
3
4
5
6
7
8
9
def reverse(str):
    """Reverse the given string recursively.

    >>> reverse("ward")
    draw
    """
    if len(str) == 0:
        return ''
    return reverse(str[1:]) + str[0]

Processing Container Values

1
2
3
4
5
6
7
8
9
10
11
12
13
# examples of sum

>>> sum([2, 3, 4])
9
>>> sum([2, 3, 4], 5)       # start=5
14

>>> sum([[2, 3], [4]], [])  # [] + [2, 3] + [4] ==> [2, 3, 4]
[2, 3, 4]
>>> sum([[2, 3], [4]])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'int' and 'list'
1
2
3
4
5
6
# examples of max

>>> max(range(5))
4
>>> max(range(10), lambda x: 7-(x-4)*(x-2))
3
1
2
3
4
5
6
# examples of all

>>> [x < 5 for x in range(5)]
[True, True, True, True, True]
>>> all([x < 5 for x in range(5)])
True