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.