Writing generic instances for Fix/Mu in F-algebras

Question

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?

Daydream

You might want to make the Eq instance for Fix NatF specifically. – Jerrold

Answer 1

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

Marsland