This is one of those posts I write to ensure I actually understand a concept. Read at your own peril. Some knowledge of Haskell is required.

### The Problem

One Hello World problem that is sometimes used to demonstrate a programming language is generating the Fibonacci series. The nth Fibonacci number is given as:

```fib 0 = 1
fib 1 = 1
fib x = fib (x - 1) + fib (x - 2)
```

This, as it turns out, is one way to define the nth Fibonacci number in Haskell. Save this code as `Fib.hs`, start the GHC REPL as `ghci Fib.hs` and you’re done — `fib 5` evaluates to `8` and `fib 7` evaluates to `21`.

However, as cute this may be, it isn’t elegant enough. Fibonacci is essentially a series, and while mathematicians will tell you that a series is essentially a function (and that “is essentially” is a transitive relation) this definition does not, yet, sit quite well. Of course, you say, something like this can be done:

```fibSeries = map f [0..]
where
f 0 = 1
f 1 = 1
f x = f (x - 1) + f (x - 2)
```

Not only is this approach a hack but is also quite slow. One nice, canonical, way to define fibSeries is this:

```fibSeries = 1:1:zipWith (+) (tail fibSeries) fibSeries
```

Note the recursion here — the series of Fibonacci numbers remains the same if we take a list of two `1`s, and append it with the elementwise sum of the list of Fibonacci numbers and the list of Fibonacci numbers less the first element. Let this sink in.

### Enter the fixed point combinator.

There happens to be another, more elegant, way of expressing fibSeries, using `fix`, Haskell’s fixed point combinator. The above definition of `fibSeries` refers to itself in its definition. Let’s say you don’t want this, perhaps for pure intellectual pleasure (like here :P) or for deeper reasons — untyped lambda calculus, for instance, does not have named values, and so you cannot write an expression that refers to itself. In such cases, we use a fixed point combinator.

The first interesting thing about `fix` is its type: `:t fix` in `ghci` (fix is in `Data.Function`) will tell you its type is `(a->a)->a`. This should strike as counter-intuitive — how can a function possibly take a, say, `Integer->Integer` (let’s call this function `foo`) and return an `Integer`? It needs some value to apply `foo` to, right? The short answer is that `fix` calculates `foo`‘s fixed point. A slightly longer answer follows, which ends at TL;DR.

The fixed point of `foo` is the value `v` such that `foo v` equals `v`. It is fixed in the sense that no matter how many times we apply `foo` on the fixed point of `foo`, it remains fixed. One way to calculate the fixed point of `foo` is to apply it to `⊥` infinite number of times. This works because a type is a complete partial order and that `foo` is (Scott) continuous. In general the person defining `foo` needs to ensure this, but, thankfully, in Haskell, all functions you can possibly define are Scott Continuous. Relevant theory is here. Keeping this way of looking at `fix` in mind (infinite applications of `foo` on undefined), you could implement `fix` as:

```fix x = applyInfinitely x undefined
where
applyInfinitely f x = f (applyInfinitely f x)
```

There are other ways to define `fix`, of course. In an untyped lambda calculus, you can define it as `fix f = x -> f (x x)) (x -> f (x x)` (this is the famed Y combinator). If you’re well-versed with types, you could implement the Y combinator in Haskell too; but then you’ll have to depend on recursion at the type level. I like to think of `fix` as something that encapsulates recursion, allowing you to write expressions that don’t have any explicit recursion, but are recursive nevertheless.

### TL;DR

Coming back to the meaty aspects of `fix`, how do you write the function in whose fixed point is the value you want to compute? In this case we want `fix` to produce a `[Integer]`. This means the function we will write (`foo`) needs to have the type `[Integer]->[Integer]`. Which means it will take an `[Integer]` and return an `[Integer]`. But what `[Integer]` does it take? The same `[Integer]` it is supposed to return! As a first attempt, with this knowledge, you could write:

```fibSeries = fix (x->x)
```

I mean, since `fix`‘s argument (we’ll call it `foo` consistently) is somehow magically the same `[Integer]` `foo` is supposed to return, what could be more straightforward? However, something smells wrong. Both because of the word magically and the fact that this definition of `fibSeries` simply does not contain any information specific to the Fibonacci series (well, except the name `fibSeries`, but I think that is expecting too much of GHC :D). One thing I had not mentioned is this: when we say “fixed point” we really mean “least fixed point”. Deep in his or her heart, everyone who plays with types knows that a type is a poset with a bottom (`⊥`). The ordering in this poset is essentially information based — `A` > `B``A` has more information than `B`. So, in the poset of `Integer`s, `1` and `2` are incomparable, since both of them contain an equal amount of information. And then you have ⊥, which contains the least information of all. What is the least value (in terms of the “least” defined above) that can be the fixed point of `x->x` (the identity function)? `⊥`, of course! Since `(x->x) ⊥` is `⊥` and no doubt, `⊥` contains the least information of all by definition!

A more intuitive way of looking at this is that when constructing `foo`, you need to make sure it adds some information. You need to embed some extra information into `foo` to ensure that, given the value you’re supposed to return, you also do some identity preserving operation on it, assuming that it is the same value you’re supposed to return. This is not as hard or tricky as it sounds. For instance, calculating `fibSeries` using `fix` is a direct extension to the self referencing definition of `fibSeries`:

```fibSeries = fix (x->1:1:zipWith (+) (tail x) x)
```

Another cute example is using `fix` to define a factorial function:

```factorial = fix (f x->if x == 0 then 1 else x * f (x - 1))
```

By the way, why won’t this

```fibSeries = fix (x->1:zipWith (+) (tail x) x)
```

work?

This entry was posted in Computers and tagged , , , . Bookmark the permalink.

### 9 Responses to Haskell's Fixed Point Combinator

1. Tyler says:

Just before intriducing the combinator, you have the code

fibSeries = 1:1:zipWith (+) (tail fibSeries) fibS

where fibS is undefined. I’m pretty sure you’d want it to be

fibSeries = 1:1:zipWith (+) (tail fibSeries) fibSeries

so I thought I’d just let you know about it.

• Sanjoy says:

Fixed. Thanks!

2. Utkarsh Kukreti says:

It won’t work because zipWith will need a second element to be defined in order to define the second element. (tail x’s first element would be the second element), and that would cause infinite recursion. Correct?

3. Sanjoy says:

I’d like to put it as “1:⊥ is the least fixed point of x->1:zipWith (+) (tail x) x”.

But two sides of the same coin, really. ⊥ stands for both “infinite loop” and “error”.

4. Matthew Brunelle says:

Excellent. I just recently began exploring Haskell and I find this kind of material fascinating.

5. xx says:

f x = fib (x – 1) + fib (x – 2)
should be
f x = f (x – 1) + f (x – 2)

6. Deech says:

Perhaps you’d enjoy a t-shirt about Hinduism and Haskell’s fix point combinator.

7. Leon P Smith says:

You can also define the original fib using fix:

fib fib 0 = 1
fib fib 1 = 1
fib fib n = fib (n-1) + fib (n-2)

fibSlow = fix fib

The definition of “fib” is not actually recursive, as the parameter shadows the function name. This style of definition (with or without shadowing) is known as “open recursion”. The advantage is that you can make it fast:

import Data.MemoTrie(memo)

fibFast :: Integer -> Integer
fibFast = fix (memo . fib)

You might be interested in the short paper “Y in Practical Programs”, by Bruce McAdam.

8. Sanjoy says:

@xx Thanks, fixed.

@Deech Thanks! Very interesting!

@Leon Thanks! Will do.