1
\$\begingroup\$

If \$f\$ is a numerical function and \$n\$ is a positive integer, then we can form the \$n\$th repeated application of \$f\$, which is defined to be the function whose value at \$x\$ is \$f(f(...(f(x))...))\$. For example, if \$f\$ adds 1 to its argument, then the \$n\$th repeated application of \$f\$ adds \$n\$. Write a function that takes as inputs a function \$f\$ and a positive integer \$n\$ and returns the function that computes the \$n\$th repeated application of \$f\$:

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

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

    >>> repeated(square, 2)(5)
    625
    >>> repeated(square, 4)(5)
    152587890625
    """
    "*** YOUR CODE HERE ***"

Below is the solution:

from operator import mul

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

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

    >>> repeated(square, 2)(5)
    625
    >>> repeated(square, 4)(5)
    152587890625
    """
    def g(x):
        i = 1
        while i <= n:
            x, i = f(x), i + 1
        return x
    return g


def square(x):
    return mul(x, x)

print(repeated(square,4)(2))

I've tested it and it looks fine.

Can I optimise this code better? Do you think I can use better names instead of i & g?

\$\endgroup\$
1
  • \$\begingroup\$ Agreed. +1 for the doc string.. :-) \$\endgroup\$ Commented Jul 13, 2014 at 21:09

2 Answers 2

Reset to default
2
\$\begingroup\$

Nice docstring.

Your loop is too complicated, and not idiomatic Python. Use range(n) to repeat n times:

def repeated(f, n):
    """Docstring here"""
    def g(x):
        for _ in range(n):
            x = f(x)
        return x
    return g

Your repeated() function works fine for functions that accept a single argument, like square(x) (which could just be written x * x, by the way). However, it fails for higher-arity functions, such as

def fib_iter(a, b):
    return b, a + b

To handle multi-argument functions…

def repeated(f, n):
    """Docstring here"""
    def g(*x):
        for _ in range(n):
            x = f(*x) if isinstance(x, tuple) else f(x)
        return x 
    return g

However, there is a bug in that: repeated(square, 0)(2) would return a tuple (2,) rather than an int 2. To work around that special case…

def repeated(f, n):
    """Docstring here"""
    def g(*x):
        for _ in range(n):
            x = f(*x) if isinstance(x, tuple) else f(x)
        return x

    def unpack(*x):
        result = g(*x)
        if isinstance(result, tuple) and len(result) == 1:
            return result[0]
        else:
            return result

    return unpack
\$\endgroup\$
8
  • \$\begingroup\$ The challenge itself states f is a function that takes only one numerical argument. \$\endgroup\$ Commented Jul 13, 2014 at 21:21
  • \$\begingroup\$ @200_success What is *x in def g(*x), is it a pointer? \$\endgroup\$ Commented Jul 15, 2014 at 7:23
  • \$\begingroup\$ In def g(*x), the * operator lets g accept arbitrary arguments — x in this case will be a list containing any and all arguments. In f(*x), the * operator has the inverse effect of unpacking the argument list — instead of calling f with a single argument that is a list, let the first element of the list be the first argument, the second element of the list be the second argument, etc. \$\endgroup\$ Commented Jul 15, 2014 at 7:35
  • \$\begingroup\$ @200_success Do you think this x = f(*x) will work? If i have print(repeated(add3, 4)(1, 2, 3)) where def add3(x, y, z): return x + y + z ? i see this error, becasue we are passing tuple x = f(*x) if isinstance(x, tuple) else f(x) TypeError: add3() takes exactly 3 arguments (1 given) \$\endgroup\$ Commented Jul 15, 2014 at 7:41
  • \$\begingroup\$ Repeating only makes sense when the function that is being called repeatedly returns as many values as it accepts. Your add3(x, y, z) returns a single scalar, so it is not repeatable. \$\endgroup\$ Commented Jul 15, 2014 at 7:43
1
\$\begingroup\$

Old question, but I feel that the functional way, involving lambda and reduce, could be mentioned:

def repeated(f, n):
    return lambda seed: reduce(lambda x, _: f(x), range(n), seed)

assert repeated(lambda x: x*x, 4)(5) == 152587890625

Although not especially pythonic, it is rather concise.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.