Bernard Pope bjpop at cs.mu.OZ.AU
Mon Apr 18 02:09:08 EDT 2005

```On Mon, 2005-04-18 at 15:35 +1000, Bernard Pope wrote:
> On Mon, 2005-04-18 at 01:08 -0400, David Menendez wrote:
> > Trevion writes:
> >
> > > On 4/18/05, Lloyd Allison <Lloyd.Allison at infotech.monash.edu.au>
> > wrote:
> > > > Is it possible to define Y in Haskell (pref' H98) --
> > > > and get it to pass type checking?
> > >
> > > I believe that
> > >
> > > y f = f (y f)
> > >
> > > is the normal way to do it.
> >
> > I've also seen this:
> >
> >     y f = g
> >         where g = f g
>
> Note that the second form generally gives more sharing than the first
> (I say generally because there is no guarantee in Haskell how much
> sharing you will get.) At least GHC (and probably hugs and nhc98) gives
> the second form a cyclic representation.
>
> See the discussion in Section 4.1 (Recursion) in "A Natural Semantics
> for Lazy Evaluation", John Launchbury.

I also meant to add that I think these solutions are not what Lloyd is
after, because they rely on recursive equations, which I believe was
avoided in Lloyd's SML code.

Here is a translation into Haskell:

---
data Rt a = Recrt (Rt a -> a)

y :: (a -> a) -> a
y x = ggg (Recrt ggg)
where
ggg (Recrt g) = x (g (Recrt g))

func :: (Int -> Int) -> Int -> Int
func f n = if n==0 then 1 else n * f (n-1)

main :: IO ()
main = print (y func 3)
---

Hugs accepts this, but GHC 6.2 goes into an infinite loop on my machine.

I think this is mentioned in the list of known bugs in GHC: