# Lab 3: Data Abstraction and Recursion/Lambdas Review

*Due at 11:59pm on 02/12/2016.*

## Starter Files

Download lab03.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 through 6 in lab03.py and submit through OK.
- Questions 7 and 8 are more practice with lambda expressions. You can run Python interactively or use Online Python Tutor to test them out, but try solving them yourself first!
- Questions 9 and 10 are
*extra practice*. They can be found in the lab03_extra.py file. It is recommended that you complete these problems on your own time.

## 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. We'll look into defining the constructors and selectors later in this discussion.

### Question 1: 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 2: Closer city

Next, implement `closer_city`

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

You may only use selectors and constructors (introduced above) and the
`distance`

function you just defined for this question. All of the
selector and constructor functions can be found in `utils.py`

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

## Recursion

### Question 3: AB+C

Implement `ab_plus_c`

, a function that takes arguments `a`

, `b`

, and
`c`

and computes `a * b + c`

. You can assume a and b are both positive
integers. However, you can't use the `*`

operator. Try recursion!

```
def ab_plus_c(a, b, c):
"""Computes a * b + c.
>>> ab_plus_c(2, 4, 3) # 2 * 4 + 3
11
>>> ab_plus_c(0, 3, 2) # 0 * 3 + 2
2
>>> ab_plus_c(3, 0, 2) # 3 * 0 + 2
2
"""
"*** YOUR CODE HERE ***"
if b == 0:
return c
return a + ab_plus_c(a, b - 1, c)
```

Use OK to test your code:

`python3 ok -q ab_plus_c`

### Question 4: Is Prime

Write a function `is_prime`

that takes a single argument `n`

and returns True if `n`

is a prime number and False otherwise.
Assume n > 1. We implemented this in the project iteratively, now
time to do it recursively!

Hint: You will need a helper function! Remember helper functions are useful if you need to keep track of more variables than the given parameters, or if you need to change the value of the input (think count_up from Lab 2)

```
def is_prime(n):
"""Returns True if n is a prime number and False otherwise.
>>> is_prime(2)
True
>>> is_prime(16)
False
>>> is_prime(521)
True
"""
"*** YOUR CODE HERE ***"
def helper(i):
if i < sqrt(n): #could replace with i == 1
return True
if n % i == 0:
return False
return helper(i - 1)
return helper(n - 1)
```

Use OK to test your code:

`python3 ok -q is_prime`

### Question 5: Interleaved Sum

Recall that the `summation`

function computes the sum of a sequence of
terms from 1 to `n`

:

```
def summation(n, term):
"""Return the sum of the first n terms of a sequence.
>>> summation(5, lambda x: pow(x, 3))
225
"""
total, k = 0, 1
while k <= n:
total, k = total + term(k), k + 1
return total
```

Write a function `interleaved_sum`

that similarly computes the sum of a
sequence of terms from 1 to `n`

, but uses different function to compute
the terms for odd and even numbers. Do so without using any loops or
testing in any way if a number is odd or even. (You may test if a
number is equal to 0, 1, or `n`

.)

Hint: Use recursion and a helper function!

```
def interleaved_sum(n, odd_term, even_term):
"""Compute the sum odd_term(1) + even_term(2) + odd_term(3) + ..., up
to n.
>>> # 1 + 2^2 + 3 + 4^2 + 5
... interleaved_sum(5, lambda x: x, lambda x: x*x)
29
"""
"*** YOUR CODE HERE ***"
return interleaved_helper(n, odd_term, even_term, 1)
def interleaved_helper(n, term0, term1, k):
if k == n:
return term0(k)
return term0(k) + interleaved_helper(n, term1, term0, k+1)
# Alternate solution
def interleaved_sum2(n, odd_term, even_term):
"""Compute the sum odd_term(1) + even_term(2) + odd_term(3) + ..., up
to n.
>>> # 1 + 2^2 + 3 + 4^2 + 5
... interleaved_sum2(5, lambda x: x, lambda x: x*x)
29
"""
total, term0, term1 = interleaved_helper2(n, odd_term, even_term)
return total
def interleaved_helper2(n, odd_term, even_term):
if n == 1:
return odd_term(1), even_term, odd_term
else:
total, term0, term1 = interleaved_helper2(n-1, odd_term,
even_term)
return total + term0(n), term1, term0
```

