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?
The simplest instance I could find was just
All that we require is that
Fix f
is an instance ofEq
precisely whenf (Fix f)
is an instance ofEq
. Since in general we have instances likeEq a => Eq (f a)
this works just fine.