Lab 4: Python Lists, Sequences

lab04.zip

Due by 11:59pm on Thursday, July 6.

Starter Files

Download lab04.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the Ok autograder.

Topics

Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.

Lists

A list is a data structure that can store multiple elements. Each element can be of any type, even a list itself. We write a list as a comma-separated list of expressions in square brackets:

>>> list_of_ints = [1, 2, 3, 4]
>>> list_of_bools = [True, True, False, False]
>>> nested_lists = [1, [2, 3], [4, [5]]]

Each element in the list has an index, with the index of the first element starting at 0. We say that lists are therefore "zero-indexed."

With list indexing, we can specify the index of the element we want to retrieve. A negative index represents starting from the end of the list, so the negative index -i is equivalent to the positive index len(lst)-i.

>>> lst = [6, 5, 4, 3, 2, 1, 0]
>>> lst[0]
6
>>> lst[3]
3
>>> lst[-1] # Same as lst[6]
0

List Slicing

To create a copy of part or all of a list, we can use list slicing. The syntax to slice a list lst is: lst[<start index>:<end index>:<step size>].

This expression evaluates to a new list containing the elements of lst:

Starting at and including the element at <start index>.
Up to but not including the element at <end index>.
With <step size> as the difference between indices of elements to include.

If the start, end, or step size are not explicitly specified, Python has default values for them. A negative step size indicates that we are stepping backwards through a list when including elements.

>>> lst = [6, 5, 4, 3, 2, 1, 0]
>>> lst[:3]     # Start index defaults to 0
[6, 5, 4]
>>> lst[3:]     # End index defaults to len(lst)
[3, 2, 1, 0]
>>> lst[:]      # Creates a copy of the list
[6, 5, 4, 3, 2, 1, 0]
>>> lst[:] == lst
True
>>> lst[:] is lst
False
>>> lst[::-1]   # Make a reversed copy of the entire list
[0, 1, 2, 3, 4, 5, 6]
>>> lst[::2]    # Skip every other; step size defaults to 1 otherwise
[6, 4, 2, 0]

List Comprehensions

List comprehensions are a compact and powerful way of creating new lists out of sequences. The general syntax for a list comprehension is the following:

[<expression> for <element> in <sequence> if <conditional>]

where the if <conditional> section is optional.

The syntax is designed to read like English: "Compute the expression for each element in the sequence (if the conditional is true for that element)."

>>> [i**2 for i in [1, 2, 3, 4] if i % 2 == 0]
[4, 16]

This list comprehension will:

Compute the expression i**2
For each element i in the sequence [1, 2, 3, 4]
Where i % 2 == 0 (i is an even number),

and then put the resulting values of the expressions into a new list.

In other words, this list comprehension will create a new list that contains the square of every even element of the original list [1, 2, 3, 4].

We can also rewrite a list comprehension as an equivalent for statement, such as for the example above:

>>> lst = []
>>> for i in [1, 2, 3, 4]:
...     if i % 2 == 0:
...         lst = lst + [i**2]
>>> lst
[4, 16]

Sequences

Sequences are ordered collections of values that support element-selection and have length. We've worked with lists, but other Python types are also sequences, including strings.

Let us go through an example of some actions we can do with strings.

>>> x = 'Hello there Oski!'
>>> x
'Hello there Oski!'
>>> len(x)
17
>>> x[6:]
'there Oski!'
>>> x[::-1]
'!iksO ereht olleH'

Since strings are sequences, we can do with strings many of the same things that we can do to lists. We can even loop through a string just like we can with a list:

>>> x = 'I am not Oski.'
>>> vowel_count = 0
>>> for i in range(len(x)):
...     if x[i] in 'aeiou':
...         vowel_count += 1
>>> vowel_count
5

Required Questions

Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

YouTube link

Lists

Q1: WWPD: Lists

Use Ok to test your knowledge with the following "What Would Python Display?" questions:
python3 ok -q lists-wwpd -u

Predict what Python will display when you type the following into the interpreter. Then try it to check your answers.

