# CS 61A

Time: Thu 9/28/17 3 pm

## Environment Diagrams

### The Name Game (fa14-mt1-2)

1. Draw the the environment diagram that results from executing the code below until the entire program is finished or an error occurs.

``````def peace(today):
harmony = love + 2
return harmony + today(love + 1)
def joy(peace):
peace, love = peace + 2, peace + 1
return love // harmony
love, harmony = 3, 2
peace(joy)``````
2. Draw the the environment diagram that results from executing the code below until the entire program is finished or an error occurs.

``````def k(g, b):
def n(s, a):
return g - p
return b(n(b, p))
g, p = 3, 7
k(p + 1, lambda s: g + 3)``````

### Environmental Policy (sp16-mt1-2)

Draw the the environment diagram that results from executing the code below until the entire program is finished or an error occurs.

``````y = 3
def out(h, m):
y = 5 * m
def inner():
return y
if m == 0:
return h
else:
return out(inner, m - 1)
v = out(None, 1)()``````

## Recursions

### You Complete Me (sp15-mt1-3)

1. Implement the combine function, which takes a non-negative integer n, a two-argument function f, and a number result. It applies f to the first digit of n and the result of combining the rest of the digits of n by repeatedly applying f (see the doctests). If n has no digits (because it is zero), combine returns result.

``````from operator import add, mul

def combine(n, f, result):
"""
Combine the digits in non-negative integer n using f.

>>> combine(3, mul, 2) # mul(3, 2)
6
>>> combine(43, mul, 2) # mul(4, mul(3, 2))
24
16
>>> combine(239, pow, 0) # pow(2, pow(3, pow(9, 0)))
8
"""

if n == 0:
return result
else:
return combine(, , )``````
2. Implement the memory function, which takes a number x and a single-argument function f. It returns a function with a peculiar behavior that you must discover from the doctests. You may only use names and call expressions in your solution. You may not write numbers or use features of Python not yet covered in the course.

``````square = lambda x: x * x
double = lambda x: 2 * x

def memory(x, f):
"""
Return a higher-order function that prints its memories.

>>> f = memory(3, lambda x: x)
>>> f = f(square)
3
>>> f = f(double)
9
>>> f = f(print)
6
>>> f = f(square)
3
None
"""

def g(h):
print()
return
return g``````

### Verbose Factorial

Here's a good way to visualize factorials--but a little challenging to code. Write a functional `verbose_fact(n)` that prints out the steps to reduce the recursive cases to a base case. You may utilize the params `fact_so_far` and `prefix` to help with building up your solution.

``````def verbose_fact(n, fact_so_far = 1, prefix = ""):
"""
>>> verbose_fact(1)
1!
= 1
>>> verbose_fact(2)
2!
= 2 x 1!
= 2 x 1
= 2
>>> verbose_fact(3)
3!
= 3 x 2!
= 3 x 2 x 1!
= 3 x 2 x 1
= 6
"""

assert n >= 1, "Use n >= 1"

Solution
``````def verbose_fact(n, fact_so_far = 1, prefix = ""):
"""
>>> verbose_fact(1)
1!
= 1
>>> verbose_fact(2)
2!
= 2 x 1!
= 2 x 1
= 2
>>> verbose_fact(3)
3!
= 3 x 2!
= 3 x 2 x 1!
= 3 x 2 x 1
= 6
"""

assert n >= 1, "Use n >= 1"

# Check if it's the first time calling the function
if not prefix:
# First time
print("  " + str(n) + "!")
else:
# Not the first time
print("= " + prefix + str(n) + "!")

# Check if recursion is finished
if n == 1:
# Base case, end of recursion
if prefix: print("= " + prefix + str(n)) # Print the simplified "1!"
# Print out the solution
print("= " + str(fact_so_far * n))
else:
# Continue by recursion
verbose_fact(n - 1, fact_so_far * n, prefix + str(n) + " x ")``````

They are naturally sustainable! Oh well, think about how trees are conceptually related to pairs. Define the terminologies around trees--tree, root, label, branch, leaf (the language we use may vary in different places).

Consider the following implementation:

``````def tree(label, branches=[]):
return [label] + branches

def label(tree):
return tree

def branches(tree):
return tree[1:]``````

There are multiple ways to get started on playing with such tree structure! As a few examples:

1. Given a tree, how can we find a largest/smallest label in the leaves?
2. Given a tree, how can we find a largest/smallest label in the tree?
3. Given a tree, how can we find the sum of all labels (assuming all labels are numbers)?
4. Given a tree, how can we make a copy of it with all the leaves pruned? The function is non-destructive.
5. Given a tree and a label, how can we check if the label we want is in the tree?
6. Given a tree, how can we check if there aren't any descendent nodes of a same label for any node in the tree?