- Submission
- Lists
- What would Python print?
- Question 1
- Question 2
- Question 3
- Question 4
- Question 5: *
- Question 6
- Question 7
- Question 8: *
- Sequences
- List Comprehensions

**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.

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

```
>>> x = [1, 2, 3]
>>> x[0]
______1
>>> x[3]
______IndexError
>>> x[-1]
______3
>>> x[-3]
______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]
______[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.

```
>>> 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]
```

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
"""
"*** YOUR CODE HERE ***"
return ______
return x[2][1]
def get_seven_b(x):
"""
>>> x = [[7]]
>>> get_seven_b(x)
7
"""
"*** YOUR CODE HERE ***"
return ______
return x[0][0]
def get_seven_c(x):
"""
>>> x = [1, [2, [3, [4, [5, [6, [7]]]]]]]
>>> get_seven_c(x)
7
"""
"*** YOUR CODE HERE ***"
return ______
return x[1][1][1][1][1][1][0]
```

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]
"""
"*** YOUR CODE HERE ***"
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]
"""
"*** YOUR CODE HERE ***"
if not lst:
return []
return reverse_recursive(lst[1:]) + [lst[0]]
```

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
"""
"*** YOUR CODE HERE ***"
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:])
```

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]
"""
"*** YOUR CODE HERE ***"
# 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
```

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]
"""
"*** YOUR CODE HERE ***"
# 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 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`

.

**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'
```

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!'`

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."

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]]
"""
"*** YOUR CODE HERE ***"
return [[x, fn(x)] for x in seq if lower <= fn(x) <= upper]
```

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]]
"""
"*** YOUR CODE HERE ***"
return [[x[i][j] + y[i][j] for j in range(len(x[0]))]
for i in range(len(x))]
```

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():
"*** YOUR CODE HERE ***"
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):
"*** YOUR CODE HERE ***"
deck = sorted(deck, key=lambda card: card[1])
return sorted(deck, key=lambda card: card[0])
```