Fixed-point combinator is a really cool thing. It allows us to encode recursion in lambda calculus, which doesn’t have built-in support for recursion. Computerphile recently made a video featuring professor Graham Hutton, author of the book “Programming in Haskell”, giving a brief introduction to the Y combinator.

The Y combinator can encode recursion because for all term `f`, `Y f = f (Y f)`. This means that whenever we want to encode a recursive function:

``````f = <body containing f>
``````

We simply bind `f` with `λ`, i.e., define

``````g = λf. <body containing f>
``````

This removes the recursion - `g` is no longer recursive because `f` is now a parameter of `g`. Then, `Y g` is exactly what we want.

# Factorial via fix

Scalaz has a quite elegant implementation of the fixed-point combinator, making use of lazy value and call-by-name parameter:

To understand how this works, just remember that every time we need to evaluate `a`, we’ll replace it with `f(a)` where `a` is a call-by-name parameter to `f`.

Let’s try to implement the factorial function using `fix`. To do so, we can use an approach similar as encoding recursive functions in lambda calculus with the Y combinator: bind the function with `λ`. That is, we turn the original factorial function,

``````val fac: Int => Int = n => if (n == 0) 1 else n * fac(n - 1)
``````

which has type `Int => Int`, into

``````val gac = λfac: Int => Int. n => if (n == 0) 1 else n * fac(n - 1)
``````

This is obviously not valid Scala syntax; in Scala it basically is

``````val gac: (=> Int => Int) => Int => Int =
fac => n => if (n == 0) 1 else n * fac.apply(n - 1)
``````

which has type `(=> Int => Int) => Int => Int`. Then, passing it to the `fix` combinator will give us what we need.

Putting everything together, this is how we define the factorial function, `facF`, using the `fix` combinator:

``````val facF = fix[Int => Int](fac => n => if (n == 0) 1 else n * fac.apply(n - 1))
``````

`facF` is no longer a recursive function, unlike the original `fac` (indeed, there is no `facF` in its definition). This is what fixed-point combinator is about: encoding recursive computation without using recursion. In practice, this doesn’t really buy us anything, in particular, turning a recursive function into an equivalent non-recursive function using `fix` does not make the function stack-safe: if the original recursive function crashes with `StackOverflowError` on some input, the `fix` version will also crash with `StackOverflowError` on a similar sized input. One small benefit of `fix` is that when you turn a recursive function into the `fix` version, since the `fix` version is non-recursive, you are no longer required to give it a name, which can be handy in a few scenarios (after all, naming things is one of the hardest things in computer science).

Now let’s see what happens when we call `facF(3)`:

``````facF(3) = fix(gac)(3)
``````

What is `fix(gac)`? According to the definition of `fix`, `fix(gac)` returns some `a`, such that evaluating `a` will get us `gac(a)`. This means that when we evaluate `fix(gac)`, we get a `gac(fix(gac))`. So now we have

``````facF(3) = fix(gac)(3) = gac(fix(gac))(3)
``````

Note that the first parameter of `gac`, i.e., `=> Int => Int`, is a call-by-name parameter. This means that we will not continue to evaluate `fix(gac)` in `gac(fix(gac))(3)`. If it were a call-by-value parameter (`Int => Int`), we would have to keep expanding `fix(gac)` into `gac(fix(gac))`, leading to infinite recursion:

``````gac(gac(gac(gac(gac(...
``````

Instead, to evaluate `gac(fix(gac))(3)`, we enter the `gac` function. According to the definition of `gac`, we have

``````facF(3) = fix(gac)(3)
= gac(fix(gac))(3)
= 3 * fix(gac)(2)
``````

So now, we can just keep evaluating it until `n = 0`:

``````facF(3) = fix(gac)(3)
= gac(fix(gac))(3)
= 3 * fix(gac)(2)
= 3 * gac(fix(gac))(2)
= 3 * 2 * fix(gac)(1)
= 6 * fix(gac)(1)
= 6 * gac(fix(gac))(1)
= 6 * 1 * fix(gac)(0)
= 6 * fix(gac)(0)
= 6 * gac(fix(gac))(0)
= 6 * 1
= 6
``````

Note that `gac(fix(gac))(0)` returns 1 directly, without evaluating the lazy parameter `fix(gac)`, hence the recursion terminates.