Take the 2-minute tour ×

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)
    >>> repeated(square, 4)(5)
    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.

share|improve this question
Here's my hint: you're trying to "compute the nth application of f" - which means that missing code must include (somehow) both f and n. your suggested return statement doesn't do anything with f. think about how you'd run f for n times. –  Jonathan Vanasco Feb 23 '13 at 21:06
add comment

3 Answers

up vote 1 down vote accepted

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.

share|improve this answer
Thank you Tim. This finally makes sense. I was truly stumped and frustrated because I knew the solution had to be simple but it was out of my reach. Your explanation makes perfect sense. Thanks again. –  Dominique LaCasse Mar 16 '13 at 16:25
add comment

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

share|improve this answer
add comment

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

share|improve this answer
I never use reduce so figured I'd try my hand at this -- thanks. It took me a minute to wrap my head around your explanation, but I figured it out. –  Jonathan Vanasco Feb 23 '13 at 21:03
add comment

Your Answer


