2017-04-07

When GHC encounters a type error, it will sometimes recommend you turn on a language extension. Extensions like OverloadedStrings, GeneralizedNewtypeDeriving, and FlexibleContexts are generally safe. However, extensions like OverlappingInstances, IncoherentInstances, and UndecidableInstances can be dangerous. This article is about both the safe and dangerous uses of UndecidableInstances.

UndecidableInstances has three main uses, one of which is dangerous and two of which are safe. I discuss all three uses below.

Use One: Overlapping Instances (DANGEROUS)

UndecidableInstances is dangerous when it is actually covering up overlapping instances. This section introduces a FooT monad transformer and shows how a MonadIO instance would be written for FooT. It then goes on to show how a general MonadIO instance could be written for any monad transformer. It concludes by explaining how this general MonadIO instance is an overlapping instance.

This section assumes knowledge of monad transformers and mtl-style monad type classes.

The FooT Monad Transformer

Imagine we have the following FooT monad transformer¹ (type annotations have been added to help the reader):

newtype FooT m a = FooT
  { runFoo :: ReaderT Int (StateT String m) a
  } deriving
      ( Functor
      , Applicative
      , Monad
      , MonadReader Int
      , MonadState String
      )

instance MonadTrans FooT where
  lift :: Monad m => m a -> FooT m a
  lift ma =
    let stateT = lift ma :: StateT String m a
        readerT = lift stateT :: ReaderT Int (StateT String m) a
    in FooT readerT

The transformers package provides MonadIO instances for ReaderT and StateT that look like the following:

class Monad m => MonadIO m where
  liftIO :: IO a -> m a

instance MonadIO m => MonadIO (ReaderT r m) where
  liftIO :: IO a -> ReaderT r m a
  liftIO = (lift :: m a -> ReaderT r m a) . (liftIO :: IO a -> m a)

instance MonadIO m => MonadIO (StateT s m) where
  liftIO :: IO a -> StateT s m a
  liftIO = (lift :: m a -> StateT s m a) . (liftIO :: IO a -> m a)

With these two instances defined, it should be easy to write a MonadIO instance for FooT:

instance MonadIO m => MonadIO (FooT m) where
  liftIO :: IO a -> FooT m a
  liftIO = (lift :: m a -> FooT m a) . (liftIO :: IO a -> m a)

With these instances defined, we should be able to compile and run the foo function below, which makes use of FooT's MonadIO instance:

useMonadIO :: MonadIO m => m ()
useMonadIO = liftIO $ putStrLn "hello"

foo :: MonadIO m => FooT m ()
foo = useMonadIO

liftIO Definition

If you go back and look at the bodies of all these liftIO functions, you will see that they are almost identical:

-- ReaderT:
liftIO :: MonadIO m => IO a -> ReaderT r m a
liftIO = (lift :: m a -> ReaderT r m a) . (liftIO :: IO a -> m a)

-- StateT:
liftIO :: MonadIO m => IO a -> StateT s m a
liftIO = (lift :: m a -> StateT s m a) . (liftIO :: IO a -> m a)

-- FooT:
liftIO :: MonadIO m => IO a -> FooT m a
liftIO = (lift :: m a -> FooT m a) . (liftIO :: IO a -> m a)

They are all defined as lift . liftIO. Shouldn't it be possible to write an instance of MonadIO that works for all monad transformers? Then we wouldn't have to write individual instances.

The general instance would look like this:

instance (Monad (t n), MonadIO n, MonadTrans t) => MonadIO (t n) where
  liftIO :: IO a -> t n a
  liftIO = (lift :: n a -> t n a) . (liftIO :: IO a -> n a)

What is this instance saying? It's saying that there is an instance of MonadIO for any t n, as long as t n is a Monad, n is MonadIO (which implies that n is also a Monad), and t is MonadTrans.

This works well. It lets the user run MonadIO actions in any transformer stack (so any ReaderT, ExceptT, StateT, etc.), as long as the monad transformer's underlying monad also implements MonadIO. In our FooT example, you don't need to write separate instances of ReaderT, StateT, and FooT. It really cuts down on the number of instances you need to write.

