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\$
  • \$\begingroup\$ Agreed. +1 for the doc string.. :-) \$\endgroup\$ – fr00z1 Jul 13 '14 at 21:09
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\$
  • \$\begingroup\$ The challenge itself states f is a function that takes only one numerical argument. \$\endgroup\$ – Mephy Jul 13 '14 at 21:21
  • \$\begingroup\$ @200_success What is *x in def g(*x), is it a pointer? \$\endgroup\$ – overexchange Jul 15 '14 at 7:23
  • \$\begingroup\$ In def g(*x), the * operator lets g accept arbitrary argumentsx 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\$ – 200_success Jul 15 '14 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\$ – overexchange Jul 15 '14 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\$ – 200_success Jul 15 '14 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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.