# Homework 6 Solutions

**Solutions:** You can find the file with solutions for all
questions here.

## Map

We wrote the recursive version of the function `map`

in lecture. Here it is again:

`map`

takes

- m - a one-argument function that you want to map onto each element in the list.
- s - a sequence of values

```
def map(f, s):
"""
Map a function f onto a sequence.
>>> def double(x):
... return x * 2
>>> def square(x):
... return x ** 2
>>> def toLetter(x):
... alpha = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
... return alpha[x%26]
>>> map(double, [1,2,3,4])
[2, 4, 6, 8]
>>> map(square, [1, 2, 3, 4, 5, 10])
[1, 4, 9, 16, 25, 100]
>>> map(toLetter, [3, 0, 19, 0])
['d', 'a', 't', 'a']
"""
if s == []:
return s
return [f(s[0])] + map(f, s[1:])
```

## Required Questions

### Question 1: Filter

Write the recursive version of the function `filter`

which takes

- filter - a one-argument function that returns True if the argument passed in should be included in the list, and False otherwise.
- s - a sequence of values

```
def filter(f, s):
"""Filter a sequence to only contain values allowed by filter.
>>> def is_even(x):
... return x % 2 == 0
>>> def divisible_by5(x):
... return x % 5 == 0
>>> filter(is_even, [1,2,3,4])
[2, 4]
>>> filter(divisible_by5, [1, 4, 9, 16, 25, 100])
[25, 100]
"""
if s == []:
return s
if f(s[0]):
return [s[0]] + filter(f, s[1:])
return filter(f, s[1:])
```

Use OK to test your code:

`python3 ok -q filter`

### Question 2: Reduce

Write the recursive version of the function `reduce`

which takes

- reducer - a two-argument function that reduces elements to a single value
- s - a sequence of values
- base - the starting value in the reduction. This is usually the identity of the reducer

If you're feeling stuck, think about the parameters of `reduce`

.

```
from operator import add, mul
def reduce(reducer, s, base):
"""Reduce a sequence under a two-argument function starting from a base value.
>>> def add(x, y):
... return x + y
>>> def mul(x, y):
... return x*y
>>> reduce(add, [1,2,3,4], 0)
10
>>> reduce(mul, [1,2,3,4], 0)
0
>>> reduce(mul, [1,2,3,4], 1)
24
"""
if s == []:
return base
next_base = reducer(base, s[0])
return reduce(reducer, s[1:], next_base)
```

Use OK to test your code:

`python3 ok -q reduce`

### Question 3: In summation...

Write the recursive version of `summation`

, which takes two arguments,
a number `n`

and a function `term`

, applies `term`

to every number
between `1`

and `n`

inclusive, and returns the sum of those results.

```
def summation(n, term):
"""Return the sum of the 0th to nth terms in the sequence defined
by term.
Should be implemented using recursion.
>>> summation(5, lambda x: x * x * x)
225
>>> summation(9, lambda x: x + 1)
55
>>> summation(5, lambda x: 2**x)
63
"""
if n == 0:
return term(0)
return term(n) + summation(n - 1, term)
```

Use OK to test your code:

`python3 ok -q summation`

### Question 4: Ten-Pairs

Write a function that takes a positive integer `n`

and returns the
number of times the number `digit`

appears. *Do not use any assignment statements.*

```
def count_digit(n, digit):
"""Return how many times digit appears in n.
>>> count_digit(55055, 5)
4
>>> count_digit(1231421, 1)
3
>>> count_digit(12, 3)
0
"""
if n == 0:
return 0
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 count_digit`

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: What if you had a function that counted the times a certain digit appeared.

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

## Challenge Questions - Optional

### Question 5: Decimal

Write the recursive version of the function `decimal`

which takes in `n`

, a number, and returns a list representing the decimal representation of the number.

```
def decimal(n):
"""Return a list representing the decimal representation of a number.
>>> decimal(55055)
[5, 5, 0, 5, 5]
>>> decimal(-136)
['-', 1, 3, 6]
"""
if n < 0:
return ['-'] + decimal(-1 * n)
elif n < 10:
return [n % 10]
else:
return decimal(n // 10) + [n % 10]
```

Use OK to test your code:

`python3 ok -q decimal`

### Question 6: Binary

Write the recursive version of the function `binary`

which takes in `n`

, a number, and returns a list representing the representation of the number in base 2.

```
def binary(n):
"""Return a list representing the representation of a number in base 2.
>>> binary(55055)
[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]
>>> binary(-136)
['-', 1, 0, 0, 0, 1, 0, 0, 0]
"""
if n < 0:
return ['-'] + binary(-1 * n)
elif n < 2:
return [n % 2]
else:
return binary(n // 2) + [n % 2]
```

Use OK to test your code:

`python3 ok -q binary`