10

阅读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
  (==) = ???

这就是我卡住的地方。我该如何填写???才能使这项工作?这甚至可能吗?

4

1 回答 1

12

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

{-# 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
于 2014-01-03T03:48:03.500 回答