# Lab 4: Data and Sequences, Data Abstraction

By the end of this lab, you should have submitted the `lab4` assignment using the command `submit lab4`.

This lab is due by 11:59pm on 7/8/2014.

Here is a lab04.py starter file for this lab.

## Data and Sequences

### 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     # Q1
______1
>>> x     # Q2
______IndexError
>>> x[-1]    # Q3
______3
>>> x[-3]    # Q4
______1``````

### Question 2

``````>>> x = [1, 2, 3, 4]
>>> x[1:3]       # Q1
______[2, 3]
>>> x[:2]        # Q2
______[1, 2]
>>> x[1:]        # Q3
______[2, 3, 4]
>>> x[-2:3]      # Q4
______
>>> x[::2]       # Q5
______[1, 3]
>>> x[::-1]      # Q6
______[4, 3, 2, 1]
>>> x[-1:0:-1]   # Q7
______[4, 3, 2]``````

### Question 3

``````>>> y = 
>>> len(y)       # Q1
______1
>>> 1 in y       # Q2
______True
>>> y + [2, 3]   # Q3
______[1, 2, 3]
>>>  + y     # Q4
______[0, 1]
>>> y * 3        # Q5
______[1, 1, 1]
>>> z = [[1, 2], [3, 4, 5]]
>>> len(z)       # Q6
______``````

### Question 4

For each of the following, define the function so the expression evaluates to 7.

``````>>> x = [1, 3, 5, 7]
>>> def get_seven(lst):
...     return lst[-1]
...
>>> get_seven(x)    # example
7

>>> x = [1, 3, [5, 7], 9]
>>> get_seven_a(x)
7

>>> x = []
>>> get_seven_b(x)
7

>>> x = [1, [2, [3, [4, [5, [6, ]]]]]]
>>> get_seven_c(x)
7``````
1. `x`
2. `x`
3. `x`

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

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

>>> reverse_recursive([1, 2, 3, 4])
[4, 3, 2, 1]
"""
"*** YOUR CODE HERE ***"``````
``````def reverse_iter(lst):
new, i = (), 0
while i < len(lst):
new = (lst[i],) + new
i += 1
return new

def reverse_recursive(lst):
if not lst:
return []
return reverse_recursive(lst[1:]) + (lst,)``````

### 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 reports its deep length. See the doctests for the function's behavior. You may write this function iteratively or recursively.

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
>>> y = [[1, [1, 1]], 1, [1, 1]]  # deep list
>>> deep_len(y)
6
"""
"*** YOUR CODE HERE ***"``````
``````def deep_len(lst):
if not lst:
return 0
elif type(lst) == list:
return deep_len(lst) + deep_len(lst[1:])
else:
return 1 + deep_len(lst[1:])``````

### Question 7

Write a recursive 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.

>>> 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
def merge(lst1, lst2):
if not lst1 or not lst2:
return lst1 + lst2
elif lst1 < lst2:
return (lst1,) + merge(lst1[1:], lst2)
else:
return (lst2,) + merge(lst1, lst2[1:])

# iterative
def merge(lst1, lst2):
new = ()
while lst1 and lst2:
if lst1 < lst2:
new += (lst1,)
lst1 = lst1[1:]
else:
new += (lst2,)
lst2 = lst2[1:]
if lst1:
return new + lst1
else:
return new + lst2``````

## Using Abstractions

One day, you and a friend decide to work on a programming project — implement a Rational Number interface. Recall that a rational number is any number that can be expressed as p / q, where p and q are integers.

Your friend gets to work implementing an abstract data type (ADT for short) to represent rational numbers. In the meantime, you will be writing functions that perform mathematical operations on rational numbers. You and your friend agree on a set of constructors and selectors:

``````def make_rat(num, den):
"""Creates a rational number, given a numerator and
denominator.
"""

def num(rat):
"""Extracts the numerator from a rational number."""

def den(rat):
"""Extracts the denominator from a rational number."""``````

`make_rat` is the constructor, and `num` and `den` are the selectors.

Notice that the functions don't have any bodies yet, so you won't know how they work — but that's okay! As long as you know what each function is supposed to do, you can write your code. This is called data abstraction.

Finish question 8 first. After that, We'll provide you a way to test your code.

### Question 8

Implement addition and subtraction for rational numbers (remember that you can use your solution for `add_rat` in `sub_rat`):

``````def add_rat(a, b):
"""Adds two rational numbers A and B. For example,
(3 / 4) + (5 / 3) = (29 / 12)

>>> a, b = make_rat(3, 4), make_rat(5, 3)
>>> c = add_rat(a, b)
>>> num(c)
29
>>> den(c)
12
"""
"*** YOUR CODE HERE ***"

def sub_rat(a, b):
"""Subtracts two rational numbers A and B. For example,
(3 / 4) - (5 / 3) = (-11 / 12)

>>> a, b = make_rat(3, 4), make_rat(5, 3)
>>> c = sub_rat(a, b)
>>> num(c)
-11
>>> den(c)
12
"""
"*** YOUR CODE HERE ***"``````
``````def add_rat(a, b):
new_num = num(a) * den(b) + num(b) * den(a)
new_den = den(a) * den(b)
return make_rat(new_num, new_den)

