I wrote about the Y-combinator before. Recently, I tried to express the Y-combinator in Haskell, thus:
y f = fg fg
where fg g = f (g g)
To my surprise, I got an error message (from GHC):
Occurs check: cannot construct the infinite type: t = t -> t1
To fix it, I had to introduce a helper type to break the direct cycle in the type definition:
newtype Hold a = Hold (Hold a -> (a -> a))
y f = fg (Hold fg)
where fg hg@(Hold g) = f (g hg)
This worked. Armed with this definition, I could now implement the factorial function in terms of the Y-combinator:
f r n = if n < 2 then 1 else n * (r (n - 1))
:type y f
-- (Num t, Ord t) => t -> t
y f 10
-- 3628800