fix is an interesting Haskell function that provides us with the ability to add recursion to non recursive functions.

It looks like this:

fix :: (a -> a) -> a
fix f = f (fix f)

In the function fix, f will get the result of fix f as input, and will return some output of the same type. fix f represents another call to the function f, which f can call to recurse on itself.

Lets take a look at a few examples and use the substitution model to gain intuition on how this works.

id

Lets start by picking a function we can pass to fix. id :: a -> a has a matching signature, lets try it:

λ> fix id
^CInterrupted.

What happened? ghci was busy trying to evaluate the function and didn't finish, so I had to cancel it. Why? Lets try to substitute ourselves:

ג> fix id
~> id (fix id) -- substitute fix with it's body
~> (\a -> a) (fix id) -- substitute id with it's body
~> fix id -- apply (fix id) as a in (\a -> a)
~> id (fix id) -- substitute fix with it's body
~> ...

As we can see we have an infinite loop of steps where we keep coming back to fix id. This is because id always call fix id as part of the computation and therefore recursing.

(+) 1

Let's take a look at another example with (\x -> 1 + x) :: Int -> Int:

λ> fix (\x -> 1 + x)
*** Exception: stack overflow

Again, to understand what's going on - lets substitute:

ג> fix (\x -> 1 + x)
~> (\x -> 1 + x) (fix (\x -> 1 + x)) -- substitute fix with it's body
~> 1 + (fix (\x -> 1 + x)) -- apply
~> 1 + (\x -> 1 + x) (fix (\x -> 1 + x)) -- (+) and 1 are evaluated. we will evaluate the right hand side - the function call, by applying
~> 1 + (1 + (fix (\x -> 1 + x))) -- apply
~> ...

At each substitution of fix we add another step that needs to be done, so we keep allocating new thunks without evaluating them and we use all of the stack space. Here as well, we always use the argument x that is passed to us, so we keep recursing.

We'll see more useful examples later.

Non-Strict Semantics

One thing that we saw in previous examples is the evaluation order in Haskell. In a strict language, we first evaluate the arguments of a function, then we apply the arguments to the function's body, and then we evaluate the body of a function. But in Haskell, we evaluate computations only when we need to.

For example, take a look at the evaluation order of this function:

const :: a -> b -> a
const = \a -> \b -> a

Strict semantics:

ג> const (1 + 1) (2 + 2)
~> const 2 (2 + 2)
~> const 2 4
~> (\a -> \b -> a) 2 4
~> (\b -> 2) 4
~> 2

Notice how we evaluated 2 + 2 without actually needing to do anything with it.

Non-strict semantics:

ג> const (1 + 1) (2 + 2)
~> (\a -> \b -> a) (1 + 1) (2 + 2)
~> (\b -> (1 + 1)) (2 + 2)
~> (1 + 1)
~> 2

Pretty cool how we didn't evaluate (2 + 2) here, right?

This might sound silly, but what if (2 + 2) is instead a very expensive computation, or even one that never finished or throws an error? Non-strict semantics can help us ignore computations we don't really need, and it can be useful in the case of fix as we'll see next.

const 0

So let's take a look at another function with fix, this time we'll use (\x -> const 0 x) :: a -> Int:

ג> fix (\x -> const 0 x)
~> (\x -> const 0 x) (fix (\x -> const 0 x))
~> const 0 (fix (\x -> const 0 x))
~> (\a -> \b -> a) 0 (fix (\x -> const 0 x))
~> (\b -> 0) (fix (\x -> const 0 x))
~> 0

Hey what do you know! Non-strict semantics helped us avoid the unnecessary recursion and let us terminate the evaluation of the expression.

This is interesting. Because the arguments to a function are not evaluated before entering a function, the function can decide whether to evaluate the arguments or not (by using them, or not, like in the case of const). In our case with const, it will always ignore the argument x that is the recursion, so we really didn't use fix at all here.

factorial

Let's take a small leap and try to implement a factorial :: Int -> Int function without a recursive call to itself by using fix. Here we will sometimes call the recursion parameter passed to us from fix, and sometimes we won't.

factorial :: Int -> Int
factorial = fix impl

impl :: (Int -> Int) -> Int -> Int
impl recur n =
  if n <= 1
    then 1
    else n * recur (n - 1)

The key idea when using fix is that a can represent any type, including functions.

