[Haskell] How to define Y combinator in Haskell

408 views
Skip to first unread message

Haihua Lin

unread,
Sep 15, 2006, 8:11:48 AM9/15/06
to haskell
Hi,

Writing

yc = \f -> (\x -> f(x x)) (\x -> f(x x))

causes type error. Is there a way to define it in Haskell?

Thanks,
Haihua

_______________________________________________
Haskell mailing list
Has...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell

Lennart Augustsson

unread,
Sep 15, 2006, 8:18:28 AM9/15/06
to Haihua Lin
Well, you can do it with the existing recursion in Haskell
let yc f = f (yc f)
Or you can encode it with type level recursion and no value recursion
by using a recursive data type.

-- Lennart

David House

unread,
Sep 15, 2006, 12:46:12 PM9/15/06
to Haihua Lin
On 15/09/06, Haihua Lin <Haih...@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, dmh...@gmail.com

Robert Dockins

unread,
Sep 15, 2006, 1:47:29 PM9/15/06
to has...@haskell.org
On Friday 15 September 2006 12:45, David House wrote:
> On 15/09/06, Haihua Lin <Haih...@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

Michael Shulman

unread,
Sep 15, 2006, 2:48:31 PM9/15/06
to robdo...@fastmail.fm
On 9/15/06, Robert Dockins <robdo...@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.html

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

Robert Dockins

unread,
Sep 15, 2006, 4:16:20 PM9/15/06
to Michael Shulman
On Friday 15 September 2006 14:48, Michael Shulman wrote:
> On 9/15/06, Robert Dockins <robdo...@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

Reply all
Reply to author
Forward
0 new messages