[Haskell] How to define Y combinator in Haskell

Michael Shulman viritrilbia at gmail.com
Fri Sep 15 14:48:02 EDT 2006

On 9/15/06, Robert Dockins <robdockins at fastmail.fm> wrote:
> You can define a direct fixed point combinator
> without relying on nominal recursion in Haskell, but it requires you to
> define a helper newtype.

That's really nifty!  I'd been wondering whether you could do this
too.  Is there a reason for the extra `z' parameter?

> Don't run this in GHC because it will diverge.  Hugs works, however.

According to


this is due to a bug in the GHC inliner that probably won't be fixed.
However, experimentation indicates you can work around the bug using
the NOINLINE pragma:

newtype Mu a = Roll { unroll :: Mu a -> a }

fix :: (a -> a) -> a
fix f = doink (Roll doink)
    where {-# NOINLINE doink #-}
          doink x = f ((unroll x) x)


More information about the Haskell mailing list