# Application of higher-order function in Python

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
"""


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?

• Agreed. +1 for the doc string.. :-) Jul 13, 2014 at 21:09

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
else:
return result

return unpack

• The challenge itself states f is a function that takes only one numerical argument. Jul 13, 2014 at 21:21
• @200_success What is *x in def g(*x), is it a pointer? Jul 15, 2014 at 7:23
• 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. Jul 15, 2014 at 7:35
• @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) Jul 15, 2014 at 7:41
• 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. Jul 15, 2014 at 7:43

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.