haskell - 不可判定的函数依赖

Question

我正在阅读Clowns to the left of me, Jokers to the right并尝试使用解剖类，我遇到了覆盖条件错误。代码:

{-# LANGUAGE TypeOperators, MultiParamTypeClasses, FunctionalDependencies #-}
import Data.Bifunctor
import GHC.Generics

data Add2 p q x y = L2 (p x y) | R2 (q x y)

instance (Bifunctor p, Bifunctor q) => Bifunctor (Add2 p q) where
  bimap f g (L2 p) = L2 (bimap f g p)
  bimap f g (R2 q) = R2 (bimap f g q)

class (Functor p, Bifunctor p') => Diss p p' | p -> p' where

instance (Diss p p', Diss q q') => Diss (p :+: q) (Add2 p' q')

GHC 错误消息:

cj.hs:13:10: error:
    • Illegal instance declaration for ‘Diss (p :+: q) (Add2 p' q')’
        The coverage condition fails in class ‘Diss’
          for functional dependency: ‘p -> p'’
        Reason: lhs type ‘p :+: q’ does not determine rhs type ‘Add2 p' q'’
        Un-determined variables: p', q'
        Using UndecidableInstances might help
    • In the instance declaration for ‘Diss (p :+: q) (Add2 p' q')’
   |
13 | instance (Diss p p', Diss q q') => Diss (p :+: q) (Add2 p' q')
   |          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

我很难理解给出的原因:我觉得类型 p :+: q 应该确定 rhs 类型，因为依赖关系 p -> p' 和 q -> q' 由约束 Diss p p' 和 Diss q q' 隐含。启用 UndecidableInstances 确实可以消除错误，但我想了解为什么在这种情况下有必要。

Answer 1

GHC documentation对于类似的场景有这样的说法:

class Mul a b c | a b -> c where
  (.*.) :: a -> b -> c

instance Mul Int Int Int where (.*.) = (*)
instance Mul Int Float Float where x .*. y = fromIntegral x * y
instance Mul a b c => Mul a [b] [c] where x .*. v = map (x.*.) v

(回答者注意:与您的示例一样，您可能会认为在 Mul a b c => Mul a [b] [c] 实例中，因为 a b 确定c，也应该是a [b]清楚地确定[c]。)

The third instance declaration does not obey the coverage condition; and indeed the (somewhat strange) definition:

f = \ b x y -> if b then x .*. [y] else y

makes instance inference go into a loop, because it requires the constraint Mul a [b] b.

因此，承保条件明确是为了排除像您这样看起来良性但可能并非良性的病例。