Functional programming approach to repeated function application

Question

Control like if..else and while

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

The solution is implemented using functional paradigm style, as shown below:

from operator import mul
from operator import pow
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(cube, 2)(5)
 1953125
 """
 assert n > 0
 def apply_n_times(x):
 count = n
 next_acc = f(x)
 count = count - 1
 while count > 0:
 next_acc = f(next_acc)
 count = count - 1
 return next_acc
 return apply_n_times
def square(x):
 return mul(x, x)
def cube(x):
 return pow(x, 3)
print(repeated(square, 0)(2))

My questions:

1. If the code looks correct from a programming style perspective, can I further optimize this code written in function repeated?

2. Can the naming conventions and error handling be better?

Answer 1

I see that you have grasped the concept of higher-order functions. To be more generalized, though, your repeat function should be able to handle n = 0 correctly too. That is, repeat(square, 0)(5) should return 5.

However, your solution is not written in the functional style, due to the use of count = count - 1. In fact, if you consider that such counting statements are forbidden in functional programming, you'll realize that iteration loops using while can't possibly be used in functional programming either. You are then left with recursion as the only viable approach. (Python isn't designed to do efficient or deep recursion, but as an academic exercise, we ignore such considerations.)

An exception is probably more appropriate than an assertion. You should assert conditions that you know to be true, not ones that you hope to be true.

It is customary to combine the two imports into a single import statement.

from operator import mul, pow
def repeat(f, n):
 def apply_n_times(n):
 if n < 0:
 raise ValueError("Cannot apply a function %d times" % (n))
 elif n == 0:
 return lambda x: x
 else:
 return lambda x: apply_n_times(n - 1)(f(x))
 return apply_n_times(n)

---

Note that lambda is merely a handy way to define an unnamed function on the spot. You could use explicitly named functions as well, but it would be less elegant.

def repeat(f, n):
 def identity(x):
 return x
 def apply_n_times(n):
 def recursive_apply(x):
 return apply_n_times(n - 1)(f(x))
 if n < 0:
 raise ValueError("Cannot apply a function %d times" % (n))
 elif n == 0:
 return identity
 else:
 return recursive_apply
 return apply_n_times(n)

• overexchange: If I would like to apply square one time, then I would say repeat(square, 1)(5) which gives the result 25. If I would like to apply square zero times, Isn't that mean that user do not require repeat functionality?
• 200_success: Yes, I would interpret repeat(any_function, 0) as the identity function — that is, a function that just passes through the parameter as the result.
• overexchange: Your point in second para about count and while is practically matching with the answer mentioned here
• overexchange: As we return implementation details to the user of repeat function; are we not breaking abstraction?

Answer 2

In terms of the functional programming paradigm, I would suggest the following for repeated:

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(cube, 2)(5)
 1953125
 """
 if n == 1:
 return f
 return lambda x: f(repeated(f, n-1)(x))

Note that, per the rule of thumb you have previously discussed, each statement can be replaced with its result and the function still works correctly.

You could also simplify the imports:

from operator import mul, pow

In terms of naming conventions, pylint doesn't like single-character names, so perhaps func and num would be better than f and n/x, but in general you don't have a problem here.

In terms of error handling, you don't currently have any. I don't think that's a problem either, though - the docstrings explain what the inputs are supposed to be, and the user should expect errors/weird behaviour if they supply anything else!

• overexchange: sorry, am yet to learn lambda expression. Can I think of this recursive approach without lambda?
• jonrsharpe: @overexchange you can also do it with a local def, i.e. def _repeat(x): return f(repeated(f, n-1)(x)); return _repeat. Any lambda can be replaced by a function.
• overexchange: Does these doc strings go in production code? I thought these doc strings are for the developers to perform Unit testing.
• jonrsharpe: Yes, you should certainly have docstrings in production code, but not necessarily with doctests (for example, if you auto generate API docs from the docstrings, you may not want them filled with tests). See e.g. github.com/textbook/py_wlc, where I've put the tests in a separate directory to keep the production code tidy, but still included docstrings.

Answer 3

This is odd:

count = n
next_acc = f(x)
count = count - 1
while count > 0:
 next_acc = f(next_acc)
 count = count - 1

Why assign n to count and then decrement it by 1 two lines later? Better to do it in one step.

And instead of x = x - 1, it's better to use x -= 1.

Putting these points together, the above code becomes:

next_acc = f(x)
count = n - 1
while count > 0:
 next_acc = f(next_acc)
 count -= 1

Actually you can go even further. Notice that you're writing f(...) twice, and in your original you did count = count - 1 twice. This suggests that probably it can be refactored to write these only once, making the code shorter and simpler. Thanks to the assert n > 0 before the function definition, this is equivalent to the original and simpler:

next_acc = x
count = n
while count > 0:
 next_acc = f(next_acc)
 count -= 1

Btw why is the variable called "next_acc". Perhaps next_x would be better.