# Lab 4: Data Abstractions and Lists

*Due at 11:59pm on 07/05/2017.*

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

## Submission

By the end of this lab, you should have submitted the lab with
`python3 ok --submit`

. You may submit more than once before the
deadline; only the final submission will be graded.

- To receive credit for this lab, you must complete Questions 1-6 in lab04.py and submit through OK.
- Questions 7-9 are
*extra practice*. It can be found in the lab04_extra.py file. It is recommended that you complete this problem on your own time.

## Lists Warm-up!

### Question 1: List Indexing

In each of following, what does the list indexing look like to get the number 7? Ex. `x = [7]`

, answer would be `x[0]`

. You can use the interpreter or Python tutor to experiment with your answers.

Use OK to test your knowledge with the following "List Indexing" questions:

`python3 ok -q indexing -u`

```
>>> x = [1, 3, [5, 7], 9]
______x[2][1]
>>> x = [[7]]
______x[0][0]
>>> x = [1, [2, [3, [4, [5, [6, [7]]]]]]]
______x[1][1][1][1][1][1][0]
```

Answer the following to solidify your understanding of list indexing.

```
>>> lst = [3, 2, 7, [84, 83, 82]]
>>> lst[4]
______Error
>>> lst = [3, 2, 7, [84, 83, 82]] # Write the code that indexes into lst to output the 82
______lst[3][2]
>>> lst[3][0]
______84
```

### Question 2: If This Not That

Define `if_this_not_that`

, which takes a list of integers `i_list`

, and an
integer `this`

, and for each element in `i_list`

if the element is larger than
`this`

then print the element, otherwise print `that`

.

```
def if_this_not_that(i_list, this):
"""Define a function which takes a list of integers `i_list` and an integer
`this`. For each element in `i_list`, print the element if it is larger
than `this`; otherwise, print the word "that".
>>> original_list = [1, 2, 3, 4, 5]
>>> if_this_not_that(original_list, 3)
that
that
that
4
5
"""
"*** YOUR CODE HERE ***"
for elem in i_list:
if elem <= this:
print("that")
else:
print(elem)
# List comprehension version
def if_this_not_that(i_list, this):
[print(i) if i > this else print('that') for i in i_list]
```

Use OK to test your code:

`python3 ok -q if_this_not_that`

## List Comprehension

List comprehensions are 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."

Note: The`if`

clause in a list comprehension is optional.

### Question 3: WWPD: Lists?

What would Python display? Try to figure it out before you type it into the interpreter!

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

`python3 ok -q lists -u`

```
>>> [x*x for x in range(5)]
______[0, 1, 4, 9, 16]
>>> [n for n in range(10) if n % 2 == 0]
______[0, 2, 4, 6, 8]
>>> ones = [1 for i in ["hi", "bye", "you"]]
>>> ones + [str(i) for i in [6, 3, 8, 4]]
______[1, 1, 1, '6', '3', '8', '4']
>>> [i+5 for i in [n for n in range(1,4)]]
______[6, 7, 8]
```

```
>>> [i**2 for i in range(10) if i < 3]
______[0, 1, 4]
>>> lst = ['hi' for i in [1, 2, 3]]
>>> print(lst)
______['hi', 'hi', 'hi']
>>> lst + [i for i in ['1', '2', '3']]
______['hi', 'hi', 'hi', '1', '2', '3']
```

### Question 4: Coordinates

Implement a function `coords`

that takes a function `fn`

, a sequence `seq`

,
and a `lower`

and `upper`

bound on the output of the function. `coords`

then
returns a list of coordinate pairs (lists) such that:

- Each (x, y) pair is represented as
`[x, fn(x)]`

- The x-coordinates are elements in the sequence
- The result contains only pairs whose y-coordinate is within the upper and lower bounds (inclusive)

See the doctest for examples.

