意外的重叠实例错误

Question

我有以下代码。 Class1 实例说明了 class 的直接 superclass 是什么，SuperClass1 自动遍历 Class1 找到所有的 superclass。（我省略了这些 classes 的实际方法，因为它们与我的问题无关。）

{-# LANGUAGE PolyKinds, RankNTypes, ConstraintKinds, FlexibleInstances, UndecidableInstances, MultiParamTypeClasses, FunctionalDependencies #-}

class Class1 b h | h -> b
instance Class1 Functor Applicative
instance Class1 Applicative Monad

class SuperClass1 b h
instance {-# OVERLAPPING #-} SuperClass1 b b
instance {-# OVERLAPPABLE #-} (SuperClass1 b c, Class1 c h) => SuperClass1 b h

效果很好！现在我想这样使用它：

newtype HFree c f a = HFree { runHFree :: forall g. c g => (forall b. f b -> g b) -> g a }

instance SuperClass1 Functor c => Functor (HFree c f)
instance SuperClass1 Applicative c => Applicative (HFree c f)
instance SuperClass1 Monad c => Monad (HFree c f)

test :: (a -> b) -> HFree Monad f a -> HFree Monad f b
test = fmap

（即只要 Functor 是 c 的超级 class，我就可以为 Hfree c f 提供 Functor 的实例。）

这在 Applicative 实例中给出了这个错误（与 Monad 实例类似）：

• Overlapping instances for SuperClass1 Functor c1
    arising from the superclasses of an instance declaration
  Matching instances:
    instance [overlappable] forall k k k (b :: k) (c :: k) (h :: k).
                            (SuperClass1 b c, Class1 c h) =>
                            SuperClass1 b h
      -- Defined at superclass.hs:17:31
    instance [overlapping] forall k (b :: k). SuperClass1 b b
      -- Defined at superclass.hs:16:30
  (The choice depends on the instantiation of ‘c1, k1’
   To pick the first instance above, use IncoherentInstances
   when compiling the other instance declarations)
• In the instance declaration for ‘Applicative (HFree c f)’

据我了解，发生的情况是 Applicative 实例需要 Functor 实例，因此 Applicative 实例还需要来自 Functor 的 SuperClass1 Functor c 约束。事实上，如果我添加这个，错误就会消失。（这是我目前拥有的：http://hackage.haskell.org/package/free-functors-0.7/docs/Data-Functor-HFree.html）

但是 GHC 以某种方式足够聪明，可以理解 SuperClass1 Applicative c 意味着 SuperClass1 Functor c，因为它不会抱怨缺少约束。相反，它会卡在重叠实例错误上。如果有修复错误的方法就好了，但我不知道如何修复！

Answer 1

But somehow GHC is smart enough to understand that SuperClass1 Applicative c implies SuperClass1 Functor c, because it doesn't complain about a missing constraint.

我担心你太有希望了 - GHC 可能正在从另一端开始工作并立即放弃：它看到 fmap 并尝试检查 HFree 是 Functor.它只有一个实例可供选择：SuperClass1 Functor c => Functor (HFree c f)。然后，它开始尝试满足对该实例的约束 (SuperClass1 Functor c) 并突然意识到它不知道该怎么做 - 它可以选择两个实例：

SuperClass1 b b
SuperClass1 b h

请注意，我遗漏了对这些实例的约束 - 那是因为 GHC 需要在查看左侧的约束之前提交到一个实例 。话虽如此，@user2407038 的评论非常正确：您的实例重叠得非常严重 - GHC 不知道它是否应该尝试统一 b ~ Functor 和 b ~ c 或 b ~ Functor 和 h ~ c。两者都可以。

如果选择 任一个 都可行，您应该启用 IncoherentInstances。不幸的是，这里不是这种情况。您知道您想要选择第二个实例，但 GHC 不知道。

我最近 toying around with a similar sort of problem but in relation to subtyping 但无论您如何处理，实例解析都非常困难。我对您的建议是尽可能使用类型族。

编辑

这是一个让你的代码编译的解决方案，除了依赖类型族而不是 type-classes。安装机器是

{-# LANGUAGE PolyKinds, ConstraintKinds, TypeFamilies, UndecidableInstances, DataKinds, TypeOperators #-}

import Data.Kind (Constraint)

-- Find transitively all the superclasses of a constraint (including itself)
type family SuperClasses (x :: k -> Constraint) :: [k -> Constraint]
type instance SuperClasses Functor = '[Functor]
type instance SuperClasses Applicative = Applicative ': SuperClasses Functor
type instance SuperClasses Monad = Monad ': SuperClasses Applicative

-- Type level version of `elem` which is a Constraint
type family Elem (x :: k) (xs :: [k]) :: Constraint where
  Elem a (a ': bs) = ()
  Elem a (b ': bs) = Elem a bs

-- Type level version of checking the first list is a subset of the second
type family Subset (xs :: [k]) (ys :: [k]) :: Constraint where
  Subset '[] bs = ()
  Subset (a ': as) bs = (Elem a bs, Subset as bs)

-- Tell us whether the constraint x is a sub-constraint (thereby implied by) y
type x <: y = SuperClasses x `Subset` SuperClasses y

然后，应用于Functor、Applicative和Monad，我们需要

-- I've cropped the body of HFree since it is of no interest here
data HFree c f a

instance Functor     <: c => Functor     (HFree c f)
instance Applicative <: c => Applicative (HFree c f)
instance Monad       <: c  => Monad      (HFree c f)

这里有一些测试

-- Compiles
test1 :: (a -> b) -> HFree Monad f a -> HFree Monad f b
test1 = fmap

-- Compiles
test2 :: a -> HFree Monad f a
test2 = pure

-- Doesn't compile
test3 :: a -> HFree Functor f a
test3 = pure

意外的重叠实例错误

Unexpected Overlapping instances error

monads

haskell

types

overlapping-instances

编辑