Stumped by one line of Python

Question

I'm unofficially doing a python course CS61A through Berkely, and I'm absolutely stumped by one simple assignment that requires me to provide only one expression at the very end of the provided template. Here is the problem code:

# HW 4 Q5. (fall 2012)

def square(x):
    return x*x

def compose1(f, g):
    """Return a function of x that computes f(g(x))."""
    return lambda x: f(g(x))

from functools import reduce

def repeated(f, n):
    """Return the function that computes the nth application of f, for n>=1.

    f -- a function that takes one argument
    n -- a positive integer

    >>> repeated(square, 2)(5)
    625
    >>> repeated(square, 4)(5)
    152587890625
    """
    assert type(n) == int and n > 0, "Bad n"
    return reduce(compose1, "*** YOUR CODE HERE ***" )

repeated(square, 2)(5) # Sample run

I've tried everything to make this work. It seems to me that this return stmt should do it:

return reduce(compose1, range(n))

But I'm not even close. Compose1 takes two args (f, g) and these should both be functions. But when the return statement calls 'compose1', 'compose1' uses '0' for 'f' and 'n' for 'g.' But 'f' and 'g' should be the function called--'square'

What am I missing.

Answer 1

reduce has an edge case when a list with only one item is supplied: It simply returns the first item. So if you enter [f] in return reduce(compose1, [f]) it is equal to f.

If two items are supplied compose1 is actually applied to those two items and returned. So [f, f] would return:

  compose(f, f)
= lambda x: f(f(x))

The next item in the list will be used as second argument together with the previous result as first argument. So if we would supply [f, f, f] it would return:

  compose(compose(f, f), f)
= lambda x: f(f(f(x)))

Now you should see a pattern. Every f in the list is applied once. So you would need [f] * n to get a list with n times f.

Answer 2

Here's a hint. Think about what the return value of compose1(square, square) would be.

Answer 3

Compose takes two argements, both of which need to be functions

By using range you are passing compse1 a pair of integers (which rightly blows up because ints are not callable. You want to pass a list of the functions you want to compose.

reduce calls its first argument on the first two elements of its second argument, then on that result and the third element... till you reach the end. The intermediate results will look like:

compose1(f1, f2)
compose1(compose(f1, f2), f3)
compase1(compose1(compose(f1, f2), f3), f4)
....

or more compactly

 f1(f2(x))
 f1(f2(f3(x)))
 f1(f2(f3(f4(x))))
 ....