1.3 A classic example of functional programming

As part of our introduction, we’ll look at a classic example of functional programming. This is based on the paper Why Functional Programming Matters by John Hughes. The article appeared in a paper called Research Topics in Functional Programming, edited by D. Turner, published by Addison-Wesley in 1990.

Here’s a link to one of the papers in Research Topics in Functional Programming, “Why Functional Programming Matters”: http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf

This paper is a profound discussion of functional programming. There are several examples given. We’ll look at just one: the Newton-Raphson algorithm for locating any roots of a function. In this case, we’ll define a function that will compute a square root of a number.

It’s important because many versions of this algorithm rely on the explicit state managed via loops. Indeed, the Hughes paper provides a snippet of the Fortran code that emphasizes stateful, imperative processing.

The backbone of this approximation is the calculation of the next approximation from the current approximation. The next_() function takes x, an approximation to the sqrt(n) value, and calculates a next value that brackets the proper root. Take a look at the following example:

def next_(n: float, x: float) -> float: 
    return (x + n / x) / 2

This function computes a series of values that will quickly converge on some value x such that x = , which means x = .

Note that the name next() would collide with a built-in function. Calling it next_() lets us follow the original presentation as closely as possible, using Pythonic names.

Here’s how the function looks when used in Python’s interactive REPL:

>>> n = 2 
>>> f = lambda x: next_(n, x) 
>>> a0 = 1.0 
>>> [round(x, 4) 
... for x in (a0, f(a0), f(f(a0)), f(f(f(a0))),) 
... ] 
[1.0, 1.5, 1.4167, 1.4142]

We defined the f() function as a lambda that will converge on where n = 2. We started with 1.0 as the initial value for a₀. Then we evaluated a sequence of recursive evaluations: a₁ = f(a₀), a₂ = f(f(a₀)), and so on. We evaluated these functions using a generator expression so that we could round each value to four decimal places. This makes the output easier to read and easier to use with doctest. The sequence appears to converge rapidly on . To get a more precise answer, we must continue to perform the series of steps after the first four shown above.

We can write a function that will (in principle) generate an infinite sequence of a_i values. This series will converge on the proper square root:

from collections.abc import Iterator, Callable 
def repeat( 
        f: Callable[[float], float], 
        a: float 
) -> Iterator[float]: 
    yield a 
    yield from repeat(f, f(a))

This function will generate a sequence of approximations using a function, f(), and an initial value, a. If we provide the next_() function defined earlier, we’ll get a sequence of approximations to the square root of the n argument.

The repeat() function expects the f() function to have a single argument; however, our next_() function has two arguments. We’ve used a lambda object, lambda x: next_(n, x), to create a partial version of the next_() function with one of two variables bound.

The Python generator functions can’t be trivially recursive; they must explicitly iterate over the recursive results, yielding them individually.

Attempting to use a simple return repeat(f, f(a)) will end the iteration, returning a generator expression instead of yielding values.

There are two ways to return all the values instead of returning a generator expression, which are as follows:

• We can write an explicit for statement to yield values as follows:

  for x in some_iter: yield x

• We can use the yield from expression as follows:

  yield from some_iter

Both techniques of yielding the values of a recursive generator function are will have similar results. We’ll try to emphasize yield from.

It turns out that yield and yield from are a bit more sophisticated than we’ve shown here. For our purposes, we’ll limit ourselves to working with recursive results. For more information on the full feature set for yield and yield from, see PEP 342 and PEP 380: https://peps.python.org/pep-0342/ and https://peps.python.org/pep-0380/.

Of course, we don’t want the entire infinite sequence created by the repeat() function. It’s essential to stop generating values when we’ve found the square root we’re looking for. The common symbol for the limit we can consider “close enough” is the Greek letter epsilon, 𝜖.

In Python, we have to be a little clever when taking items from an infinite sequence one at a time. It works out well to use a simple interface function that wraps a slightly more complex recursion. Take a look at the following code snippet:

from collections.abc import Iterator 
def within( 
        𝜖: float, 
        iterable: Iterator[float] 
) -> float: 
    def head_tail( 
            𝜖: float, 
            a: float, 
            iterable: Iterator[float] 
    ) -> float: 
        b = next(iterable) 
        if abs(a-b) <= 𝜖: 
            return b 
        return head_tail(𝜖, b, iterable) 
 
    return head_tail(𝜖, next(iterable), iterable)

We’ve defined an internal function, head_tail(), which accepts the tolerance, 𝜖, an item from the iterable sequence, a, and the rest of the iterable sequence, iterable. The first item from the iterable, extracted with the next() function, is bound to a name, b. If |a − b|≤ 𝜖, the two values of a and b are close enough to call the value of b the square root; the difference is less than or equal to the very small value of 𝜖. Otherwise, we use the b value in a recursive invocation of the head_tail() function to examine the next pair of values.

Our within() function properly initializes the internal head_tail() function with the first value from the iterable parameter.

We can use the three functions, next_(), repeat(), and within(), to create a square root function, as follows:

def sqrt(n: float) -> float: 
    return within( 
        𝜖=0.0001, 
        iterable=repeat( 
            lambda x: next_(n, x), 
            1.0 
        ) 
    )

We’ve used the repeat() function to generate a (potentially) infinite sequence of values based on the next_(n,x) function. Our within() function will stop generating values in the sequence when it locates two values with a difference less than 𝜖.

This definition of the sqrt() function provides useful default values to the underlying within() function. It provides an 𝜖 value of 0.0001 and an initial a₀ value of 1.0.

A more advanced version could use default parameter values to make changes possible. As an exercise, the definition of sqrt() can be rewritten so an expression such as sqrt(1.0, 0.000_01, 3) will start with an approximation of 1.0 and compute the value of to within 0.00001. For most applications, the initial a₀ value can be 1.0. However, the closer it is to the actual square root, the more rapidly this algorithm converges.

The original example of this approximation algorithm was shown in the Miranda language. It’s easy to see there are some profound differences between Miranda and Python. In spite of the differences, the similarities give us confidence that many kinds of functional programming can be easily implemented in Python.

The within function shown here is written to match the original article’s function definition. Python’s itertools library provides a takewhile() function that might be better for this application than the within() function. Similarly, the math.isclose() function may be better than the abs(a-b) <= 𝜖 expression used here. Python offers a great many pre-built functional programming features; we’ll look closely at these functions in Chapter 8, The Itertools Module and Chapter 9, Itertools for Combinatorics – Permutations and Combinations.