[Haskell] Y in haskell?
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)
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:
"GHC's inliner can be persuaded into non-termination using the standard
way to encode recursion via a data type"
More information about the Haskell