## 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 the paper *Research Topics in Functional Programming*:

http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf

This discussion of functional programming in general is profound. There are several examples given in the paper. We'll look at just one: the Newton-Raphson algorithm for locating the roots of a function. In this case, the function is the square root.

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)`

method and calculates a next value that brackets the proper root. Take a look at the following example:

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

This function computes a series of values

. The distance between the values is halved each time, so they'll quickly converge on the value such that

, which means

. 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 Command Prompt:

**>>> 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've defined the `f()`

method as a `lambda`

that will converge on

. We started with 1.0 as the initial value for

. Then we evaluated a sequence of recursive evaluations:

,

, and so on. We evaluated these functions using a generator expression so that we could round off each value. This makes the output easier to read and easier to use with `doctest`

. The sequence appears to converge rapidly on

.

We can write a function, which will (in principle) generate an infinite sequence of

values converging on the proper square root:

def repeat(f, a): yield a for v in repeat(f, f(a)): yield v

This function will generate 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.

### Note

The `repeat()`

function expects the `f()`

function to have a single argument; however, our `next_()`

function has two arguments. We can use 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 the sequence of 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`

loop as follows:

for x in some_iter: yield x.

- We can use the
`yieldfrom`

statement as follows:

yield from some_iter.

Both techniques of yielding the values of a recursive generator function are equivalent. We'll try to emphasize `yield from`

. In some cases, however, the `yield`

with a complex expression will be clearer than the equivalent mapping or generator expression.

Of course, we don't want the entire infinite sequence. It's essential to stop generating values when two values are so close to each other that either one is useful as the square root we're looking for. The common symbol for the value, which is close enough, is the Greek letter **Epsilon**, `ε`

, which can be thought of as the largest error we will tolerate.

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:

def within(ε, iterable): def head_tail(ε, a, iterable): 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 next item from the `iterable`

is bound to a name `b`

. If

, the two values are close enough together to find the square root. 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 merely seeks to properly initialize the internal `head_tail()`

function with the first value from the `iterable`

parameter.

Some functional programming languages offer a technique that will put a value back into an `iterable`

sequence. In Python, this might be a kind of `unget()`

or `previous()`

method that pushes a value back into the iterator. Python iterables don't offer this kind of rich functionality.

We can use the three functions `next_()`

, `repeat()`

, and `within()`

to create a square root function, as follows:

def sqrt(a0, ε, n): return within(ε, repeat(lambda x: next_(n,x), a0))

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 `ε`

.

When we use this version of the `sqrt()`

method, we need to provide an initial seed value, `a0`

, and an `ε`

value. An expression such as `sqrt(1.0, .0001, 3)`

will start with an approximation of 1.0 and compute the value of

to within 0.0001. For most applications, the initial `a0`

value can be 1.0. However, the closer it is to the actual square root, the more rapidly this method converges.

The original example of this approximation algorithm was shown in the Miranda language. It's easy to see that there are few profound differences between Miranda and Python. The biggest difference is Miranda's ability to construct `cons`

, turning a value back into an `iterable`

, doing a kind of `unget`

. This parallelism between Miranda and Python gives us confidence that many kinds of functional programming can be easily done in Python.