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.

Ziyang Liu's Haskell Blog

The fix Combinator in Scalaz

Factorial via fix

Further Reading