ZWA

Let’s say we want to implement the good old factorial function but we do not want to use recursion. Instead we will write an infinite number of custom factorial functions that take just one value:

fact0 = 1
fact1 = 1 * fact0
fact2 = 2 * fact1
fact3 = 3 * fact2
fact4 = 4 * fact3
.
.
.

This will work fine, it is just a little inconvenient since it is, well infinite. But maybe we can functionalize it by writing a factR that creates a factorial function with the factorial function for N − 1 as an input.

factR <- function(r){
	function(n){
		if (n == 0){
			1
		} else {
			n * r(n - 1)
		}
	}
}

What values do we use for r? We can create the r function with factR:

For !0:

R> factR(NULL)(0)
1

We pass in a NULL function. If this function is called, then an error will be raised. But it isn’t called since n = 1 and thus 1 is returned. If instead we input 1:

R> factR(NULL)(1)
Error in r(n - 1) : could not find function "r"

We need to go deeper.

R> factR(factR(NULL))(1)
1

What about 2, 3, 4?

R> factR(factR(factR(NULL)))(2)
2
R> factR(factR(factR(factR(NULL))))(3)
6
R> factR(factR(factR(factR(factR(NULL)))))(4)
24

So long as the factR fnctions are nested deeper than the input n, the expression evaluates correctly. But writing these deeply nested expressions is tedious. So let’s write a function to do it for us:

kfunctions <- function(k, f){
	if(k < 1){
		error("k must be greater than or equal to 1")
	}
	fs = list()
	for(i in 1:k){
		fs[[i]] = f
	}
	Reduce(function(x, r){r(x)}, fs, NULL)
}

There is nothing in kfunctions that is specific to the factorial function, so we just call the input function f. The only requirement is that f MUST be a function that takes a function as an argument and returns a new function. Now we can use kfunctions(3,factR) as a short cut for factR(factR(factR(NULL))). For the case of factorial, where it is easy to calculate the required recursive depth, we could write the factorial solution:

fact <- function(n){
	kfunctions(n+1, factR)(n)
}

This new fact function will work neatly for any number. But what if we don’t know how deeply we need to recurse? What we need is something like kfunction but that can be infinite. Fortunately, R happens to be lazy, so inifinity plays nicely.

fix <- function(f){
	f( fix(f) )
}

The function fix encapsulates the notion of recursion. It takes a non-recursive function and makes it recursive. The important thing to remember is that the non-recursive function must be a function that takes a function as an argument and returns a function.

Now we can write our factorial functions as:

fact <- fix(factR)

This solution is fully general, it will work for more complex recursive problems, such as calculating the fibonacci sequence which branches recursively:

fibR <- function(r) {
	function(n) {
		if (n == 0){
			1
		} else if (n == 1){
			1
		} else {
			r(n-1) + r(n-2)
		}
	}
}

fib = fix(fibR)

The reason fix does not fall into an infinite recursive loop is because of R’s laziness. r is an infinitely nest of fibR functions, but the thunk fix(f) is not evaluated until its value is needed, thus is remains finite and expands to f( fix(f) ) only when needed. So the evaluation rolls all the way down to the base cases of 0 and 1 and then wrap back up summing the values.

What is the point of all this? Well, we have factored recursion out of R. Now all recursive handling can be managed within one function. And we can modify this function to modify how recursion itself works. We can rewrite the fix function to, for example, memoize intermediate values. And that is just the beginning. There are many more complex recursive patterns we can abstract from our code, but this is a topic for a future post.

Fixpoints in R