为什么使用 QuantifiedConstraints 指定类型类的子类也需要子类的实例？

Question

我正在研究 Free

的多种无标记编码

{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE TypeSynonymInstances #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE Rank2Types #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE ConstraintKinds #-}
{-# LANGUAGE QuantifiedConstraints #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE TypeOperators #-}
module Free where
import GHC.Types

type (a :: k) ~> (b :: k) = Morphism k a b

newtype Natural (f :: j -> k) (g :: j -> k) = 
  Natural { getNatural :: forall (x :: j). f x ~> g x }

type family Morphism k :: k -> k -> Type where
  Morphism Type = (->)
  Morphism (j -> k) = Natural

class DataKind k where
  data Free :: (k -> Constraint) -> k -> k
  interpret :: forall (cls :: k -> Constraint) (u :: k) (v :: k). 
               cls v => (u ~> v) -> (Free cls u ~> v)
  call :: forall (cls :: k -> Constraint) (u :: k). 
          u ~> Free cls u

instance DataKind Type where
  newtype Free cls u = Free0
    { runFree0 :: forall v. cls v => (u ~> v) -> v }
  interpret f = \(Free0 g) -> g f
  call = \u -> Free0 $ \f -> f u

我可以毫无问题地为 Free Semigroup 和 Free Monoid 编写 Semigroup 个实例：

instance Semigroup (Free Semigroup u) where
  Free0 g <> Free0 g' = Free0 $ \f -> g f <> g' f

instance Semigroup (Free Monoid u) where
  Free0 g <> Free0 g' = Free0 $ \f -> g f <> g' f

这些实例是相同的，并且将用于 Semigroup 的任何其他子类。

我想使用 QuantifiedConstraints 这样我就可以为 Semigroup 的所有子类编写一个实例:

instance (forall v. cls v => Semigroup v) => Semigroup (Free cls u) where
  Free0 g <> Free0 g' = Free0 $ \f -> g f <> g' f

但是编译器 (GHC-8.6.3) 抱怨它无法推断 cls (Free cls u):

Free.hs:57:10: error:
    • Could not deduce: cls (Free cls u)
        arising from a use of ‘GHC.Base.$dmsconcat’
      from the context: forall v. cls v => Semigroup v
        bound by the instance declaration at Free.hs:57:10-67
    • In the expression: GHC.Base.$dmsconcat @(Free cls u)
      In an equation for ‘GHC.Base.sconcat’:
          GHC.Base.sconcat = GHC.Base.$dmsconcat @(Free cls u)
      In the instance declaration for ‘Semigroup (Free cls u)’
    • Relevant bindings include
        sconcat :: GHC.Base.NonEmpty (Free cls u) -> Free cls u
          (bound at Free.hs:57:10)
   |
57 | instance (forall v. cls v => Semigroup v) => Semigroup (Free cls u) where
   |          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Free.hs:57:10: error:
    • Could not deduce: cls (Free cls u)
        arising from a use of ‘GHC.Base.$dmstimes’
      from the context: forall v. cls v => Semigroup v
        bound by the instance declaration at Free.hs:57:10-67
      or from: Integral b
        bound by the type signature for:
                   GHC.Base.stimes :: forall b.
                                      Integral b =>
                                      b -> Free cls u -> Free cls u
        at Free.hs:57:10-67
    • In the expression: GHC.Base.$dmstimes @(Free cls u)
      In an equation for ‘GHC.Base.stimes’:
          GHC.Base.stimes = GHC.Base.$dmstimes @(Free cls u)
      In the instance declaration for ‘Semigroup (Free cls u)’
    • Relevant bindings include
        stimes :: b -> Free cls u -> Free cls u (bound at Free.hs:57:10)
   |
57 | instance (forall v. cls v => Semigroup v) => Semigroup (Free cls u) where
   |          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

当我将其添加为实例的上下文时，它可以正常编译：

instance (cls (Free cls u), forall v. cls v => Semigroup v) => Semigroup (Free cls u) where
  Free0 g <> Free0 g' = Free0 $ \f -> g f <> g' f

添加的上下文有点冗长，但由于 Free 的重点是 cls (Free cls u) 始终为真，并不繁琐。

我不明白的是为什么 GHC 需要能够为Semigroup 的子类Semigroup 得出cls (Free cls u) ] 实例进行编译。我尝试用 undefined 替换 (<>) 的定义并得到相同的错误，所以我认为问题不在实现本身，而是在实例的声明中；可能是因为 QuantifiedConstraints 的某些方面我不明白。

Answer 1

错误消息指出这些错误来自 sconcat 和 stimes 的默认定义。量化的上下文就像 instances：在你的 instance Semigroup (Free cls v) 中，就好像范围内有一个 instance cls v => Semigroup v。 instance通过匹配选出。 sconcat 和 stimes 想要 Semigroup (Free cls v)，所以他们根据上下文 instance forall z. cls z => Semigroup z 匹配那个想要，用 z ~ Free cls v 成功，并得到进一步想要的 cls (Free cls v).即使我们也有一个递归 instance _etc => Semigroup (Free cls v) 周围，也会发生这种情况。请记住，我们假设类型类实例是连贯的；使用量化上下文还是使用当前定义的实例应该没有区别，因此 GHC 只会选择它想要使用的实例。

然而，这不是一个好情况。量化的上下文 overlaps 与我们的实例（实际上，它与 every Semigroup 实例重叠），这是惊人的。如果你尝试像 (<>) = const (Free0 _etc) ([1, 2] <> [3, 4]) 这样的东西，你会得到类似的错误，因为量化的上下文掩盖了库中真实的 instance Semigroup [a]。我认为包括来自 issue 14877 的一些想法可以减少这种不适：

class (a => b) => Implies a b
instance (a => b) => Implies a b
instance (forall v. cls v `Implies` Semigroup v) => Semigroup (Free cls u) where
  Free0 g <> Free0 g' = Free0 $ \f -> g f <> g' f

在这里使用 Implies 意味着量化的上下文不再匹配 Semigroup (Free cls v) 的需求，而是通过递归来释放。但是，约束背后的要求不会改变。本质上，我们保留了量化约束的需求片段，对于用户来说，Semigroup v应该被cls v隐含，同时在放电片段上打了一个安全，用于实现，所以它不会破坏我们的约束解决方案。 Implies 约束仍然可以而且必须用于证明 (<>) 中的 Semigroup v 约束，但它被认为是显式 Semigroup 实例用尽后的最后手段。

为什么使用 QuantifiedConstraints 指定类型类的子类也需要子类的实例？

Why is using QuantifiedConstraints to specify a subclass of a typeclass also demanding an instance of the subclass?

haskell

quantified-constraints