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

Question

阅读完Milewski的F代数文章后，我尝试实现它并将其用于解决实际问题。 但是，我似乎无法弄清楚如何编写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
  (==) = ???

我现在遇到了困难。要如何填写???才能使这个工作？这样做可能吗？

- Rufflewind

---

你可能想要专门为Fix NatF创建Eq实例。 - David Young

Answer 1

我能找到的最简单的例子只是这样的

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

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

我们唯一需要的是，当 f (Fix f) 是 Eq 的实例时，Fix f 也是 Eq 的实例。由于通常我们有类似 Eq a => Eq (f a) 这样的实例，这很好地解决了问题。

 > Fx Zero == Fx Zero
   True

- Daniel Gratzer