Application of higher-order function in Python

Question

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?

Answer 1

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

Answer 2

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.