You can still run the following foo function without any problem:

useMonadIO :: MonadIO m => m ()
useMonadIO = liftIO $ putStrLn "hello"

foo :: MonadIO m => FooT m ()
foo = useMonadIO

However, if you try to compile this general instance, GHC will give an error saying that you need to turn on UndecidableInstances:

test-monad-trans.hs:52:10: error:
  • The constraint ‘Monad (t n)’ is no smaller than the instance head
    (Use UndecidableInstances to permit this)
  • In the instance declaration for ‘MonadIO (t n)’

What does this mean? Let's take a look at the instance definition again:

instance (Monad (t n), MonadIO n, MonadTrans t) => MonadIO (t n) where

Do you see the very first constraint Monad (t n), and how the (t n) here is exactly the same as the (t n) in the instance head MonadIO (t n)? GHC doesn't allow this. GHC thinks of an instance as "decidable" only if all of the parameters of the type class get smaller as you walk backwards into the instance dependencies.²

This means that the constraint MonadIO n is acceptable, since n is smaller than the (t n) in the instance head. For the same reason, the constraint MonadTrans t is also acceptable. But Monad (t n) is not.

If we could somehow create the following MonadIO instance, we might be alright:

instance (MonadIO n, MonadTrans t) => MonadIO (t n) where

However, this isn't possible because of the constraints on the actual MonadIO and MonadTrans type classes. And even if it were possible, it leads us to an even bigger problem. This MonadIO (t n) instance overlaps with some potentially valid instances.

Overlapping Instances

Imagine the following FreeIO datatype:

newtype FreeIO f a = FreeIO (IO (Either a (f (FreeIO f a))))

This is just a free monad wrapped around IO. It's okay if you don't understand this datatype. For our purposes, it's enough to know that this is a valid data type.

For completeness, here are the Functor, Applicative, and Monad instances for FreeIO. Feel free to just skim over these:

instance Functor f => Functor (FreeIO f) where
  fmap :: (a -> b) -> FreeIO f a -> FreeIO f b
  fmap f (FreeIO io) = FreeIO $ do
    eitherA <- io
    pure $
      case eitherA of
        Left a -> Left $ f a
        Right fFreeIO -> Right $ fmap f <$> fFreeIO

instance Functor f => Applicative (FreeIO f) where
  pure :: a -> FreeIO f a
  pure a = FreeIO . pure $ Left a

  (<*>) :: FreeIO f (a -> b) -> FreeIO f a -> FreeIO f b
  (<*>) (FreeIO ioA2b) (FreeIO ioA) = FreeIO $ do
    eitherFa2b <- ioA2b
    eitherFa <- ioA
    pure $
      case (eitherFa2b, eitherFa) of
        (Left a2b, Left a) -> Left $ a2b a
        (Left a2b, Right fFreeIOa) -> Right $ fmap a2b <$> fFreeIOa
        (Right fFreeIOa2b, o) -> Right $ (<*> FreeIO (pure o)) <$> fFreeIOa2b

instance Functor f => Monad (FreeIO f) where
  (>>=) :: FreeIO f a -> (a -> FreeIO f b) -> FreeIO f b
  (>>=) (FreeIO ioA) mA2b = FreeIO $ do
    eitherFa <- ioA
    case eitherFa of
      Left a ->
        let (FreeIO ioB) = mA2b a
        in ioB
      Right fFreeIOa -> pure . Right $ fmap (>>= mA2b) fFreeIOa

It's possible to write a MonadIO instance for FreeIO:

instance Functor f => MonadIO (FreeIO f) where
  liftIO :: IO a -> FreeIO f a
  liftIO ioAction = FreeIO (Left <$> ioAction)

We can even imagine writing a function using the MonadIO instance of FreeIO:

liftIOInFreeIO :: Functor f => FreeIO f ()
liftIOInFreeIO = liftIO $ print "hello"

