看似不重叠的重叠实例

Question

考虑以下（接近最小值）示例：

{-# Language FlexibleInstances #-}

class Predicate a where
    test :: a -> Bool

instance (Predicate a, Traversable t) => Predicate (t a) where
    test = all test

data Bar = Bar
instance Predicate Bar where
    test Bar = False

data Baz a = Baz a
instance Predicate a => Predicate (Baz a) where
    test (Baz x) = test x

main :: IO ()
main = print $ test $ Baz Bar

查看 test $ Baz Bar，您会期望得到 False 的结果，因为我们有实例 Predicate Bar 和 Predicate a => Predicate (Baz a)。

但是 GHC 8.6.3 和 8.0.1 都拒绝了这个：

test.hs:18:16: error:
    • Overlapping instances for Predicate (Baz Bar)
        arising from a use of ‘test’
      Matching instances:
        instance (Predicate a, Traversable t) => Predicate (t a)
          -- Defined at test.hs:6:10
        instance Predicate a => Predicate (Baz a)
          -- Defined at test.hs:14:10
    • In the second argument of ‘($)’, namely ‘test $ Baz Bar’
      In the expression: print $ test $ Baz Bar
      In an equation for ‘main’: main = print $ test $ Baz Bar
   |
18 | main = print $ test $ Baz Bar
   |                ^^^^^^^^^^^^^^

但没有重叠：我们可以通过注释掉 Predicate (Baz a) 实例来确认没有 Traversable Baz 实例，在这种情况下我们会得到错误：

test.hs:18:16: error:
    • No instance for (Traversable Baz) arising from a use of ‘test’
    • In the second argument of ‘($)’, namely ‘test $ Baz Bar’
      In the expression: print $ test $ Baz Bar
      In an equation for ‘main’: main = print $ test $ Baz Bar
   |
18 | main = print $ test $ Baz Bar
   |                ^^^^^^^^^^^^^^

我假设这是 FlexibleInstances 的限制？如果是，为什么，是否有批准的解决方法？

好吧，事实证明这是 GHC 决定独立使用哪个实例的结果，如 here 所述。不过，这个技巧在这里似乎不起作用：

instance (b ~ Baz, Predicate a) => Predicate (b a) where

给出了 Duplicate instance declarations 错误，所以我将问题悬而未决，寻找适用于这种情况的解决方案。

Answer 1

问题是那些实例确实重叠了，因为实例解析机制在决定使用哪个实例时只看实例头，只有稍后，在一个实例有被选中后，它会检查约束以查看是否满足（否则会抛出错误）。

我建议阅读 instance resolution

上的文档

解决问题的一种方法（除了重新设计解决方案，这可能是正确的做法）是告诉 GHC 某个实例是 "less important"（或可重叠的）。
这基本上意味着 GHC 将选择一个更具体的实例（如果它可用）（更具体意味着您可以在上面链接的文档中阅读）。
这是通过使用 pragma {-# OVERLAPPABLE #-} 或 {-# OVERLAPS #-} 来实现的（阅读文档以查看差异，基本上前者更具体）。

生成的代码看起来像这样

{-# Language FlexibleInstances #-}

class Predicate a where
    test :: a -> Bool

instance {-# OVERLAPPABLE #-} (Predicate a, Traversable t) => Predicate (t a) where
    test = all test

data Bar = Bar
instance Predicate Bar where
    test Bar = False

data Baz a = Baz a
instance Predicate a => Predicate (Baz a) where
    test (Baz x) = test x

main :: IO ()
main = do
   print . test $ Baz Bar
   print . test $ ([] :: [Bar])
   print . test $ [Bar]
   print . test $ Baz ([] :: [Bar])

而运行的结果是

False
True
False
True

符合预期。

Answer 2

使用 DerivingVia 你可以将此行为赋予新类型

type    WrappedPredicate :: (k -> Type) -> k -> Type
newtype WrappedPredicate t a = WrapPredicate (t a)
  deriving
  stock Foldable

-- Foldable is sufficient
instance (Foldable t, Predicate a) => Predicate (WrappedPredicate t a) where
  test :: WrappedPredicate t a -> Bool
  test = all test

并通过它导出 Predicate，这比您给出的重叠实例更可取。

{-# Language DerivingVia #-}

type Tree :: Type -> Type
data Tree a = Leaf a | Branch (Tree a) (Tree a)
  deriving
  stock Foldable

  deriving Predicate
  via WrappedPredicate Tree a

就像 Ap f a newtype 是比定义与 Monoid [a] 和其他常见实例不兼容的实例更好的解决方案。

instance (Applicative f, Semigroup a) => Semigroup (f a) where
  (<>) :: f a -> f a -> f a
  (<>) = liftA2 (<>)

instance (Applicative f, Monoid a) => Monoid (f a) where
  mempty :: f a
  mempty = pure mempty

看似不重叠的重叠实例

Overlapping instances that don't seem to overlap

haskell

derivingvia