haskell - 如何在递归方案中派生实例

Question

我正在测试 this article 中的一些想法.

我想派生 Term 类型的 Eq 实例:

{-# LANGUAGE DeriveFunctor #-}
data Tree a = Branch Int [a] | Leaf Int deriving (Eq, Functor, Show)
data Term f = Term (f (Term f)) deriving (Eq)

但出现此错误:

No instance for (Eq (f (Term f)))
      arising from the first field of ‘Term’ (type ‘f (Term f)’)
    Possible fix:
      use a standalone 'deriving instance' declaration,
        so you can specify the instance context yourself
    When deriving the instance for (Eq (Term f))

我尝试添加一个独立的派生实例:

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE StandaloneDeriving #-}
data Tree a = Branch Int [a] | Leaf Int deriving (Eq, Functor, Show)
data Term f = Term (f (Term f))
deriving instance (Eq f) => Eq (Term f)

但出现此错误:

The first argument of ‘Term’ should have kind ‘* -> *’,
  but ‘f’ has kind ‘*’
In the stand-alone deriving instance for ‘(Eq f) => Eq (Term f)’

现在我被困住了。如何证明 f 有一种 * -> *？为什么我需要 Term 的独立派生实例而不是 Tree？两者都有类型变量，这些变量不一定是 Eq? 的实例。 (a 和 f)

Answer 1

有两种解决方案:

使用一些 GHC 扩展 StandaloneDeriving、UndecidableInstances 以及其他一些您可以编写的扩展:

deriving instance (Eq (f (Term f))) => Eq (Term f)

这就是 recursion-schemes目前做

--

或者，您可以使用 transformers 中的 Eq1或base-4.9.0.0

class Eq1 f where
    liftEq :: (a -> b -> Bool) -> f a -> f b -> Bool

eq1 :: (Eq1 f, Eq a) -> f a -> f a -> Bool
eq1 = liftEq (==)

instance Eq1 f => Eq (Term f) where
    Term a == Term b = eq1 a b

引用:https://github.com/ekmett/recursion-schemes/blob/ffada24f92efd5bcfe71f7f0af3b4af057f50bd0/Data/Functor/Foldable.hs#L392