Lab 6: Mutability

Due by 11:59pm on Friday, October 11.

Starter Files

Download lab06.zip.

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

Mutability

Consult the drop-down if you need a refresher on mutability. It's okay to skip directly to the questions and refer back here should you get stuck.

Some objects in Python, such as lists and dictionaries, are mutable, meaning that their contents or state can be changed. Other objects, such as numeric types, tuples, and strings, are immutable, meaning they cannot be changed once they are created.

The two most common mutation operations for lists are item assignment and the append method.

>>> s = [1, 3, 4]
>>> t = s  # A second name for the same list
>>> t[0] = 2  # this changes the first element of the list to 2, affecting both s and t
>>> s
[2, 3, 4]
>>> s.append(5)  # this adds 5 to the end of the list, affecting both s and t
>>> t
[2, 3, 4, 5]

There are many other list mutation methods:

  • append(elem): Add elem to the end of the list. Return None.
  • extend(s): Add all elements of iterable s to the end of the list. Return None.
  • insert(i, elem): Insert elem at index i. If i is greater than or equal to the length of the list, then elem is inserted at the end. This does not replace any existing elements, but only adds the new element elem. Return None.
  • remove(elem): Remove the first occurrence of elem in list. Return None. Errors if elem is not in the list.
  • pop(i): Remove and return the element at index i.
  • pop(): Remove and return the last element.

Dictionaries also have item assignment (often used) and pop (rarely used).

>>> d = {2: 3, 4: 16}
>>> d[2] = 4
>>> d[3] = 9
>>> d
{2: 4, 4: 16, 3: 9}
>>> d.pop(4)
16
>>> d
{2: 4, 3: 9}

Important: For all WWPD questions, type Function if you believe the answer is <function...>, Error if it errors, and Nothing if nothing is displayed.

Q1: WWPD: List-Mutation

Important: For all WWPD questions, type Function if you believe the answer is <function...>, Error if it errors, and Nothing if nothing is displayed.

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q list-mutation -u

>>> s = [6, 7, 8]
>>> print(s.append(6))

______
None

>>> s

______
[6, 7, 8, 6]

>>> s.insert(0, 9)
>>> s

______
[9, 6, 7, 8, 6]

>>> x = s.pop(1)
>>> s

______
[9, 7, 8, 6]

>>> s.remove(x)
>>> s

______
[9, 7, 8]

>>> a, b = s, s[:]
>>> a is s

______
True

>>> b == s

______
True

>>> b is s

______
False

>>> a.pop()

______
8

>>> a + b

______
[9, 7, 9, 7, 8]

>>> s = [3]
>>> s.extend([4, 5])
>>> s

______
[3, 4, 5]

>>> a

______
[9, 7]

>>> s.extend([s.append(9), s.append(10)])
>>> s

______
[3, 4, 5, 9, 10, None, None]

Q2: Insert Items

Write a function that takes in a list s, a value before, and a value after. It modified s in place by inserting after just after each value equal to before in s. It returns s.

Important: No new lists should be created.

Note: If the values passed into before and after are equal, make sure you're not creating an infinitely long list while iterating through it. If you find that your code is taking more than a few seconds to run, the function may be in an infinite loop of inserting new values.

def insert_items(s, before, after):
    """Insert after into s after each occurrence of before and then return s.

    >>> test_s = [1, 5, 8, 5, 2, 3]
    >>> new_s = insert_items(test_s, 5, 7)
    >>> new_s
    [1, 5, 7, 8, 5, 7, 2, 3]
    >>> test_s
    [1, 5, 7, 8, 5, 7, 2, 3]
    >>> new_s is test_s
    True
    >>> double_s = [1, 2, 1, 2, 3, 3]
    >>> double_s = insert_items(double_s, 3, 4)
    >>> double_s
    [1, 2, 1, 2, 3, 4, 3, 4]
    >>> large_s = [1, 4, 8]
    >>> large_s2 = insert_items(large_s, 4, 4)
    >>> large_s2
    [1, 4, 4, 8]
    >>> large_s3 = insert_items(large_s2, 4, 6)
    >>> large_s3
    [1, 4, 6, 4, 6, 8]
    >>> large_s3 is large_s
    True
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q insert_items

Q3: Group By

Write a function that takes a list s and a function fn, and returns a dictionary that groups the elements of s based on the result of applying fn.

  • The dictionary should have one key for each unique result of applying fn to elements of s.
  • The value for each key should be a list of all elements in s that, when passed to fn, produce that key value.

In other words, for each element e in s, determine fn(e) and add e to the list corresponding to fn(e) in the dictionary.

def group_by(s, fn):
    """Return a dictionary of lists that together contain the elements of s.
    The key for each list is the value that fn returns when called on any of the
    values of that list.

    >>> group_by([12, 23, 14, 45], lambda p: p // 10)
    {1: [12, 14], 2: [23], 4: [45]}
    >>> group_by(range(-3, 4), lambda x: x * x)
    {9: [-3, 3], 4: [-2, 2], 1: [-1, 1], 0: [0]}
    """
    grouped = {}
    for ____ in ____:
        key = ____
        if key in grouped:
            ____
        else:
            grouped[key] = ____
    return grouped

Use Ok to test your code:

python3 ok -q group_by

Q4: Partial Reverse

Partially reversing the list [1, 2, 3, 4, 5] starting from index 2 until the end of the list will give [1, 2, 5, 4, 3].

Implement the function partial_reverse which reverses a list starting from index start until the end of the list. This reversal should be in-place, meaning that the original list is modified. Do not create a new list inside your function, even if you do not return it. The partial_reverse function returns None.

Hint: You can swap elements at index i and j in list s with multiple assignment: s[i], s[j] = s[j], s[i]

def partial_reverse(s, start):
    """Reverse part of a list in-place, starting with start up to the end of
    the list.

    >>> a = [1, 2, 3, 4, 5, 6, 7]
    >>> partial_reverse(a, 2)
    >>> a
    [1, 2, 7, 6, 5, 4, 3]
    >>> partial_reverse(a, 5)
    >>> a
    [1, 2, 7, 6, 5, 3, 4]
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q partial_reverse

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 Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.