Writing generic instances for Fix/Mu in F-algebras

algebra, fixpoint-combinators, haskell, recursive-datastructures, typeclass

Solution

The simplest instance I could find was just

{-# LANGUAGE UndecidableInstances, FlexibleContexts #-}
import Data.Function (on)

instance Eq (f (Fix f)) => Eq (Fix f) where
  (==) = (==) `on` unFix

All that we require is that `Fix f` is an instance of `Eq` precisely when `f (Fix f)` is an instance of `Eq`. Since in general we have instances like `Eq a => Eq (f a)` this works just fine.

 > Fx Zero == Fx Zero
   True

Problem

After reading Milewski's F-algebra article, I tried to implement it and use for a real-world problem. However, I can't seem to figure out how to write instances for `Fix`, ``` newtype Fix f = Fx { unFix :: f (Fix f) } cata :: Functor f => (f a -> a) -> Fix f -> a cata alg = alg . fmap (cata alg) . unFix ``` For example, let's say I this simple algebra: ``` data NatF a = Zero | Succ a deriving Eq type Nat = Fix NatF ``` and now I try to implement an instance of `Eq` (note: `deriving` doesn't work): ``` instance ??? => Eq (Fix f) where (==) = ??? ``` And this is where I get stuck. How do I fill in the `???` to make this work? Is this even possible to do?

Original source