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)

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!

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.