Haskell: Overlapping instances

Question

Consider the following example program:

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 ()

It can only use get instead of lift get because instance MonadState s m => MonadState s (MaybeT m) is defined in the MaybeT module.

Many such instances are defined in kind of a combinatoric explosion manner.

It would have been nice (although impossible? why?) if we had the following type-class:

{-# LANGUAGE MultiParamTypeClasses #-}

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

Let's try to define it as such:

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

Using lifts $ print i instead of liftIO $ print i works, which is nice.

But using lifts (get :: StateT Int IO Int) instead of (get :: MaybeT (StateT Int IO) Int) doesn't work.

GHC (6.10.3) gives the following error:

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)

I can see why "instance SuperMonad a a" applies. But why does GHC think that the other one does, too?

Answer 1

To follow up ephemient's excellent answer: Haskell type classes use an open-world assumption: some idiot can come along later and add an instance declaration that's not a duplicate and yet overlaps with your instance. Think of it as an adversary game: if an adversary can make your program ambiguous, the compiler bleats.

If you're using GHC you can of course say to the compiler "to hell with your paranoia; allow me my ambiguous instance declaration":

{-# LANGUAGE OverlappingInstances #-}

If later evolution of your program leads to overload resolution you didn't expect, the compiler gets 1,000 I-told-you-so points :-)

Deprecation Note

This pragma has been deprecated since GHC 7.10, and per-instance pragmas should be used instead. More detail can be found in the GHC documentation.

Answer 2

Just because you haven't defined an instance in your current module doesn't mean that one couldn't be defined somewhere else.

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

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

Suppose your module and SomeOtherModule are linked together in a single program.

Now, answer this: does your code use

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

or

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

?

Answer 3

It's better to give these overlapping instances a name by attaching the behaviour to a newtype. This lets you explicitly reuse the code:

type    SuperEgo :: (k -> Type) -> (k -> Type)
newtype SuperEgo m a = SuperEgo (m a)

{-
type MonadTransformer :: Type
type MonadTransformer = (Type -> Type) -> (Type -> Type)

type    Elevator :: MonadTransformer -> MonadTransformer
-}
type    Elevator :: (k -> k1 -> Type) -> (k -> k1 -> Type)
newtype Elevator trans m a = Elevator (trans m a)

instance m ~ m' => SuperMonad m (SuperEgo m') where
  lifts :: m ~> SuperEgo m
  lifts = SuperEgo

instance (SuperMonad m super, Monad super, MonadTrans trans) => SuperMonad m (Elevator trans super) where
  lifts :: m ~> Elevator trans super
  lifts = Elevator . lift . lifts

Monads can now derive via SuperEgo M to get an identity instances

{-# Language DerivingVia #-}

data Ok a = Ok a
  deriving (SuperMonad Ok)
  via SuperEgo Ok

It's more of a hassle to define a monad transformer so I'll show how to define a lifting instance for an existing Monad transformers like StateT s. This uses standalone deriving which is more verbose, you need to fill in the class context yourself:

deriving
  via Elevator (StateT s) super
  instance (Monad super, SuperMonad m super) => SuperMonad m (StateT s super)