fix f = let x = f x in x

One function in the Haskell standard library is ‘fix’, the least fixed point operator (a sort of generalisation of the Y combinator). As per the topic, the entire source code for it is:

fix :: (t -> t) -> t
fix f = let x = f x in x

This is really awesome, but it took me a while to figure out how it worked.

Let’s take an example:

g x = 1 : x
ones = fix g

This gives us an infinite list of ones. However, it’s important to note that at this point nothing is evaluated.

Suppose I wanted to evaluate head ones. How would the evaluation proceed? It would go as follows:

head(ones) = head(1 : ones) = 1

No more of the argument is evaluated than needed. That’s what laziness means.

Now let’s see how we use it as Y combinator.

genfact f 0 = 0
genfact f n = n * (f(n-1))

(I’m aware my bracketing is non-ideal. I haven’t quite got the hang of reading and writing Haskell in a normal style yet though)

fix genfact 3 = genfact (fix genfact) 3
= 3 * ( (fix genfact) 2 )
= 3 * ( genfact (fix genfact) 2)
= 3 * 2 * ( (fix genfact) 1)
= 3 * 2 * 1 * (fix genfact 0)
= 3 * 2 * 1 * (genfact (fix genfact) 0)
= 3 * 2 * 1 * 1
= 6

Neat.

This entry was posted in programming on by .