If you try to compile liftIOInFreeIO with both this instance MonadIO (FreeIO f) and the bad instance from above MonadIO (t n) in scope, you get the following error:

test-monad-trans.hs:103:25: error:
    • Overlapping instances for MonadIO (FreeIO f)
        arising from a use of ‘liftIO’
      Matching instances:
        instance (Monad (t n), MonadIO n, MonadTrans t) => MonadIO (t n)
          -- Defined at test-monad-trans.hs:52:10
        instance Functor f => MonadIO (FreeIO f)
          -- Defined at test-monad-trans.hs:98:10
    • In the expression: liftIO $ print "hello"
      In an equation for ‘tryMyLiftIOWithFreeIO’:
          tryMyLiftIOWithFreeIO = liftIO $ print "hello"

Why does this happen?

Well, in instance (Monad (t n), MonadIO n, MonadTrans t) => MonadIO (t n), what is the kind of t and n?

Since n is supposed to be a Monad, its kind is * -> *. And since t is a monad transformer, its kind is (* -> *) -> * -> *. t n is also supposed to be a Monad, so its kind is also * -> *:

n :: * -> *
t :: (* -> *) -> * -> *
t n :: * -> *

Now, in instance Functor f => MonadIO (FreeIO f), what are the kinds of FreeIO and f?

f is supposed to be a Functor, so its kind is * -> *. FreeIO's kind is (* -> *) -> * -> *. FreeIO f is a Monad, so its kind is * -> *:

f :: * -> *
FreeIO :: (* -> *) -> * -> *
FreeIO f :: * -> *

Since the kinds are the same, you can see that instance Functor f => MonadIO (FreeIO f) overlaps with instance (Monad (t n), MonadIO n, MonadTrans t) => MonadIO (t n). When GHC is trying to decide which instance to use for FreeIO f, it isn't sure which one to pick!

"Wait a minute!" you say. "The constraints are different! MonadIO (FreeIO f) has the constraint Functor f, while MonadIO (t n) has the constraint Monad (t n), MonadIO n, MonadTrans t. Surely GHC can figure this out!" But unfortunately, it can't.

When GHC is determining which instance to use, it only looks at the instance head. It does not look at the constraints. So GHC isn't able to decide whether to use MonadIO (FreeIO f) or MonadIO (t n).

"But hold on!" you say. "Since we're looking for an instance of MonadIO for FreeIO f, surely GHC can see that the instance MonadIO (FreeIO f) is more specific than the instance MonadIO (t n). Doesn't GHC realize we want the more specific instance?" Unfortunately, it doesn't.

By default, if you have two matching instances, GHC doesn't take the more specific one. It just returns the error from above, saying that there are multiple matching instances.

What if I really need this to work?

You can get around this by marking your MonadIO (FreeIO f) instance as OVERLAPPING:

instance {-# OVERLAPPING #-} Functor f => MonadIO (FreeIO f) where
  liftIO :: IO a -> FreeIO f a
  liftIO m = FreeIO (Left <$> m)

Or, you can go the other way and mark the MonadIO (t n) instance as OVERLAPPABLE:

instance {-# OVERLAPPABLE #-} (Monad (t n), MonadIO n, MonadTrans t) => MonadIO (t n) where
  liftIO :: IO a -> t n a
  liftIO = (lift :: n a -> t n a) . (liftIO :: IO a -> n a)

Either of these will make GHC pick the more specific instance MonadIO (FreeIO f).

However, this is a treacherous route to go down. You can find out more about why overlapping can be bad from the GHC user guide.

This MonadIO (FreeIO f) example was created by Edward Kmett. He says:

I have about 3 overlappable/overlapped instances in the million+ lines of haskell I maintain. All of them are bad ideas like this where I tried to save myself effort. None of them are critical.

He also gives one more example of a bad overlapping instance involving PolyKinds at the very end of this reddit post.

If you are working with your own type class (and not a type class defined by another package else like MonadIO), it is possible to use DefaultSignatures to make deriving instances much simpler.³

Use Two: Type Class Synonyms (safe)

Type classes can be used to create synonyms of other type classes. Here's an example:

class (Show a, Monoid a) => ShowDefault a

instance (Show a, Monoid a) => ShowDefault a

showDefault :: forall a . ShowDefault a => a -> String
showDefault a =
  let def = mempty :: a
  in show a ++ " (default: " ++ show def ++ ")"

test :: String
test = showDefault ([1,2,3] :: [Int])

We define a ShowDefault type class that is a synonym for Show and Monoid. We use it in the showDefault function.

Running the test function should output:

[1,2,3] (default: [])

However, if you actually try to compile this, you will get the following compilation error:

test-monad-trans.hs:119:10: error:
    • The constraint ‘Show a’ is no smaller than the instance head
      (Use UndecidableInstances to permit this)
    • In the instance declaration for ‘ShowDefault a’

test-monad-trans.hs:119:10: error:
    • The constraint ‘Monoid a’ is no smaller than the instance head
      (Use UndecidableInstances to permit this)
    • In the instance declaration for ‘ShowDefault a’

Once again, this is the same problem we saw earlier. The a in the constraints Show a and Monoid a is no smaller than the a in the instance head ShowDefault a.

However, unlike the previous usage (which was actually an overlapping instance), there is no real danger here. We're just using ShowDefault as a synonym for something that has an instance of both Show and Monoid.

The only real danger is if we have circular instances:

class Bar a => Foo a
instance Bar a => Foo a

class Foo a => Bar a
instance Foo a => Bar a

You can see how Foo depends on Bar, and Bar depends on Foo. Even UndecidableInstances won't help us here.⁴

Use Three: Functional Dependencies and Type Families (safe)

UndecidableInstances often rears its head when dealing with functional dependencies and type families. However, it's generally safe.

This section assumes knowledge of functional dependencies and type families.

Functional Dependencies

Let's take a look at the well-known and -loved MonadState:

class Monad m => MonadState s m | m -> s where
  get :: m s
  put :: s -> m ()

Here is the instance for ReaderT:

instance MonadState s m => MonadState s (ReaderT r m) where
  get :: ReaderT r m s
  get = ReaderT $ \_ -> get

  put :: s -> ReaderT r m ()
  put s = ReaderT $ \_ -> put s

If you try to compile this, you will get the following error:

test-monad-trans.hs:132:10:
    Illegal instance declaration for ‘MonadState s (ReaderT r m)’
      The coverage condition fails in class ‘MonadState’
        for functional dependency: ‘m -> s’
      Reason: lhs type ‘ReaderT r m’ does not determine rhs type ‘s’
      Using UndecidableInstances might help
    In the instance declaration for ‘MonadState s (ReaderT r m)’

What's going on here? Well, our type class definition for MonadState has the functional dependency m -> s. This means that we know what the s will be, as long as we know what the m is. You could say that the s depends on the m.

Now what does the instance for ReaderT look like?

instance MonadState s m => MonadState s (ReaderT r m) where

This says that there is an instance MonadState s (ReaderT r m) as long as there is an instance MonadState s m. However, the compiler error tells us lhs type ‘ReaderT r m’ does not determine rhs type ‘s’. Our functional dependency has become ReaderT r m -> s. And GHC is right. ReaderT r m does not determine the s. The s is actually determined by the constraint MonadState s m.

GHC, with its overly simplistic rules, is right to get angry with us. We're not following its rules. But there's actually no danger here. We know that the s will be determined by the m, just as we want.

In order to get this to compile, we need to turn on UndecidableInstances to make GHC happy.

Type Families

Another common use of UndecidableInstances is when working with MonadTransControl, MonadBase, and MonadBaseControl.

Let's take a look at the MonadTransControl, MonadBase, and MonadBaseControl classes:

class MonadTrans t => MonadTransControl t where
  type StT t a :: *
  liftWith :: Monad m => (Run t -> m a) -> t m a
  restoreT :: Monad m => m (StT t a) -> t m a

class (Monad b, Monad m) => MonadBase b m | m -> b where
  liftBase ∷ b a -> m a

class MonadBase b m => MonadBaseControl b m | m -> b where
  type StM m a :: *
  liftBaseWith :: (RunInBase m b -> b a) -> m a
  restoreM :: StM m a -> m a

Imagine we have the following ActionT data type:

newtype ActionT m a = ActionT
  { runActionT :: ExceptT String m a
  } deriving (Functor, Applicative, Monad, MonadError String)

instance MonadTrans ActionT where
  lift :: forall m a. Monad m => m a -> ActionT m a
  lift = ActionT . (lift :: m a -> ExceptT String m a)

We can derive MonadTransControl, MonadBase, and MonadBaseControl for ActionT using helper functions provided by monad-control:

instance MonadTransControl ActionT where
  type StT ActionT a = StT (ExceptT String) a
  liftWith = defaultLiftWith ActionT runActionT
  restoreT = defaultRestoreT ActionT

instance MonadBase b m => MonadBase b (ActionT m) where
  liftBase = liftBaseDefault

instance MonadBaseControl b m => MonadBaseControl b (ActionT m) where
  type StM (ActionT m) a = StM m (StT ActionT a)
  liftBaseWith = defaultLiftBaseWith
  restoreM = defaultRestoreM

Even if you don't understand what's going on here, you can guess that we're going to have a problem when we try to compile this, because of the functional dependencies on MonadBase and MonadBaseControl.

GHC spits out four errors. Here are the first two:

test-monad-trans.hs:171:10:
  Illegal instance declaration for ‘MonadBase b (ActionT m)’
    The coverage condition fails in class ‘MonadBase’
      for functional dependency: ‘m -> b’
    Reason: lhs type ‘ActionT m’ does not determine rhs type ‘b’
    Using UndecidableInstances might help
  In the instance declaration for ‘MonadBase b (ActionT m)’

test-monad-trans.hs:174:10:
  Illegal instance declaration for ‘MonadBaseControl b (ActionT m)’
    The coverage condition fails in class ‘MonadBaseControl’
      for functional dependency: ‘m -> b’
    Reason: lhs type ‘ActionT m’ does not determine rhs type ‘b’
    Using UndecidableInstances might help
  In the instance declaration for ‘MonadBaseControl b (ActionT m)’

Did you guess right? This is exactly the same problem with functional dependencies that we saw in the previous section!

GHC also gives us the following two errors:

test-monad-trans.hs:167:8:
  Application is no smaller than the instance head
    in the type family application: StT (ExceptT String) a
  (Use UndecidableInstances to permit this)
  In the type instance declaration for ‘StT’
  In the instance declaration for ‘MonadTransControl ActionT’

test-monad-trans.hs:175:8:
  Nested type family application
    in the type family application: StM m (StT ActionT a)
  (Use UndecidableInstances to permit this)
  In the type instance declaration for ‘StM’
  In the instance declaration for ‘MonadBaseControl b (ActionT m)’

These errors are talking about the type family instances for StT and StM:

instance MonadTransControl ActionT where
  type StT ActionT a = StT (ExceptT String) a

instance MonadBaseControl b m => MonadBaseControl b (ActionT m) where
  type StM (ActionT m) a = StM m (StT ActionT a)

Just like functional dependencies, GHC has rules about what makes a type family instance "decidable". These two type families violate GHC's strict rules.

Without going in too much detail, it's sufficient to know that both of these type family instances are perfectly safe. Once again, you can turn on UndecidableInstances to get this code to compile.⁵

Conclusion

There are three main uses of UndecidableInstances:

1. Potentially overlapping instances
2. Creating type class synonyms
3. Working with functional dependencies and type families

Using UndecidableInstances for type class synonyms, functional dependencies, and type families is generally safe. There is often no other way to write the code you want to write. However, using UndecidableInstances for overlapping instances can be dangerous and a cause of major headaches.

If GHC suggests that you turn on UndecidableInstances, make sure you're not actually writing an overlapping instance.

Footnotes

tags: haskell