Непредвиденная ошибка перекрывающихся экземпляров

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 (и аналогичном для экземпляра 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 также требуется 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 - нет.

---

Недавно я играл с подобной проблемой, но в отношении подтипов, но независимо от того, как вы это решите, разрешение экземпляра действительно сложно. Я советую вам использовать семейства типов, когда вы можете.

РЕДАКТИРОВАТЬ

Вот решение, позволяющее компилировать ваш код, за исключением использования семейств типов вместо классов типов. Механизм настройки

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