## Starter Files

Download lab07.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

## Submission

This lab will not be graded. You do not need to submit anything.

## Control

### Question 1: Abundant

Implement a function `abundant` that takes a positive integer `n`. It prints all ways of multiplying two positive integers to make `n`. It returns whether `n` is an abundant number, meaning that the sum of its proper divisors is greater than `n`. A proper divisor of `n` is an integer smaller than `n` that evenly divides `n`.

Hint: To print `1 * 2`, use the expression `print(1, '*', 2)`

``````def abundant(n):
"""Print all ways of forming positive integer n by multiplying two positive
integers together, ordered by the first term. Then, return whether the sum
of the proper divisors of n is greater than n.

A proper divisor of n evenly divides n but is less than n.

>>> abundant(12) # 1 + 2 + 3 + 4 + 6 is 16, which is larger than 12
1 * 12
2 * 6
3 * 4
True
>>> abundant(14) # 1 + 2 + 7 is 10, which is not larger than 14
1 * 14
2 * 7
False
>>> abundant(16)
1 * 16
2 * 8
4 * 4
False
>>> abundant(20)
1 * 20
2 * 10
4 * 5
True
>>> abundant(22)
1 * 22
2 * 11
False
>>> r = abundant(24)
1 * 24
2 * 12
3 * 8
4 * 6
>>> r
True

>>> r = abundant(25)
1 * 25
5 * 5
>>> r
False
>>> r = abundant(156)
1 * 156
2 * 78
3 * 52
4 * 39
6 * 26
12 * 13
>>> r
True
"""
d, total = 1, 0
while d*d <= n:
if n % d == 0:
print(d, '*', n//d)
total = total + d
if d > 1 and d*d < n:
total = total + n//d
d = d + 1

Use OK to test your code:

``python3 ok -q abundant``

### Question 2: Same hailstone

Implement `same_hailstone`, which returns whether positive integer arguments `a` and `b` are part of the same hailstone sequence. A hailstone sequence is defined in Homework 1 as the following:

1. Pick a positive integer `n` as the start.
2. If `n` is even, divide it by 2.
3. If `n` is odd, multiply it by 3 and add 1.
4. Continue this process until `n` is 1.
``````def same_hailstone(a, b):
"""Return whether a and b are both members of the same hailstone
sequence.

>>> same_hailstone(10, 16) # 10, 5, 16, 8, 4, 2, 1
True
>>> same_hailstone(16, 10) # order doesn't matter
True
>>> result = same_hailstone(3, 19) # return, don't print
>>> result
False

Extra tests:

>>> same_hailstone(19, 3)
False
>>> same_hailstone(4858, 61)
True
>>> same_hailstone(7, 6)
False
"""
return in_hailstone(a, b) or in_hailstone(b, a)

def in_hailstone(a, b):
"""Return whether b is in hailstone sequence of a."""
while a > 1:
if a == b:
return True
elif a % 2 == 0:
a = a // 2
else:
a = a * 3 + 1
return False``````

Use OK to test your code:

``python3 ok -q same_hailstone``

## Higher-Order Functions

### Question 3: Piecewise

Implement `piecewise`, which takes two one-argument functions, `f` and `g`, along with a number `b`. It returns a new function that takes a number `x` and returns either `f(x)` if `x` is less than `b`, or `g(x)` if `x` is greater than or equal to `b`.

``````def piecewise(f, g, b):
"""Returns the piecewise function h where:

h(x) = f(x) if x < b,
g(x) otherwise

>>> def negate(x):
...     return -x
>>> identity = lambda x: x
>>> abs_value = piecewise(negate, identity, 0)
>>> abs_value(6)
6
>>> abs_value(-1)
1
"""
def h(x):
if x < b:
return f(x)
return g(x)
return h``````

Use OK to test your code:

``python3 ok -q piecewise``

### Question 4: Smoothing

The idea of smoothing a function is a concept used in signal processing among other things. If `f` is a one-argument function and `dx` is some small number, then the smoothed version of `f` is the function whose value at a point `x` is the average of `f(x - dx)`, `f(x)`, and `f(x + dx)`. Write a function `smooth` that takes as input a function `f` and a value to use for `dx` and returns a function that computes the smoothed version of `f`. Do not use any `def` statements inside of `smooth`; use `lambda` expressions instead.

``````def smooth(f, dx):
"""Returns the smoothed version of f, g where

g(x) = (f(x - dx) + f(x) + f(x + dx)) / 3

>>> square = lambda x: x ** 2
>>> round(smooth(square, 1)(0), 3)
0.667
"""
return lambda x: (f(x - dx) + f(x) + f(x + dx)) / 3``````

Use OK to test your code:

``python3 ok -q smooth``

It is sometimes valuable to repeatedly smooth a function (that is, smooth the smoothed function, and so on) to obtain the `n`-fold smoothed function. Show how to generate the `n`-fold smoothed function, `n_fold_smooth`, of any given function using your `smooth` function and `repeated` function:

``````def repeated(f, n):
"""Returns a single-argument function that takes a value, x, and applies
the single-argument function F to x N times.
>>> repeated(lambda x: x*x, 3)(2)
256
"""
def h(x):
for k in range(n):
x = f(x)
return x
return h``````

As with `smooth`, use `lambda` expressions rather than `def` statements in the body of `n_fold_smooth`.

``````def n_fold_smooth(f, dx, n):
"""Returns the n-fold smoothed version of f

>>> square = lambda x: x ** 2
>>> round(n_fold_smooth(square, 1, 3)(0), 3)
2.0
"""
return repeated(lambda g: smooth(g, dx), n)(f)``````

The `repeated` function takes in a single-argument function `f` and returns a new single-argument function that repeatedly applies `f` to its argument. We want to repeatedly apply `smooth`, but `smooth` is a two-argument function. So we first have to convert it to a one-argument function, using a `lambda` expression. Then `repeated` returns a function that repeatedly smooths its input function, and we apply this to `f` to get an `n`-fold smoothed version of `f`.

Use OK to test your code:

``python3 ok -q n_fold_smooth``

## Lambdas

### Question 5: 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 6: 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 7: Deep Linked List Length

A linked list that contains one or more linked lists as elements is called a deep linked list. Write a function `deep_len` that takes in a (possibly deep) linked list and returns the deep length of that linked list, which is the sum of the deep length of all linked lists contained in a deep linked list.

``````def deep_len(lnk):
""" Returns the deep length of a possibly deep linked list.
3
4
5
"""
return 1
elif lnk == empty:
return 0
else:
return deep_len(first(lnk)) + deep_len(rest(lnk))``````

Use OK to test your code:

``python3 ok -q deep_len``

### Question 8: Linked Lists as Strings

Marvin and Brian like different ways of displaying the linked list structure in Python. While Marvin likes box and pointer diagrams, Brian prefers a more futuristic way. Write a function `make_to_string` that returns a function that converts the linked list to a string in their preferred style.

Hint: You can convert numbers to strings using the `str` function, and you can combine strings together using `+`.

``````>>> str(4)
'4'
>>> 'cs ' + str(61) + 'a'
'cs 61a'``````
``````def make_to_string(front, mid, back, empty_repr):
""" Returns a function that turns linked lists to strings.

>>> marvins_to_string = make_to_string("[", "|-]-->", "", "[]")
>>> brians_to_string = make_to_string("(", " . ", ")", "()")
>>> marvins_to_string(lst)
'[1|-]-->[2|-]-->[3|-]-->[4|-]-->[]'
>>> marvins_to_string(empty)
'[]'
>>> brians_to_string(lst)
'(1 . (2 . (3 . (4 . ()))))'
>>> brians_to_string(empty)
'()'
"""
def printer(lst):
if lst == empty:
return empty_repr
else:
return front + str(first(lst)) + mid + printer(rest(lst)) + back
return printer``````

Use OK to test your code:

``python3 ok -q make_to_string``

## Trees

### Question 9: Tree Map

Define the function `tree_map`, which takes in a tree and a one-argument function as arguments and returns a new tree which is the result of mapping the function over the entries of the input tree.

``````def tree_map(fn, t):
"""Maps the function fn over the entries of tree and returns the
result in a new tree.

>>> numbers = tree(1,
...                [tree(2,
...                      [tree(3),
...                       tree(4)]),
...                 tree(5,
...                      [tree(6,
...                            [tree(7)]),
...                       tree(8)])])
>>> print_tree(tree_map(lambda x: 2**x, numbers))
2
4
8
16
32
64
128
256
"""
if children(t) == []:
return tree(fn(entry(t)), [])
mapped_subtrees = []
for subtree in children(t):
mapped_subtrees += [ tree_map(fn, subtree) ]
return tree(fn(entry(t)), mapped_subtrees)

# Alternate solution
def tree_map(fn, t):
return tree(fn(entry(t)), [tree_map(fn, t) for t in children(t)])``````

Use OK to test your code:

``python3 ok -q tree_map``

Define the function `add_trees`, which takes in two trees and returns a new tree where each corresponding node from the first tree is added with the node from the second tree. If a node at any particular position is present in one tree but not the other, it should be present in the new tree as well.

Hint: You may want to use the built-in zip function to iterate over multiple sequences at once.

``````def add_trees(t1, t2):
"""
>>> numbers = tree(1,
...                [tree(2,
...                      [tree(3),
...                       tree(4)]),
...                 tree(5,
...                      [tree(6,
...                            [tree(7)]),
...                       tree(8)])])
2
4
6
8
10
12
14
16
5
4
5
>>> print_tree(add_trees(tree(2, [tree(3)]), tree(2, [tree(3), tree(4)])))
4
6
4
>>> print_tree(add_trees(tree(2, [tree(3, [tree(4), tree(5)])]), \
tree(2, [tree(3, [tree(4)]), tree(5)])))
4
6
8
5
5
"""
if not t1:
return t2
if not t2:
return t1
new_entry = entry(t1) + entry(t2)
t1_children, t2_children = children(t1), children(t2)
length_t1, length_t2 = len(t1_children), len(t2_children)
if length_t1 < length_t2:
t1_children += [None for _ in range(length_t1, length_t2)]
elif len(t1_children) > len(t2_children):
t2_children += [None for _ in range(length_t2, length_t1)]
return tree(new_entry, [add_trees(child1, child2) for child1, child2 in zip(t1_children, t2_children)])``````

Use OK to test your code:

``python3 ok -q add_trees``