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:

1
2
3
4

def fix[A](f: (=> A) => A): A = {
lazy val a: A = f(a)
a
}

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.

# Further Reading

The idea of fixed-point combinator is also applicable to types. It is possible to rewrite a recursive type into an equivalent, non-recursive type using a fixed-point type constructor. Matryoshka is a library for working with fixed-point types.