Functional programming approach to repeated function application

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:

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

-
Can the naming conventions and error handling be better?

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!

StackExchange Code Review Q#80524, answer score: 4