[Haskell-cafe] Re: Equirecursive types?

[ihope]

On 3/27/06, lee marks <ana_cata_hylo at yahoo.com> wrote:
> So this is legal:
>
>   type Fix s a = s a (Fix s a)
>
>   fold :: Functor (s a) => (s a b -> b) -> Fix s a -> b
>   fold f = f . fmap (fold f)
>
> but this is not:
>
>   fold f = f . fmap (fold f)

data Fix s a = Fix {runFix :: s a (Fix s a)}

fold :: Functor (s a) => (s a b -> b) -> Fix s a -> b
fold f g = f . fmap (fold f) . runFix

Yes, we can build infinite types :-) My favorite so far:

data Self a = Self {runSelf :: Self a -> a}
fix f = (\(Self g) -> f (g (Self g))) (Self (\(Self g) -> f (g (Self g))))

That one seems to give GHCi something to think about! Adding a type
annotation doesn't help.