为免费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).正如错误消息所示,您需要启用(无害的)FlexibleContextsGHC扩展来执行此操作,因此请添加...

{-# LANGUAGE FlexibleContexts #-}

...到源文件的顶部.

但请注意,这(Functor f, Eq (f a))并不能真正反映您在实施过程中所做的工作(==).首先,你并不需要这样的假设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.