Re: [Haskell] How to define Y combinator in Haskell
On 15/09/06, Haihua Lin <HaihuaLin@163.com> wrote:
Is there a way to define it in Haskell?
Note that the function 'fix' (find the fixpoint of a function) already exists in Haskell, and is equivalent to the Y combinator. It's interesting that most (all?) fixed-point combinators don't typecheck. The Y combinator, and by extension recursion in general, has to be added as a constant to the language. -- -David House, dmhouse@gmail.com
On Friday 15 September 2006 12:45, David House wrote:
On 15/09/06, Haihua Lin <HaihuaLin@163.com> wrote:
Is there a way to define it in Haskell?
Note that the function 'fix' (find the fixpoint of a function) already exists in Haskell, and is equivalent to the Y combinator.
It's interesting that most (all?) fixed-point combinators don't typecheck. The Y combinator, and by extension recursion in general, has to be added as a constant to the language.
This actually isn't true. You can define a direct fixed point combinator without relying on nominal recursion in Haskell, but it requires you to define a helper newtype. Don't run this in GHC because it will diverge. Hugs works, however. newtype Mu a = Roll (Mu a -> (a -> a)) unroll (Roll x) = x fix :: (a -> a) -> a -> a fix = \f -> (\x z -> f ((unroll x) x z)) (Roll (\x z -> f ((unroll x) x z))) facF :: (Int -> Int) -> Int -> Int facF f x | x <= 0 = 1 | otherwise = x * (f (x-1)) fac :: Int -> Int fac = fix facF undefined main = print $ fac 5 Rob Dockins Talk softly and drive a Sherman tank. Laugh hard, it's a long way to the bank. -- TMBG
On 9/15/06, Robert Dockins <robdockins@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?
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.htm... 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
On Friday 15 September 2006 14:48, Michael Shulman wrote:
On 9/15/06, Robert Dockins <robdockins@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
participants (3)
-
David House -
Michael Shulman -
Robert Dockins