haskell - 为 Free Monad 定义相等实例

Question

鉴于 Free Monad :

data Free f a = Var a
               | Node (f (Free f a)) 

我试图为它定义一个 Eq 实例:

instance (Functor f, Eq (f a)) => Eq (Free f a) where
    (==) (Var x) (Var y)       = x == y
    (==) (Node fu1) (Node fu2) = fu1 == fu2
    (==) _ _                   = False

但这无法编译:

FreeMonad.hs:17:10:
    Non type-variable argument in the constraint: Eq (f a)
    (Use FlexibleContexts to permit this)
    In the context: (Functor f, Eq (f a))
    While checking an instance declaration
    In the instance declaration for ‘Eq (Free f a)’
Failed, modules loaded: none.

指定 (Functor f, Eq (f a)) 的约束/先决条件对我来说似乎很奇怪(至少我认为我以前没有将它视为初学者)。

如何为 Eq 定义 Free f a 实例？

Answer 1

像 Eq (f a) 这样的约束并没有错。正如错误消息所说，您需要启用(无害的)FlexibleContexts GHC 扩展来执行此操作，因此添加...

{-# LANGUAGE FlexibleContexts #-}

...到源文件的顶部。

但是请注意， (Functor f, Eq (f a)) 并没有真正反射(reflect)您在 (==) 的实现中所做的事情。首先，这里不需要假设 f 是 Functor，因此可以安全地删除 Functor f 约束。其次，约束应该与您编写不同案例所需的内容相匹配。在第一种情况下，您执行 x == y 。 x 和 y 都是 a 类型，所以你需要 Eq a 。出于类似的原因，第二种情况需要 Eq (f (Free f a)) 而不是 Eq (f a) 。这意味着你最终会...

(Eq (f (Free f a)), Eq a) => Eq (Free f a)

...匹配引用实现，例如 Control.Monad.Free 中的实现。