在F-algebras中编写Fix/Mu的通用实例

Question

在阅读了Milewski的F-algebra文章后,我尝试实现它并用于解决现实问题.但是,我似乎无法弄清楚如何编写实例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

例如,让我说我这个简单的代数:

data NatF a = Zero | Succ a   deriving Eq
type Nat    = Fix NatF

现在我尝试实现一个实例Eq(注意:deriving不起作用):

instance ??? => Eq (Fix f) where
  (==) = ???

这就是我陷入困境的地方.我如何填写???以使其工作？这甚至可能吗？

Answer 1

我能找到的最简单的例子就是

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

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

我们需要的Fix f只是一个Eq恰好f (Fix f)是何时是实例的实例Eq.因为一般来说我们有这样的实例Eq a => Eq (f a)工作得很好.

 > Fx Zero == Fx Zero
   True