# Lab 4: Lists

## Submission

This lab is due at 11:59pm on 10/01/2014.

Please start at the beginning of the lab and work your way through, working and talking over Python's behavior in the conceptual questions with your classmates nearby. These questions are designed to help you experiment with the concepts on the Python interpreter. They are good tests for your understanding.

When you are done with lab, submit Questions 6, 7, 11, and 13 provided in the starter file lab04.py to receive credit for this lab. Questions 5, 8, and 12 are marked with an asterisk and considered extra practice. They can be found in the lab04_extra.py file. It is recommended that you complete these problems on your own time.

By the end of this lab, you should have submitted the `lab04` assignment using the command `submit lab04`. You can check if we received your submission by running `glookup -t`. Click here to see more complete submission instructions.

## Lists

### What would Python print?

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

### Question 1

``````>>> x = [1, 2, 3]
>>> x[0]
______1
>>> x[3]
______IndexError
>>> x[-1]
______3
>>> x[-3]
______1``````

### Question 2

``````>>> 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]
______[1, 3]
>>> x[::-1]
______[4, 3, 2, 1]
>>> x[-1:0:-1]
______[4, 3, 2]``````

Note: As you may have noticed, Python has a convenient notation for slicing, or breaking up, a list. Specifically, we can write `[start:end:step]` to slice a list with three integers. `start` denotes the index for where to begin the slice, `end` denotes the index to stop the slice, and `step` denotes how many indicies 0 for the starting index, the length for the ending index, and 1 for the step size. Using negative indicies for `start` and `end` behaves in the same way as indexing into negative indicies, and using a negative `step` means to move backwards through the list. It is also important to note that slicing a list creates a new list, without modifying the original list.

### Question 3

``````>>> y = [1]
>>> len(y)
______1
>>> 1 in y
______True
>>> y + [2, 3]
______[1, 2, 3]
>>> [0] + y
______[0, 1]
>>> y * 3
______[1, 1, 1]
>>> z = [[1, 2], [3, 4, 5]]
>>> len(z)
______[2]``````

### Question 4

For each of the following, use element selection to get the number 7 from the particular list in the doctest. Don't worry about making this work for all lists.

``````def get_seven_a(x):
"""
>>> x = [1, 3, [5, 7], 9]
>>> get_seven_a(x)
7
"""
return ______
return x[2][1]
def get_seven_b(x):
"""
>>> x = [[7]]
>>> get_seven_b(x)
7
"""
return ______
return x[0][0]
def get_seven_c(x):
"""
>>> x = [1, [2, [3, [4, [5, [6, [7]]]]]]]
>>> get_seven_c(x)
7
"""
return ______
return x[1][1][1][1][1][1][0]``````

### Question 5: *

Write a function `reverse` that takes a list and returns the reverse. Write both an iterative and a recursive version. You may use slicing notation, but don't use `list[::-1]`.

``````def reverse_iter(lst):
"""Returns the reverse of the given list.

>>> reverse_iter([1, 2, 3, 4])
[4, 3, 2, 1]
"""
new, i = [], 0
while i < len(lst):
new = [lst[i]] + new
i += 1
return new
def reverse_recursive(lst):
"""Returns the reverse of the given list.

>>> reverse_recursive([1, 2, 3, 4])
[4, 3, 2, 1]
"""
if not lst:
return []
return reverse_recursive(lst[1:]) + [lst[0]]``````

### Question 6

A list that contains one or more lists as elements is called a deep list. For example, `[1, [2, 3], 4]` is a deep list.

Write a function `deep_len` that takes a list and returns its deep length. See the doctests for the function's behavior.

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 deep_len(lst):
"""Returns the deep length of the list.

>>> deep_len([1, 2, 3])     # normal list
3
>>> x = [1, [2, 3], 4]      # deep list
>>> deep_len(x)
4
>>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
>>> deep_len(x)
6
"""
if not lst:
return 0
elif type(lst[0]) == list:
return deep_len(lst[0]) + deep_len(lst[1:])
else:
return 1 + deep_len(lst[1:])``````

### Question 7

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.

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

>>> merge([1, 3, 5], [2, 4, 6])
[1, 2, 3, 4, 5, 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]
"""
# recursive
if not lst1 or not lst2:
return lst1 + lst2
elif lst1[0] < lst2[0]:
return [lst1[0]] + merge(lst1[1:], lst2)
else:
return [lst2[0]] + merge(lst1, lst2[1:])

# Iterative solution
def merge_iter(lst1, lst2):
"""Merges two sorted lists recursively.

>>> merge_iter([1, 3, 5], [2, 4, 6])
[1, 2, 3, 4, 5, 6]
>>> merge_iter([], [2, 4, 6])
[2, 4, 6]
>>> merge_iter([1, 2, 3], [])
[1, 2, 3]
>>> merge_iter([5, 7], [2, 4, 6])
[2, 4, 5, 6, 7]
"""
new = []
while lst1 and lst2:
if lst1[0] < lst2[0]:
new += [lst1[0]]
lst1 = lst1[1:]
else:
new += [lst2[0]]
lst2 = lst2[1:]
if lst1:
return new + lst1
else:
return new + lst2``````

### Question 8: *

Mergesort is a type of sorting algorithm. It follows a naturally recursive procedure:

• Break the input list into equally-sized halves
• Recursively sort both halves
• Merge the sorted halves.

Using your `merge` function from the previous question, implement `mergesort`.

Challenge: Implement mergesort itself iteratively, without using recursion.

``````def mergesort(seq):
"""Mergesort algorithm.

