[Haskell] Y in haskell?

[Bernard Pope]

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.

Bernie.