>>> s = [7//3, 5, [4, 0, 1], 2]
>>> s[0]
______
2
>>> s[2]
______
[4, 0, 1]
>>> s[-1]
______
2
>>> len(s)
______
4
>>> 4 in s
______
False
>>> 4 in s[2]
______
True
>>> s + [3 + 2, 9]
______
[2, 5, [4, 0, 1], 2, 5, 9]
>>> s[2] * 2
______
[4, 0, 1, 4, 0, 1]
>>> x = [1, 2, 3, 4]
>>> x[1:3]
______
[2, 3]
>>> x[:2]
______
[1, 2]
>>> x[1:]
______
[2, 3, 4]
>>> x[-2:3]
______
[3]
>>> x[-2:4]
______
[3, 4]
>>> x[0:4:2]
______
[1, 3]
>>> x[::-1]
______
[4, 3, 2, 1]

Q2: Flatten

Write a function flatten that takes a list and returns a "flattened" version of it. The input list could be a deep list, meaning that there could be a multiple layers of nesting within the list.

Make sure your solution does not mutate the input list.

For example, one use case of flatten could be the following:

>>> lst = [1, [[2], 3], 4, [5, 6]]
>>> flatten(lst)
[1, 2, 3, 4, 5, 6]

Hint: you can check if something is a list by using the built-in type function. For example:
>>> type(3) == list
False
>>> type([1, 2, 3]) == list
True

def flatten(s):
    """Returns a flattened version of list s.

    >>> flatten([1, 2, 3])     # normal list
    [1, 2, 3]
    >>> x = [1, [2, 3], 4]     # deep list
    >>> flatten(x)
    [1, 2, 3, 4]
    >>> x # Ensure x is not mutated
    [1, [2, 3], 4]
    >>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
    >>> flatten(x)
    [1, 1, 1, 1, 1, 1]
    >>> x
    [[1, [1, 1]], 1, [1, 1]]
    >>> x = [[1, [2, 3], [4, [5, 6]]]]
    >>> flatten(x)
    [1, 2, 3, 4, 5, 6]
    >>> x
    [[1, [2, 3], [4, [5, 6]]]]
    >>> x = [[1, [1, [1, [1, 1, [1, 1, [1]]]], 1]]]
    >>> flatten(x)
    [1, 1, 1, 1, 1, 1, 1, 1, 1]
    >>> x
    [[1, [1, [1, [1, 1, [1, 1, [1]]]], 1]]]
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q flatten

Sequences

Many languages provide map, filter, reduce functions for sequences. Python also provides these functions (and we'll formally introduce them later on in the course), but to help you better understand how they work, you'll be implementing these functions in the following problems.

In Python, the map and filter built-ins have slightly different behavior than the my_map and my_filter functions we are defining here.

Q3: Map

my_map takes in a one argument function fn and a sequence seq and returns a list containing fn applied to each element in seq.

Use only a single line for the body of the function. (Hint: use a list comprehension.)

def my_map(fn, seq):
    """Applies fn onto each element in seq and returns a list.
    >>> my_map(lambda x: x*x, [1, 2, 3])
    [1, 4, 9]
    >>> my_map(lambda x: abs(x), [1, -1, 5, 3, 0])
    [1, 1, 5, 3, 0]
    >>> my_map(lambda x: print(x), ['cs61a', 'summer', '2023'])
    cs61a
    summer
    2023
    [None, None, None]
    """
    return ______

Use Ok to test your code:

python3 ok -q my_map

Use Ok to run the local syntax checker (which checks that you used only a single line for the body of the function):

python3 ok -q my_map_syntax_check

Q4: Filter

my_filter takes in a predicate function pred and a sequence seq and returns a list containing all elements in seq for which pred returns True. (A predicate function is a function that takes in an argument and returns either True or False.)

Use only a single line for the body of the function. (Hint: use a list comprehension.)

def my_filter(pred, seq):
    """Keeps elements in seq only if they satisfy pred.
    >>> my_filter(lambda x: x % 2 == 0, [1, 2, 3, 4])  # new list has only even-valued elements
    [2, 4]
    >>> my_filter(lambda x: (x + 5) % 3 == 0, [1, 2, 3, 4, 5])
    [1, 4]
    >>> my_filter(lambda x: print(x), [1, 2, 3, 4, 5])
    1
    2
    3
    4
    5
    []
    >>> my_filter(lambda x: max(5, x) == 5, [1, 2, 3, 4, 5, 6, 7])
    [1, 2, 3, 4, 5]
    """
    return ______

Use Ok to test your code:

python3 ok -q my_filter

Use Ok to run the local syntax checker (which checks that you used only a single line for the body of the function):

python3 ok -q my_filter_syntax_check

Q5: Reduce

my_reduce takes in a two argument function combiner and a non-empty sequence seq and combines the elements in seq into one value using combiner.

def my_reduce(combiner, seq):
    """Combines elements in seq using combiner.
    seq will have at least one element.
    >>> my_reduce(lambda x, y: x + y, [1, 2, 3, 4])  # 1 + 2 + 3 + 4
    10
    >>> my_reduce(lambda x, y: x * y, [1, 2, 3, 4])  # 1 * 2 * 3 * 4
    24
    >>> my_reduce(lambda x, y: x * y, [4])
    4
    >>> my_reduce(lambda x, y: x + 2 * y, [1, 2, 3]) # (1 + 2 * 2) + 2 * 3
    11
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q my_reduce

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit

Make sure to submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. For a refresher on how to do this, refer to Lab 00.

Optional Questions

These questions are optional, but you must complete them in order to be checked off before the end of the lab period. They are also useful practice!

Lists

Q6: Merge

Write a function merge that takes 2 sorted lists lst1 and lst2, and returns a new list that contains all the elements in the two lists in sorted order.

Note: Try to solve this question using recursion instead of iteration.

def merge(lst1, lst2):
    """Merges two sorted lists.

    >>> s1 = [1, 3, 5]
    >>> s2 = [2, 4, 6]
    >>> merge(s1, s2)
    [1, 2, 3, 4, 5, 6]
    >>> s1
    [1, 3, 5]
    >>> s2
    [2, 4, 6]
    >>> merge([], [2, 4, 6])
    [2, 4, 6]
    >>> merge([1, 2, 3], [])
    [1, 2, 3]
    >>> merge([5, 7], [2, 4, 6])
    [2, 4, 5, 6, 7]
    >>> merge([2, 3, 4], [2, 4, 6])
    [2, 2, 3, 4, 4, 6]
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q merge

Sequences

Q7: Count Palindromes

The Python library defines filter, map, and reduce, which operate on Python sequences. Devise a function that counts the number of palindromic words (those that read the same backwards as forwards) in a tuple of words using only lambda, basic operations on strings, the tuple constructor, conditional expressions, and the functions filter, map, and reduce. Specifically, do not use recursion or any kind of loop:

def count_palindromes(L):
    """The number of palindromic words in the sequence of strings
    L (ignoring case).

    >>> count_palindromes(("Acme", "Madam", "Pivot", "Pip"))
    2
    """
    return ______

Hint: The easiest way to get the reversed version of a string s is to use the Python slicing notation trick s[::-1]. Also, the function lower, when called on strings, converts all of the characters in the string to lowercase. For instance, if the variable s contains the string "PyThoN", the expression s.lower() evaluates to "python".

Use Ok to test your code:

python3 ok -q count_palindromes