From Fixed Points to Recursion

Recursion refers to self-referential code. Most people are familiar with recursion in the form of names that are used before their values are fully computed. The classic Fibonacci function can be used to illustrate this. As you can see, the definition of fib references itself.

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

The fix function in Haskell calculates the least fixed point of the function provided as argument, if it exists. From numerical analysis, you may recall a fixed point as a value at which the output remains unaltered no matter how many times you apply the function to it. In other words, the following statement is true for all f, for which the fix function can be computed:

f (fix f) = fix f

To use the fix function, we first need to a redefine fib as a function that can be supplied to it. We define a new variable f that represents the Fibonacci function, moving fib over to the right side.

let f = \fib -> \n -> if n < 2 then n else fib (n - 1) + fib (n - 2)

In plain English, you could read this as: given the Fibonacci function and a number, we can calculate the value as (a) the number itself if it is less than 2, or (b) the sum of the Fibonacci function applied to the previous two numbers respectively.

Notice that the definition above no longer uses recursion; it simply accepts fib and n as arguments, and calculates the result.

We now find the least fixed point for the Fibonacci function, and apply it to the desired input. For instance, to find the 11^th Fibonacci number, we write:

import Data.Function (fix)
fix f 11

…and voila! it prints the result 89.

If you open up the source code of fix, this is how it is defined:

fix :: (a -> a) -> a
fix f = let x = f x in x

Again, in plain English, replace x with the supplied function f applied to (f applied to (f applied to (…))), then return x. You would think this would go into an infinite loop — and it does, if the function doesn’t converge — but it actually works! One of the advantages of a language with non-strict evaluation semantics like Haskell is the ability to work effectively with infinite regress.

Link to GitHub

That’s all for today, folks! 🖖