Apparently one can define the Y combinator with lambda expressions in Haskell. The problem with fix f = (\x -> f (x x))(\x -> f (x x)) is that one needs a solution to the type equation b = b -> a. Fortunately this can be done with Haskell’s data types.
> newtype Mu a = Roll { unroll :: Mu a -> a }
Haskell allows non-monotonic data types, so this is a legal definition. The resulting type Mu a is isomorphic to Mu a -> a. Using this isomorphism one can define the standard Y combinator.
#ifndef __GLASGOW_HASKELL__ > fix f = (\x -> f ((unroll x) x)) (Roll (\x -> f ((unroll x) x))) #endif
Don’t try this with GHC. Due to a mis-feature, GHC’s inliner will continuously expand this expression. If you are desperate you can try Michael Shulman’s solution.
#ifdef __GLASGOW_HASKELL__
> fix f = fixH (Roll fixH)
> where
> {-# NOINLINE fixH #-}
> fixH x = f ((unroll x) x)
#endif
Of course, this is just an academic exercise. To actually define a fixpoint combinator in Haskell, one would use recursive definitions.
> fix2 f = f (fix2 f)