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