"""CS 61A HW 02
Name:
Login:
TA:
Section:
"""
from operator import add, mul, sub
#### Q1
def double(f):
"""Return a function that applies f twice.
>>> increment = lambda x: x + 1
>>> add_two = double(increment)
>>> add_two(2)
4
>>> double(lambda x: x + 2)(2)
6
"""
# BEGIN SOLUTION
return lambda x: f(f(x))
# END SOLUTION
#### Q2
def compose1(f, g):
"""Return the composition function which given x, computes f(g(x))."""
return lambda x: f(g(x))
def repeated(f, n):
"""Return the function that computes the nth application of f.
>>> square = lambda x: x ** 2
>>> increment = lambda x: x + 1
>>> add_five = repeated(increment, 5)
>>> add_five(6)
11
>>> repeated(lambda x: x + 2, 7)(6)
20
>>> repeated(square, 2)(5)
625
"""
# BEGIN SOLUTION
repeated_function = lambda x: x # Apply function 0 times
while n > 0:
repeated_function, n = compose1(f, repeated_function), n - 1
return repeated_function
# END SOLUTION
#### Q3
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
"""
# BEGIN SOLUTION
return lambda x: (f(x - dx) + f(x) + f(x + dx)) / 3
# END SOLUTION
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
"""
# BEGIN SOLUTION
smooth_with_dx = lambda g: smooth(g, dx)
return repeated(smooth_with_dx, n)(f)
# END SOLUTION
#### Q4
def continued_frac(n_term, d_term, k):
"""Returns the k-term continued fraction with numerators defined by n_term
and denominators defined by d_term.
>>> # 1 / golden ratio
... round(continued_frac(lambda x: 1, lambda x: 1, 8), 3)
0.618
>>> # 1 / (1 + (2 / (2 + (3 / (3 + (4 / 4))))))
... round(continued_frac(lambda x: x, lambda x: x, 4), 6)
0.578947
"""
# BEGIN SOLUTION
frac = 0
while k > 0:
frac = n_term(k)/(d_term(k) + frac)
k -= 1
return frac
# END SOLUTION
#### Extra for Experts
#### Q5
def zero(f):
return lambda x: x
def successor(n):
return lambda f: lambda x: f(n(f)(x))
def one(f):
"""Do this without using successor or zero"""
# BEGIN SOLUTION
return lambda x: f(x)
# END SOLUTION
def two(f):
"""Do this without using successor or zero"""
# BEGIN SOLUTION
return lambda x: f(f(x))
# END SOLUTION
def add(n, m):
"""Add the church numerals n and m to produce the church numeral
representing n + m
"""
# BEGIN SOLUTION
return lambda f: lambda x: n(f)(m(f)(x))
# END SOLUTION
def church_to_int(c):
"""Convert the church numeral c to a regular Python integer
>>> church_to_int(zero)
0
>>> church_to_int(one)
1
>>> church_to_int(successor(zero))
1
>>> church_to_int(two)
2
>>> church_to_int(successor(successor(zero)))
2
>>> church_to_int(add(two, one))
3
>>> church_to_int(successor(successor(successor(zero))))
3
"""
# BEGIN SOLUTION
return c(lambda x: x + 1)(0)
# END SOLUTION