... until the collector arrives ...

This "blog" is really just a scratchpad of mine. There is not much of general interest here. Most of the content is scribbled down "live" as I discover things I want to remember. I rarely go back to correct mistakes in older entries. You have been warned :)

2010-08-11

Y-Combinator in Haskell

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

Blog Archive