def sub_rat(a, b):
neg = make_rat(-num(b), den(b))

# alternate solution
def sub_rat(a, b):
new_num = num(a) * den(b) - num(b) * den(a)
new_den = den(a) * den(b)
return make_rat(new_num, new_den)``````

## Defining Abstractions

Your friend finally finished implementing the constructors and selectors for the Rational Number ADT — you can use the following code to check your answers to the previous exercises.

``````def make_rat(num, den):
"""Creates a rational number, given a numerator and denominator."""
return lambda x, y: [lambda: den + x, lambda: num + y]

def num(rat):
"""Extracts the numerator from a rational number."""
return rat(2, 3)() - 3

def den(rat):
"""Extracts the denominator from a rational number."""
return rat(8, 5)() - 8``````

### Question 9

The code your friend wrote will work, but it is very hard to understand (luckily, you respected data abstraction, so your own code doesn't depend on how your friend's works). Not only that, but it doesn't simplify fractions in the constructor!

Consider the following rational:

``````>>> a = make_rat(6, 9)
>>> num(a)
6
>>> den(a)
9``````

We would like to simplify the rational number so that it becomes (2 / 3). Write the `make_rat` function so that it does this, and write the two selectors `num` and `den` to be consistent with your constructor.

Hint: you can write your own Greatest Common Divisor function, or you can use Python's built-in `gcd` function.

Also, in `make_rat`, make sure to add some `assert` statements to check that `num` and `den` are indeed integers and use appropriate error messages if they are not (refer to the doctests in the skeleton code).

``````from fractions import gcd

def make_rat(num, den):
"*** YOUR CODE HERE ***"

def num(rat):
"*** YOUR CODE HERE ***"

def den(rat):
"*** YOUR CODE HERE ***"``````

Anything that is consistent will work here. Here's an example:

``````def make_rat(num, den):
assert type(num) == int, 'Numerator is not an integer'
assert type(den) == int, 'Denominator is not an integer'
gcd_fraction = gcd(num, den)
return (num // gcd_fraction, den // gcd_fraction)

def num(rat):
return rat

def den(rat):
return rat``````

Now check your solutions again to the previous exercises. Do they still work? If you didn't violate data abstraction, they should!

## Abstraction Violations

Now we will fix some data abstraction violations. A data abstraction violation occurs when a piece of code does not use the constructors and selectors of an ADT. Consider the following rational number ADT:

``````# Constructor
def make_rat(num, dem):
return [num, dem]

# Selectors
def num(rat):
return rat

def dem(rat):
return rat``````

Given that the three functions above are the only constructors and selectors, the following function `print_rat` contains two abstraction violations:

``````def print_rat(rat):
"""Returns the last element in a vector."""
return print(rat, '/', rat)``````

The rational number ADT is not guaranteed to be implemented to be a list, so we can't index into 'rat'.

The best way to spot abstraction violations is to ignore the implementation of the constructors and selectors. If you want to take it one step further, you can imagine the constructors and selectors were implemented with lambdas:

``````# Constructor
def make_rat(num, den):
"""Creates a rational number, given a numerator and denominator."""
return lambda x, y: [lambda: den + x, lambda: num + y]

# Selectors
def num(rat):
"""Extracts the numerator from a rational number."""
return rat(2, 3)() - 3

def den(rat):
"""Extracts the denominator from a rational number."""
return rat(8, 5)() - 8``````

### Question 10

Now, the `print` function above clearly won't work, because it violates abstraction! How do we fix this? Fix the broken 'print_rat' in your starter file.
``````def print_rat(rat):
"""Returns the last element in a vector."""
return print(num(rat), '/', dem(rat))``````

### Question 11: (Optional)

For the following function, spot as many abstraction violations as you can, and rewrite the code to fix it. Use the rational number ADT defined above. This is really important practice, so please make sure you understand why your answers are correct.

``````def approximate_pi(iter=1000):
""" Computes an approximation of pi based on the idea
pi/4 = (2/3)*(4/3)*(4/5)*(6/5)*(6/7)*(8/7)...

>>> approximate_pi(10)
3.2751010413348074
>>> approximate_pi()
3.1431607055322663
>>> approximate_pi(10000)
3.1417497057380523
"""
result = make_rat(1, 1)
compute_num = lambda x: 2 + 2 * ((x + 1) // 2)
compute_dem = lambda x: 1 + 2 * ((x + 2) // 2)
for i in range(iter):
n = compute_num(i)
d = compute_dem(i)
result = [n * result, d * result]
return 4 * num(result) / result``````
``````def approximate_pi(iter=1000):
""" Computes an approximation of pi based on the idea
pi/4 = (2/3)*(4/3)*(4/5)*(6/5)*(6/7)*(8/7)...

>>> approximate_pi(10)
3.2751010413348074
>>> approximate_pi()
3.1431607055322663
>>> approximate_pi(10000)
3.1417497057380523
"""
result = make_rat(1, 1)
compute_num = lambda x: 2 + 2 * ((x + 1) // 2)
compute_dem = lambda x: 1 + 2 * ((x + 2) // 2)
for i in range(iter):
n = compute_num(i)
d = compute_dem(i)
new_rat = make_rat(n, d)
result = mul_rat(new_rat, result)
return 4 * num(result) / dem(result)``````