[Haskell] Y in haskell?
bjpop at cs.mu.OZ.AU
Mon Apr 18 01:35:36 EDT 2005
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>
> > > 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.
More information about the Haskell