Ошибка неожиданных совпадений экземпляров

Question

У меня есть следующий код. Class1 экземпляров говорят, что прямой суперкласс класса, SuperClass1 автоматически обходит Class1, чтобы найти все суперклассы. (Я не указал фактические методы этих классов, потому что они не имеют отношения к моей проблеме.)

{-# 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 для Hfree c f когда Functor является суперкласс c.)

И это дает эту ошибку в Applicative инстанции (и аналогично для экземпляра Монада):

• 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)’ 

насколько я понимаю, что происходит, является то, что Прикладное экземпляр требует экземпляр Functor, поэтому аппликативный экземпляр также нуждается в SuperClass1 Functor c Ограничение от Functor. И действительно, если я добавлю это, ошибка исчезнет. (Это то, что я в настоящее время: http://hackage.haskell.org/package/free-functors-0.7/docs/Data-Functor-HFree.html)

Но как-то GHC достаточно умен, чтобы понять, что SuperClass1 Applicative c подразумевает SuperClass1 Functor c, потому что он не жалуется на недостающую ограничения. Вместо этого он застревает в ошибке совпадающих экземпляров. Было бы здорово, если бы был способ исправить ошибку, но я не могу понять, как это сделать!

Answer 1

Но как-то GHC достаточно умен, чтобы понять, что SuperClass1 Applicative c подразумевает SuperClass1 Functor c, потому что он не жалуется на недостающую ограничения.

Я боюсь, вы слишком надежды - 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, но независимо от того, как вы это, разрешение экземпляр на самом деле трудно. Мой совет - использовать семьи типов, когда сможете.

EDIT

Вот решение, чтобы получить код для компиляции, за исключением того, опираясь на тип семьи вместо типа классов. Машины установка

{-# 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