Why Functional Programming Matters

We can start with one function that we'll call reduce, which is used to process lists. reduce is a function that recursively iterates through a list, applies a specialized function to each element to the list, and returns the value of the applied function up the recursive stack. Reduce looks like

(reduce f value)

Where f is a specializing function, and value is the base case value for the recursion. When applied to f and value, reduce returns a function awaiting a list. We can use reduce to create a function that sums up a list of numbers.

sum = reduce add 0
sum [1 2 3 4] // evaluates to 10

The call stack looks like (add 1(add 2 (add 3 (add 4 0)))).

We can use reduce to create a copy of a list.

copy = reduce cons []
copy [1 2 3 4] // evaluates to [1 2 3 4]

The function cons takes two arguments, a value and a list, and puts the value on the front of the list. And for the base case of the recursion, we give it an empty list. The call stack looks like (cons 1 (cons 2 (cons 3 (cons 4 [])))) which gives us the list [1 2 3 4].

We can use reduce to implement map. Map applies a function to each element of a list, and returns a new list of the values of those applied functions.

fandcons = cons . f
map = reduce fandcons []

double x = 2 * x
map double [1 2 3 4] // evaluates to [2 4 6 8]

Note: The "⋅" operator is function composition. (f ⋅ g) h is equivalent to f (g h).

Reduce shows us how you can glue modular functions together to create more powerful functions. Reduce is a generic function that knows how to operate on a list, and it applies the provided specializing function to each element of the list.

The ideas here can also be applied to other data structures other than lists. The paper covers redtree, a function similar to reduce except that it operates on trees. With redtree we can implement sumtree and maptree very similar to how we did with lists.

Whenever a new data structure is defined, new higher order functions should be written to process it. This makes it easy to process and encapsulates the details of the implementation.

We can take advantage of this by implementing the Newton-Raphson square roots algorithm. The algorithm works by starting with an initial approximation for the square root of a number which we'll call a₀. From that initial approximation, we can come up with better and better ones using the rule:

a(n+1) = (a(n) + N/a(n)) / 2

If the approximations approach some limit a, then a is the square root of N. If we provide a tolerance and stop the approximation once two successive approximations differ by less than the tolerance, we can approximate the square root. Using a typical programming language it would be programmed iteratively in a loop like the following:

sqrt(tol, a0, N) {
  x = a0
  y = a0 + 2*tol
  while(true) {
    if (abs(x - y) < tol) {
      return x;
    }
    y = x;
    x = (x + N/x) / 2;
  }
}

Unfortunately, the sqrt function is indivisible when written like this. Using lazy evaluation we can write it in a modular fashion and reuse those parts in other code.

First we define the function next which computes an approximation when given the previous one:

next N x = (x + N/x) / 2

Next we define a function repeat which will repeatedly call a function with the result of the previous call to the function in order to build a list:

repeat f a = cons a (repeat f (f a))

Then we can build our list of square root approximations:

repeat (next N) a0

Our list is an example of an infinite list. It can potentially create output forever. But because of lazy evaluation, approximations will only be computed as needed.

The last part we need is the function within, which is an example of a selector. The selector is a function which will iterate through the infinite list until subsequent approximations are within the tolerance.

within tol (cons a (cons b rest)) = b if abs(a - b) <= tol
                                  = within tol (cons b rest) otherwise

Now we can glue these 3 functions into a new function which approximates the square root of a number.

sqrt a0 tol N = within eps (repeat (next N) a0)

It's clear how much more modular this is than the original solution. We've broke it down into 3 sub-problems: a function that creates an approximation (next), a function that repeatedly calls it (repeat), and a function that tests for the termination condition (within) and glued them together to solve a specific problem. We can leverage those functions in many other solutions outside of approximating square roots.

In artificial intelligence there's an algorithm that estimates how good of a position a game player is in, called the alpha-beta heuristic. It looks ahead to see how the game might develop, but avoids looking ahead on moves that are not beneficial. To implement the alpha-beta heuristic we can use a game tree to represent the state of a game.

The tree contains the current game state at the root, and its childen are the possible moves from the current state to another state.

Lazy evaluation is important here because sometimes game trees are infinite in size or too big to hold in memory.

Lazy evaluation allows you to evaluate portions of the tree at a time, and when those portions have been evaluated, they are garbage collected. Only the portion being evaluated needs to be in memory at a given time which makes it possible to operate on huge, or even infinite trees.

The implementation of the alpha-beta heuristic plays out similar to the square root algorithm, so refer to the paper for the details. What's interesting though, is that the paper goes through several iterations of optimization on the algorithm which are great examples of the type of modularization made possible by higher order functions and lazy evaluation.

The paper also walk through a couple of more examples, including numerical differentiation through approximation and numerical integration through approximation.