In part 1, we saw how defining functions as sets of recursive equations lets us prove their correctness, using structural induction. In this article, we’ll examine the second big thing that recursion enables: performance. To get at how this is the case, let’s first look at special-purpose tools that use laziness to avoid unnecessary work.

A long time ago, in a registry far far away, there was a little compile-to-JavaScript language called CoffeeScript. Before JavaScript had modules and everything was built using Webpack, a common method for building client-side code was to run each file through the CoffeeScript compiler, and then concatenate all the resulting files. (Modern build tooling still essentially does this, it’s just substantially more complicated.) One could quite happily write a short shell script to build one’s project:

#!/bin/bash

mkdir -p compiled

for file in $(find src -name '*.coffee') ; do
  ./bin/coffee -co compiled $file
done

cat compiled/*.js > coffee-script.js

In keeping with our theme, the CoffeeScript compiler is itself written in CoffeeScript, and running this build process over its codebase on my computer takes about 7 seconds.

$ time ./build.sh

real    0m6.975s

Now, let’s write the same build process using Make. Here sources is a list of all the .coffee files in the src directory, and outputs is the result of replacing the pattern src/%.coffee with compiled/%.js in sources. We declare that coffee-script.js is derived from outputs by concatenating those files, and each compiled file compiled/%.js is derived from the corresponding src/%.coffee file by running the coffee compiler.

sources := $(shell find src -name '*.coffee')
outputs := $(sources:src/%.coffee=compiled/%.js)

coffee-script.js: $(outputs)
	cat $^ > $@

compiled/%.js: src/%.coffee compiled
	./bin/coffee -co $(dir $@) $<

compiled:
	mkdir -p $@

When we run this, it does all the same things the shell script does, and takes about the same amount of time.

$ time make
mkdir -p compiled
./bin/coffee -co compiled/ src/optparse.coffee
./bin/coffee -co compiled/ src/lexer.coffee
./bin/coffee -co compiled/ src/register.coffee
./bin/coffee -co compiled/ src/repl.coffee
./bin/coffee -co compiled/ src/nodes.coffee
./bin/coffee -co compiled/ src/cake.coffee
./bin/coffee -co compiled/ src/browser.coffee
./bin/coffee -co compiled/ src/coffeescript.coffee
./bin/coffee -co compiled/ src/index.coffee
./bin/coffee -co compiled/ src/rewriter.coffee
./bin/coffee -co compiled/ src/helpers.coffee
./bin/coffee -co compiled/ src/command.coffee
./bin/coffee -co compiled/ src/grammar.coffee
cat compiled/optparse.js compiled/lexer.js compiled/register.js \
    compiled/repl.js compiled/nodes.js compiled/cake.js compiled/browser.js \
    compiled/coffeescript.js compiled/index.js compiled/rewriter.js \
    compiled/helpers.js compiled/command.js compiled/grammar.js >
    coffee-script.js

real    0m7.092s

However, if we change one file, and run make again, then only that file is recompiled and concatenated with the existing compiled files, taking less than a second.

$ touch src/lexer.coffee

$ time make
./bin/coffee -co compiled/ src/lexer.coffee
cat compiled/optparse.js compiled/lexer.js compiled/register.js \
    compiled/repl.js compiled/nodes.js compiled/cake.js compiled/browser.js \
    compiled/coffeescript.js compiled/index.js compiled/rewriter.js \
    compiled/helpers.js compiled/command.js compiled/grammar.js >
    coffee-script.js

real    0m0.835s

If we change a few files, those are recompiled and concatenated with the existing files. But, note that Make compiles them sequentially, and it takes 1.9 seconds.

$ touch src/{grammar,helpers,lexer}.coffee

$ time make
./bin/coffee -co compiled/ src/lexer.coffee
./bin/coffee -co compiled/ src/helpers.coffee
./bin/coffee -co compiled/ src/grammar.coffee
cat compiled/optparse.js compiled/lexer.js compiled/register.js \
    compiled/repl.js compiled/nodes.js compiled/cake.js compiled/browser.js \
    compiled/coffeescript.js compiled/index.js compiled/rewriter.js \
    compiled/helpers.js compiled/command.js compiled/grammar.js >
    coffee-script.js

real    0m1.906s

However if we pass the option -j 3 (which means “run at most 3 concurrent jobs”) to make, the compilations run in parallel and when all of them are done, the results are concatenated. The parallelisation reduces the run time to 1.2 seconds.

$ touch src/{grammar,helpers,lexer}.coffee

$ time make -j 3
./bin/coffee -co compiled/ src/lexer.coffee
./bin/coffee -co compiled/ src/helpers.coffee
./bin/coffee -co compiled/ src/grammar.coffee
cat compiled/optparse.js compiled/lexer.js compiled/register.js \
    compiled/repl.js compiled/nodes.js compiled/cake.js compiled/browser.js \
    compiled/coffeescript.js compiled/index.js compiled/rewriter.js \
    compiled/helpers.js compiled/command.js compiled/grammar.js >
    coffee-script.js

real    0m1.245s

This happens because we’ve described the structure of the process to Make, rather than writing it as one opaque procedure. coffee-script.js, depends on all the files matching compiled/%.js, which themselves are each generated from a corresponding src/%.coffee file. This means Make can figure out which parts of the tree are out of date, based on their ancestors having been updated. It can also spot tasks that don’t depend on each other, like compiling each file, and automatically parallelises them, while making things that do depend on other tasks wait for those tasks to finish.

grammar.coffee    helpers.coffee    lexer.coffee
       |                |                 |
       |                |                 |
       v                v                 v
  grammar.js        helpers.js        lexer.js
       |                |                 |
       |                |                 |
       +----------------+-----------------+
                        |
                        v
                 coffee-script.js

Make is a special-purpose tool, tailor-made for generating files from other files. Some functional languages like Haskell apply this idea of laziness to general computation, and they do it by making use of recursion.

We’ve already seen the recursive definition of map, now we’re going to use two new functions: filter and !!. Filtering an empty list gives an empty list, and filtering any other list either keeps or drops the first element based on whether the predicate returns true. !! gets the nth element of a list; when called with 0 it returns the first element, and when called with any other integer it recurses by dropping the first element and reducing n by 1.

map               :: (a -> b) -> [a] -> [b]
map _ []          =  []
map f (x:xs)      =  f x : map f xs

filter            :: (a -> Bool) -> [a] -> [a]
filter _ []       =  []
filter p (x:xs)
    | p x         =  x : filter p xs
    | otherwise   =  filter p xs

(!!)              :: [a] -> Int -> a
(x:xs) !! 0       =  x
(x:xs) !! n       =  xs !! (n - 1)

Let’s say we want to get element number 2 of the list of squares of the even numbers. In JavaScript we might write this as:

numbers.filter((n) => n % 2 == 0).map((n) => n * n)

Now suppose that numbers is an infinite list. Haskell natively supports infinite lists, and in JavaScript one could simulate them using generators. In a language without lazy evaluation, the filter() call will first try to completely process its input, and it will never return as it loops trying to reach the end of an infinite list. However, the way Haskell defines functions lets it evaluate such an expression slightly differently.

The expression we want to evaluate is shown below. (^ 2) is the notation for a function that squares its input, even takes a number and returns True or False, and [1..] denotes the infinite list of integers counting from 1.

    (map (^ 2) (filter even [1..])) !! 2

As we did before, let’s use the function definitions as rewrite rules and start to transform this expression. The list can be decomposed into 1 paired with an infinite list beginning with 2:

    (map (^ 2) (filter even (1 : [2..]))) !! 2

Then, by the definition of filter, we drop the 1 because even 1 is False.

    (map (^ 2) (filter even [2..])) !! 2

The next list element is 2, and we can pull this out in front of filter because even 2 is True. That leaves [3..] inside the filter expression.

    (map (^ 2) (2 : filter even [3..])) !! 2

Now we have an expression in the form (map f (x : xs)), which we know transforms into (f x : map f xs). Notice we don’t square the 2 yet: we just pull the 2 through the map expression and retain the 2 ^ 2 expression, unevaluated.

    (2 ^ 2 : map (^ 2) (filter even [3..])) !! 2

We now have an expression of the form (x : xs) !! n, so by the definition of !!, we drop this term from the list and reduce n to 1. We never actually called the squaring function, and in fact if you trace the execution of this example you’ll see it won’t get called on the first element.

    (map (^ 2) (filter even [3..])) !! 1

Running this process again, we drop the 3, keep the 4, pull 4 ^ 2 out of the map, then drop it and reduce n to 0.

    (map (^ 2) (filter even [3..])) !! 1
  = (map (^ 2) (filter even (3 : [4..]))) !! 1
  = (map (^ 2) (filter even [4..])) !! 1
  = (map (^ 2) (4 : filter even [5..])) !! 1
  = (4 ^ 2 : map (^ 2) (filter even [5..])) !! 1
  = (map (^ 2) (filter even [5..])) !! 0

One last time, we drop the 5, keep the 6, square it, and then by the definition of !! this time we keep the first element, rather than the rest of the list. Now we evaluate this element since we actually want to use it, getting 36.

    (map (^ 2) (filter even [5..])) !! 0
  = (map (^ 2) (filter even (5 : [6..]))) !! 0
  = (map (^ 2) (filter even [6..])) !! 0
  = (map (^ 2) (6 : filter even [7..])) !! 0
  = (6 ^ 2 : map (^ 2) (filter even [7..])) !! 0
  = 6 ^ 2
  = 36

Two interesting things happened here: we managed to process data from an infinite list without iterating over the whole thing, and we avoiding evaluating things we weren’t going to use. Haskell can do this because its functions are expressed as recursive structures, rather than procedures that must run to completion before returning. Each time we transform an expression we’re taking one step through an iteration, and then seeing if any other transformations can be applied. We’re not running an whole loop to completion inside one function before doing any other work.

In the previous article we saw the function composition law, which says:

    map f (map g list) == map (f . g) list

This is a useful result because it tells us we can iterate over the list just once, rather than once for each function. But this isn’t a special case: all lazy list operations work this way. Rather than filter iterating over the whole list, and then map doing the same thing, the two functions work in tandem and there is only one iteration that steps through the expression until it finds the result we asked for. Anything that’s not necessary to produce that result is discarded.

Lazy constructs do exist in other languages. Ruby has lazy enumerators, Rust’s Iterator is lazy, and Node.js streams can be used to implement laziness (see my talk, Practical functional programming). However, in those languages it is only those constructs that are lazy. For example, take this Rust program:

fn main() {
    let mut squares = (1..).map(|n| {
        println!("squaring {}", n);
        n * n
    });

    println!("{:?}", squares.nth(20).unwrap());
}

Before printing the final result of 441, this will print squaring 1, squaring 2, squaring 3 and so on, all the way up to squaring 21. The map function is lazy as it only processes enough elements from 1.. to satisfy the nth call, and it can collapse chained map and filter calls into a single iteration, but the closure passed to map is called for every item, even though all but the last result is not used. In contrast, take this Haskell program:

import Debug.Trace

square n =
    trace ("squaring " ++ show n) n * n

main = do
    let squares = map square [1..]
    print (squares !! 20)

The entire output of this program is:

squaring 21
441

It only runs the square function for the list element the program is actually going to use. In Haskell, laziness applies to all computations, and this is possible because it defines functions as recursive equations. Just as Make uses its knowledge of your build structure to make sure it only rebuilds things that have changed, Haskell uses the structure of these equations to work backwards from your program’s output instructions to find the expressions that are essential to produce that output. It means each function, especially functions that work with lists or trees, can be evaluated just for the next element of the list, rather than for the entire list, before further work can be done on the expression, and this is an essential component in evaluating functional programs efficiently.

In the next and final part of this series we’ll see how recursive definitions let us better express the meaning of our programs, and we’ll meet logic programming and the idea of running functions backwards.