>>> mergesort([4, 2, 5, 2, 1])
[1, 2, 2, 4, 5]
>>> mergesort([])     # sorting an empty list
[]
>>> mergesort([1])   # sorting a one-element list
[1]
"""
# recursive solution
if len(seq) < 2:
return seq
mid = len(seq) // 2
return merge(mergesort(seq[:mid]), mergesort(seq[mid:]))

# Iterative solution
def mergesort_iter(seq):
"""Mergesort algorithm.

>>> mergesort_iter([4, 2, 5, 2, 1])
[1, 2, 2, 4, 5]
>>> mergesort_iter([])     # sorting an empty list
[]
>>> mergesort_iter([1])   # sorting a one-element list
[1]
"""
if not seq:
return []
queue = [[elem] for elem in seq]
while len(queue) > 1:
first, second = queue[0], queue[1]
queue = queue[2:] + [merge(first, second)]
return queue[0]``````

## Sequences

Sequences are ordered collections of values that support element-selection and have length. The most common sequence you've worked with are lists, but many other Python types are sequences as well, including strings.

In lecture, you learned about a few powerful higher-order functions that process sequences. Let's review them here:

• `apply_to_all(fn, seq)`: applies a function `fn` onto every element in the given sequence `seq`.
• `keep_if(cond, seq)`: keeps elements in the sequence `seq` only if those elements satisfy the condition function `cond` (that is, for an element `x`, keep it only if `cond(x)` is True).
• `reduce(combiner, seq, initial)`: combines all elements in the sequence `seq` with the `combiner` function (which must take two arguments), starting from the `initial` value.

Note: `apply_to_all` and `keep_if` will always return lists, no matter what kind of sequence we pass in.

We've provided the implementation for these functions in `lab04.py`.

### Question 9: What would Python print?

Note: First run `python3 -i lab04.py` to load the provided functions before trying the following questions.

``````>>> apply_to_all(lambda x: x**2, [1, 2, 3, 4])
______[1, 4, 9, 16]
>>> apply_to_all(lambda a: a, 'cs61a')
______['c', 's', '6', '1', 'a']
>>> keep_if(lambda x: x % 2 == 0, [1, 2, 3, 4])
______[2, 4]
>>> reduce(lambda a, b: a + b, [1, 2, 3, 4, 5], 0)
______15
>>> reduce(lambda a, b: b + a, 'hello world!', '')
______'!dlrow olleh'``````

### Question 10

Fill in the blanks for the following lines so that each expression evaluates to the expected output:

``````>>> apply_to_all(_______, [1, 3, -1, -4, 2])
[1, 1, -1, -1, 1]
>>> keep_if(______, [1, 7, 14, 21, 28, 35, 42])
[1, 14, 28, 42]
>>> reduce(_______, _______, '')
'olleh'
>>> reduce(______, apply_to_all(______, 'nnnnn'), __) + ' batman!'
'nanananana batman!'``````
• `apply_to_all(lambda x: x // abs(x), [1, 3, -1, -4, 2])`
• `keep_if(lambda x: x // 7 % 2 == 0, [1, 7, 14, 21, 28, 35, 42])`
• `reduce(lambda x, y: y + x, 'hello', '')`
• ```reduce(lambda x, y: x + y, apply_to_all(lambda s: s + 'a', 'nnnnn'), '') + ' batman!'```

## List Comprehensions

Our functions `apply_to_all` and `keep_if` are implemented using list comprehensions, a compact and powerful way of creating new lists out of sequences. Let's work with them directly:

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

is equivalent to

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

The general syntax for a list comprehension is

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

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

### Question 11

Implement a function `coords`, which takes a function, a sequence, and an upper and lower bound on output of the function. `coords` then returns a list of x, y coordinate pairs (lists) such that:

• Each pair contains [x, fn(x)]
• The x coordinates are the elements in the sequence
• Only pairs whose y coordinate is within the upper and lower bounds are included

See the doctest if you are still confused.

One other thing: your answer can only be one line long. You should make use of list comprehensions!

``````def coords(fn, seq, lower, upper):
"""
>>> seq = [-4, -2, 0, 1, 3]
>>> fn = lambda x: x**2
>>> coords(fn, seq, 1, 9)
[[-2, 4], [1, 1], [3, 9]]
"""
return [[x, fn(x)] for x in seq if lower <= fn(x) <= upper]``````

### Question 12: *

To practice, write a function that adds two matrices together using list comprehensions. The function should take in two 2D lists of the same dimensions. Try to implement this in one line!

``````def add_matrices(x, y):
"""
>>> add_matrices([[1, 3], [2, 0]], [[-3, 0], [1, 2]])
[[-2, 3], [3, 2]]
"""
return [[x[i][j] + y[i][j] for j in range(len(x[0]))]
for i in range(len(x))]``````

### Question 13

Now write a list comprehension that will create a deck of cards. Each element in the list will be a card, which is represented by a list containing the suit as a string and the value as an int.

``````def deck():
return [[suit, value]
for suit in ["spades", "clubs", "diamonds", "hearts"]
for value in range(1, 14)]``````

Python also includes a powerful `sorted` function which returns a sorted version of a list. It can also take a `key` function that tells `sorted` how to actually sort the objects. For more information, look at Python's documentation for the sorted method. Note that `sorted` is stable, meaning if two values are equal according to the `key` function, their relative positions will stay the same after sorting. Now, use the `sorted` function to write a function that takes in a shuffled deck and returns a sorted deck. It should sort cards of the same suit together, and then sort each card in each suit in increasing value.

``````def sort_deck(deck):