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?

• fr00z1: Agreed. +1 for the doc string.. :-)

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

• Mephy: The challenge itself states f is a function that takes only one numerical argument.
• overexchange: @200_success What is *x in def g(*x), is it a pointer?
• 200_success: 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.
• overexchange: @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)
• 200_success: 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.

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.