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^{1} (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:

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.^{2}

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:

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:

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`

:

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.^{3}

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

You can see how `Foo`

depends on `Bar`

, and `Bar`

depends on `Foo`

. Even `UndecidableInstances`

won't help us here.^{4}

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

:

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?

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.^{5}

## Conclusion

There are three main uses of `UndecidableInstances`

:

- Potentially overlapping instances
- Creating type class synonyms
- 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

My research into

`UndecidableInstances`

was kicked off by this Stack Overflow post about`UndecidableInstances`

for monad transformers. This example was taken from there.↩︎I posted a question about

`UndecidableInstances`

on reddit. Edward Kmett gave a great explanation about`UndecidableInstances`

. Most of this blog post is expanding on his answer.↩︎Using

`DefaultSignatures`

, defining the`MonadIO`

class would need to look like this:`class Monad m => MonadIO m where liftIO :: IO a -> m a default liftIO :: forall t n a. ( MonadIO n , MonadTrans t , m ~ t n ) => IO a -> t n a liftIO = (lift :: n a -> t n a) . (liftIO :: IO a -> n a)`

This says that there is a default implementation of

`liftIO`

for any`t n`

, where`n`

is an instance of`MonadIO`

, and`t`

is an instance of`MonadTrans`

.With this default siguature for

`liftIO`

, defining instances of`MonadIO`

for`ReaderT`

and`StateT`

would look like this:Very simple. You don't need to provide the function body of

`liftIO`

since the default will be used.The only major drawback of this is that it is not widely done. The

`DefaultSignatures`

machinery seems to be mainly used for generic programming, not monad typeclasses.Talking to Edward about this, he points out another drawback:

The minor downside is that if you ever wrote your own data type and started to use the 'silence all the warnings' style of code writing that some folks use, it'd complain with an error rather than a warning if the

`liftIO`

default wasn't able to typecheck.Another way to make type class synonyms is the following:

This requires the

`ConstraintKinds`

language pragma. As Edward points out, these type class synonyms have some drawbacks.↩︎User

`gelisam`

on reddit gives a good example of how`UndecidableInstances`

is safe when used with`TypeFamilies`

.↩︎

tags: haskell