2006-09-19T08:48:00Z

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)`

Tags

Russell O’Connor: contact me