Note: your answer can only beone 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 ______
return [[x, fn(x)] for x in seq if lower <= fn(x) <= upper]
```

Use OK to test your code:

`python3 ok -q coords`

## Data Abstraction

Data abstraction is a powerful concept in computer science that
allows programmers to treat code as objects --- for example,
car objects, chair objects, people objects, etc. That way,
programmers don't have to worry about *how* code is
implemented --- they just have to know *what* it does.

Data abstraction mimics how we think about the world. When you want to drive a car, you don't need to know how the engine was built or what kind of material the tires are made of. You just have to know how to turn the wheel and press the gas pedal.

An abstract data type consists of two types of functions:

- Constructors: functions that build the abstract data type.
- Selectors: functions that retrieve information from the data type.

Say we have an abstract data type called `city`

.
This `city`

object will hold the `city`

's name, and
its latitude and longitude. To create a `city`

object,
you'd use a constructor like

`city = make_city(name, lat, lon)`

To extract the information of a `city`

object, you would use the selectors like

```
get_name(city)
get_lat(city)
get_lon(city)
```

Here is how we would use the `make_city`

constructor to create a city object to represent Berkeley
and the selectors to access its information.

```
>>> berkeley = make_city('Berkeley', 122, 37)
>>> get_name(berkeley)
'Berkeley'
>>> get_lat(berkeley)
122
>>> get_lon(berkeley)
37
```

Notice that we don't need to know how these functions were implemented. We are assuming that someone else has defined them for us.

It's okay if the end user doesn't know how functions were implemented. However, the functions still have to be defined by someone.

### Question 5: Distance

We will now use those selectors to write `distance`

, which computes the
distance between two city objects. Recall that the distance between two
coordinate pairs, `(x1, y1)`

and `(x2, y2)`

can be found by calculating
the `sqrt`

of `(x1 - x2)**2 + (y1 - y2)**2`

. We have already imported
`sqrt`

for your convenience, so use that and the appropriate selectors
to fill in the function.

```
from math import sqrt
def distance(city1, city2):
"""
>>> city1 = make_city('city1', 0, 1)
>>> city2 = make_city('city2', 0, 2)
>>> distance(city1, city2)
1.0
>>> city3 = make_city('city3', 6.5, 12)
>>> city4 = make_city('city4', 2.5, 15)
>>> distance(city3, city4)
5.0
"""
"*** YOUR CODE HERE ***"
lat_1, lon_1 = get_lat(city1), get_lon(city1)
lat_2, lon_2 = get_lat(city2), get_lon(city2)
return sqrt((lat_1 - lat_2)**2 + (lon_1 - lon_2)**2)
```

Use OK to test your code:

`python3 ok -q distance`

### Question 6: Closer city

Implement `closer_city`

, a function that takes a latitude,
longitude, and two cities, and returns the name of the city that is
closer to the provided latitude and longitude.

You may only use selectors and constructors (introduced above) for
this question. You should also use the `distance`

function
defined above. All of these functions can be found in lab file, if you
are curious how they are implemented. However, the point of data abstraction,
as we've said, is that we do not need to know how an abstract data type is
implemented, but rather just how we can interact with and use the data type.

```
def closer_city(lat, lon, city1, city2):
"""
Returns the name of either city1 or city2, whichever is closest to
coordinate (lat, lon).
>>> berkeley = make_city('Berkeley', 37.87, 112.26)
>>> stanford = make_city('Stanford', 34.05, 118.25)
>>> closer_city(38.33, 121.44, berkeley, stanford)
'Stanford'
>>> bucharest = make_city('Bucharest', 44.43, 26.10)
>>> vienna = make_city('Vienna', 48.20, 16.37)
>>> closer_city(41.29, 174.78, bucharest, vienna)
'Bucharest'
"""
"*** YOUR CODE HERE ***"
new_city = make_city('arb', lat, lon)
dist1 = distance(city1, new_city)
dist2 = distance(city2, new_city)
if dist1 < dist2:
return get_name(city1)
return get_name(city2)
```

Use OK to test your code:

`python3 ok -q closer_city`

## Extra List Questions

### Question 7: Deep Length

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.

A deep list of integers is a list containing either integers or deep lists.
Implement `deep_len`

, which takes in a deep list of integers `lst`

. It returns
the number of integers that appear anywhere within `lst`

.

*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
>>> x = []
>>> for i in range(100):
... x = [x] + [i] # very deep list
...
>>> deep_len(x)
100
"""
"*** YOUR CODE HERE ***"
if not isinstance(lst, list):
return 1
else:
return sum([deep_len(e) for e in lst])
```

Use OK to test your code:

`python3 ok -q deep_len`

### Question 8: Riffle Shuffle

The familiar riffle shuffle of a deck of cards (or in our case, of a sequence of things) results in a new configuration of cards in which the original top card is followed by the original middle card, then by the original second card, then the card after the middle, and so forth. Assuming the deck (sequence) contains an even number of cards, write a list comprehension that produces the shuffled sequence.

*Hint:* To write this as a single comprehension, you may find the expression
`k%2`

, which evaluates to 0 on even numbers and 1 on odd numbers, to be useful.

```
def riffle(deck):
"""Produces a single, perfect riffle shuffle of DECK, consisting of
DECK[0], DECK[M], DECK[1], DECK[M+1], ... where M is position of the
second half of the deck. Assume that len(DECK) is even.
>>> riffle([3, 4, 5, 6])
[3, 5, 4, 6]
>>> riffle(range(20))
[0, 10, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 17, 8, 18, 9, 19]
"""
"*** YOUR CODE HERE ***"
return _______
return [ deck[(i % 2) * len(deck)//2 + i // 2] for i in range(len(deck)) ]
```

Use OK to test your code:

`python3 ok -q riffle`

### Question 9: Adding matrices

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):
"""
>>> matrix1 = [[1, 3],
... [2, 0]]
>>> matrix2 = [[-3, 0],
... [1, 2]]
>>> add_matrices(matrix1, matrix2)
[[-2, 3], [3, 2]]
"""
"*** YOUR CODE HERE ***"
return ______
return [[x[i][j] + y[i][j] for j in range(len(x[0]))]
for i in range(len(x))]
```

Use OK to test your code:

`python3 ok -q add_matrices`