It's important to remember that functions are first class in Haskell, when we see an a, it could also be some function and not just a regular value like Bool.

So if we replace a with Int -> Int in the type signature for fix, we'll see that the function we pass to fix should now be of type (Int -> Int) -> Int -> Int, and the resulted type of applying fix to a function with that type would be Int -> Int.

So for example, what is fix impl? if we substitute fix with its body, we get: impl (fix impl), we know is that the first argument of impl is the result of fix impl :: Int -> Int,

which is a factorial function as we defined (and which we will evaluate only if we want to due to non-strict semantics), and the second argument should be the input to the function (the number for which we will calculate it's factorial).

Finally, let's evaluate this ourselves using the substitution model!

 0 ג> factorial 3
 1 ~> fix impl 3 -- substitute the body of factorial
 2 ~> impl (fix impl) 3 -- substitute the body of fix
 3 ~> (\recur -> \n -> if n <= 1 then 1 else n * recur (n - 1)) (fix impl) 3 -- substitute the body of impl
 4 ~> (\n -> if n <= 1 then 1 else n * fix impl (n - 1)) 3 -- apply (fix impl)
 5 ~> if 3 <= 1 then 1 else 3 * fix impl (3 - 1) -- apply 3
 6 ~> if False then 1 else 3 * fix impl (3 - 1) -- apply 3 -- evaluate the if condition
 7 ~> 3 * fix impl (3 - 1) -- choose the else branch
 8 ~> 3 * impl (fix impl) (3 - 1) -- (*) and 3 are evaluated, let's evaluate fix
 9 ~> 3 * (\recur -> \n -> if n <= 1 then 1 else n * recur (n - 1)) (fix impl) (3 - 1) -- substitute the body of impl
10 ~> 3 * (\n -> if n <= 1 then 1 else n * (fix impl) (n - 1)) (3 - 1) -- apply (fix impl)
11 ~> 3 * (if (3 - 1) <= 1 then 1 else (3 - 1) * (fix impl) ((3 - 1) - 1)) -- apply (3 - 1)
12 ~> 3 * (if    2    <= 1 then 1 else (3 - 1) * (fix impl) ((3 - 1) - 1)) -- evalute (3 - 1) in the if condition
13 ~> 3 * (if False then 1 else (3 - 1) * (fix impl) ((3 - 1) - 1)) -- evaluate the if condition
14 ~> 3 * ((3 - 1) * (fix impl) ((3 - 1) - 1)) -- choose the else branch
15 ~> 3 * (   2    * (fix impl) ((3 - 1) - 1)) -- (*) is evaluated, now we evaluate the left hand side of (*)
16 ~> 3 * (2 * impl (fix impl) ((3 - 1) - 1)) -- and now the right side - starting with (fix impl)
17 ~> 3 * (2 * (\recur -> \n -> if n <= 1 then 1 else n * recur (n - 1)) (fix impl) ((3 - 1) - 1)) -- and now the right side - starting with (fix impl)
18 ~> 3 * (2 * (\n -> if n <= 1 then 1 else n * (fix impl) (n - 1)) ((3 - 1) - 1)) -- apply (fix impl)
19 ~> 3 * (2 * (if ((3 - 1) - 1) <= 1 then 1 else ((3 - 1) - 1) * (fix impl) ( ((3 - 1) - 1) - 1))) -- apply ((3 - 1) - 1)
20 ~> 3 * (2 * (if (2 - 1) <= 1 then 1 else ((3 - 1) - 1) * (fix impl) ( ((3 - 1) - 1) - 1))) -- evaluating the if condition...
21 ~> 3 * (2 * (if 1 <= 1 then 1 else ((3 - 1) - 1) * (fix impl) ( ((3 - 1) - 1) - 1))) -- still evaluating ...
22 ~> 3 * (2 * (if True then 1 else ((3 - 1) - 1) * (fix impl) ( ((3 - 1) - 1) - 1))) -- still...
23 ~> 3 * (2 * 1) -- choosing the true branch
24 ~> 3 * 2 -- evaluating
25 ~> 6 -- evaluating

Bam! It was pretty long, but we did it.

One step in particular that I think is worth noting is line 23, where we discard the recursion branch in favor of the terminating branch. We chose to end the recursion!

Summary

We can use fix to add recursion to a non recursive function by getting as an input argument the a function that represents the recursion part. And the magic behind the termination of fix in Haskell resides with non-strict semantics.