Хаскелл:Перекрывающиеся экземпляры

Question

Рассмотрим следующий пример программы:

next :: Int -> Int
next i
  | 0 == m2 = d2
  | otherwise = 3 * i + 1
  where
    (d2, m2) = i `divMod` 2

loopIteration :: MaybeT (StateT Int IO) ()
loopIteration = do
  i <- get
  guard $ i > 1
  liftIO $ print i
  modify next

main :: IO ()
main = do
  (`runStateT` 31) . runMaybeT . forever $ loopIteration
  return ()

Он может использовать только get вместо lift get потому что instance MonadState s m => MonadState s (MaybeT m) определяется в модуле MaybeT.

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

Было бы здорово (хотя невозможно?почему?), если бы у нас был следующий тип-класс:

{-# LANGUAGE MultiParamTypeClasses #-}

class SuperMonad m s where
  lifts :: m a -> s a

Попробуем определить это так:

{-# LANGUAGE FlexibleInstances, ... #-}

instance SuperMonad a a where
  lifts = id

instance (SuperMonad a b, MonadTrans t, Monad b) => SuperMonad a (t b) where
  lifts = lift . lifts

С использованием lifts $ print i вместо liftIO $ print i работает, что приятно.

Но используя lifts (get :: StateT Int IO Int) вместо (get :: MaybeT (StateT Int IO) Int) не работает.

GHC (6.10.3) выдает следующую ошибку:

Overlapping instances for SuperMonad
                            (StateT Int IO) (StateT Int IO)
  arising from a use of `lifts'
Matching instances:
  instance SuperMonad a a
  instance (SuperMonad a b, MonadTrans t, Monad b) =>
           SuperMonad a (t b)
In a stmt of a 'do' expression:
    i <- lifts (get :: StateT Int IO Int)

Я понимаю, почему»instance SuperMonad a a"применяется.Но почему GHC думает, что и другой тоже?

Answer 1

Чтобы продолжить отличный ответ эфемиента:Классы типов Haskell используют предположение об открытом мире:какой-нибудь идиот может прийти позже и добавить объявление экземпляра, которое не дубликат и все еще пересекается с ваш экземпляр. Думайте об этом как о противоборствующей игре:если злоумышленник может сделать вашу программу неоднозначной, компилятор блеет.

Если вы используете GHC, вы, конечно, можете сказать компилятору: «К черту вашу паранойю;позвольте мне мое неоднозначное объявление экземпляра":

{-# LANGUAGE OverlappingInstances #-}

Если дальнейшее развитие вашей программы приведет к разрешению перегрузки, которого вы не ожидали, компилятор получает 1000 баллов «Я же вам говорил» :-)

Answer 2

Тот факт, что вы не определили экземпляр в текущем модуле, не означает, что его нельзя определить где-то еще.

{-# LANGUAGE ... #-}
module SomeOtherModule where

-- no practical implementation, but the instance could still be declared
instance SuperMonad (StateT s m) m

Предположим, ваш модуль и SomeOtherModule объединены в одну программу.

Теперь ответьте на это:использует ли ваш код

instance SuperMonad a a
  -- with a = StateT Int IO

или

instance (SuperMonad a b, MonadTrans t, Monad b) => SuperMonad a (t b)
  -- with a = StateT Int IO
  --      t = StateT Int
  --      b = IO

?