haskell - 在 F 代数中为 Fix/Mu 编写通用实例

Question

阅读后Milewski's F-algebra article ，我尝试实现它并用于解决现实世界的问题。但是，我似乎不知道如何为 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