[Haskell] How to define Y combinator in Haskell
Robert Dockins
robdockins at fastmail.fm
Fri Sep 15 13:46:54 EDT 2006
On Friday 15 September 2006 12:45, David House wrote:
> On 15/09/06, Haihua Lin <HaihuaLin at 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
More information about the Haskell
mailing list