Homework 2 Solutions

Solution Files

You can find solutions for all questions in hw02.py.

The construct_check module is used in this assignment, which defines a function check. For example, a call such as

check("foo.py", "func1", ["While", "For", "Recursion"])

checks that the function func1 in file foo.py does not contain any while or for constructs, and is not an overtly recursive function (i.e., one in which a function contains a call to itself by name.)

Several doctests refer to these one-argument functions:

def square(x):
    return x * x

def identity(x):
    return x

triple = lambda x: 3 * x

increment = lambda x: x + 1

add = lambda x, y: x + y

mul = lambda x, y: x * y

Q1: Product

The summation(n, term) function from the higher-order functions lecture adds up term(1) + ... + term(n). Write a similar product(n, term) function that returns term(1) * ... * term(n).

Then, show how to define the factorial function in terms of product.

Try using the identity function for factorial.

def product(n, term):
    """Return the product of the first n terms in a sequence.
    n    -- a positive integer
    term -- a function that takes one argument

    >>> product(3, identity)  # 1 * 2 * 3
    6
    >>> product(5, identity)  # 1 * 2 * 3 * 4 * 5
    120
    >>> product(3, square)    # 1^2 * 2^2 * 3^2
    36
    >>> product(5, square)    # 1^2 * 2^2 * 3^2 * 4^2 * 5^2
    14400
    >>> product(3, increment) # (1+1) * (2+1) * (3+1)
    24
    >>> product(3, triple)    # 1*3 * 2*3 * 3*3
    162
    """
total, k = 1, 1 while k <= n: total, k = term(k) * total, k + 1 return total
# The identity function, defined using a lambda expression! identity = lambda k: k def factorial(n): """Return n factorial for n >= 0 by calling product. >>> factorial(4) 24 >>> factorial(6) 720 >>> from construct_check import check >>> check(HW_SOURCE_FILE, 'factorial', ['Recursion', 'For', 'While']) True """
return product(n, identity)

Use Ok to test your code:

python3 ok -q product
python3 ok -q factorial

The product function has similar structure to summation, but starts accumulation with the value total=1. Factorial is a product with the identity function as term.

Q2: Make Adder with a Lambda

Implement the make_adder function below using a single return statement that returns the value of a lambda expression.

def make_adder(n):
    """Return a function that takes an argument K and returns N + K.

    >>> add_three = make_adder(3)
    >>> add_three(1) + add_three(2)
    9
    >>> make_adder(1)(2)
    3
    """
return lambda k: n + k

Use Ok to test your code:

python3 ok -q make_adder

Note we could solve this without lambdas like this:

def make_adder(n):
    def inner(k):
        return n + k
    return inner

Since this is a one line return function, changing it to a lambda is just a matter of translation.