[Haskell] How to define Y combinator in Haskell

[Robert Dockins]

On Friday 15 September 2006 14:48, Michael Shulman wrote:
> 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?

It made the typing work out ;-)  It can probably be eliminated, but I haven't 
bothered to figure out how.  I originally wrote it as a mental exercise and 
stopped once I got it to work.

> > Don't run this in GHC because it will diverge.  Hugs works, however.
>
> According to
>
> http://www.haskell.org/pipermail/glasgow-haskell-bugs/2001-August/001717.ht
>ml
>
> 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)
>
>
> Mike

-- 
Rob Dockins

Talk softly and drive a Sherman tank.
Laugh hard, it's a long way to the bank.
       -- TMBG