hw2.py

hw2.py (plain text)


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