Use OK to test your code:

`python3 ok -q interleaved_sum`

## Lambdas

Although only question 6 is mandatory, we recommend going through question 7 and 8 through Python Tutor on your own. Lambda environment diagrams can be quite tricky and have come up on past tests.

### Question 6: WWPP: Lambda Trivia

The following WWPP questions will review your understanding of lambdas. Python Tutor may be helpful in understanding what is happening.

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

`python3 ok -q lambda -u`

Hint: Remember for all WWPP questions, enter`Function`

if you believe the answer is`<function ...>`

and`Error`

if it errors.

```
>>> x = 5
>>> x = lambda x: lambda x: lambda y: 3+x
>>> x(3)(5)(7)
______8
>>> you = 'fly'
>>> yo, da = lambda do: you, lambda can: True
>>> yo = yo('jedi')
>>> da = (3 and 4 and 5 and (False or ' you shall'))
>>> yo+da
______'fly you shall'
>>> annoying = lambda yell: annoying
>>> annoying('aiya')('aaa')('aaaa')('aaaaa')('aaaaaa')
______Function
>>> more = ' productive'
>>> lip_service = lambda say: print(say)
>>> useful_person = lambda do: do + more
>>> lip_service('blah blah blah') + useful_person('be')
______blah blah blah
Error
```

### Question 7: Lambda the Plentiful

Try drawing an environment diagram for the following code and predict what Python will output.

**Note**: This is a challenging problem! Work together with your neighbors and
see if you can arrive at the correct answer.

You can check your work with the Online Python Tutor, but try drawing it yourself first!

```
>>> def go(bears):
... gob = 3
... print(gob)
... return lambda ears: bears(gob)
>>> gob = 4
>>> bears = go(lambda ears: gob)
______3
>>> bears(gob)
______4
```

Hint: What is the parent frame for a lambda function?

### Question 8: Church numerals

Find the value of the following three expressions, using the given
values of `t`

and `s`

.

```
>>> t = lambda f: lambda x: f(f(f(x)))
>>> s = lambda x: x + 1
>>> t(s)(0)
______3
>>> t(t(s))(0)
______9
>>> t(t)(s)(0)
______27
```

## Extra Questions

Questions in this section are not required for submission. However, we encourage you to try them out on your own time for extra practice.

### Question 9: Palindrome

A number is considered a palindrome if it reads the same forwards and backwards. Fill in the blanks '_' to help determine if a number is a palindrome. In the spirit of exam style questions, please do not edit any parts of the function other than the blanks.

```
def is_palindrome(n):
"""
Fill in the blanks '_____' to check if a number
is a palindrome.
>>> is_palindrome(12321)
True
>>> is_palindrome(42)
False
>>> is_palindrome(2015)
False
>>> is_palindrome(55)
True
"""
x, y = n, 0
f = lambda: _____
f = lambda: y * 10 + x % 10 while x > 0:
x, y = _____, f()
x, y = x // 10, f() return y == n
```

Use OK to test your code:

`python3 ok -q is_palindrome`

### Question 10: Ten-pairs

Write a function that takes a positive integer `n`

and returns the
number of ten-pairs it contains. A ten-pair is a pairs of digits
within `n`

that sum to 10. *Do not use any assignment statements.*

The number 7,823,952 has 3 ten-pairs. The first and fourth digits sum to 7+3=10, the second and third digits sum to 8+2=10, and the second and last digit sum to 8+2=10:

Hint: Use a helper function to calculate how many times a digit appears in n.

```
def ten_pairs(n):
"""Return the number of ten-pairs within positive integer n.
>>> ten_pairs(7823952)
3
>>> ten_pairs(55055)
6
>>> ten_pairs(9641469)
6
"""
"*** YOUR CODE HERE ***"
if n < 10:
return 0
else:
return ten_pairs(n//10) + count_digit(n//10, 10 - n%10)
def count_digit(n, digit):
"""Return how many times digit appears in n.
>>> count_digit(55055, 5)
4
"""
if n == 0:
return 0
else:
if n%10 == digit:
return count_digit(n//10, digit) + 1
else:
return count_digit(n//10, digit)
```

Use OK to test your code:

`python3 ok -q ten_pairs`