MonadError instance for a Free Monad

Question

I have created a very useful Free Monad out of a sum data type. That abstracts access to a persistent data store:

data DataStoreF next = 
     Create    Asset                           ( String -> next)
  |  Read      String                          ( Asset  -> next)
  |  Update    Asset                           ( Bool   -> next)
  |  UpdateAll [Asset]                         ( Bool   -> next)
  |  Delete    Asset                           ( Bool   -> next)
  |  [...] -- etc. etc.
  |  Error     String

type DataStore = Free DataStoreF

I would like to make DataStore an instance of MonadError with the error message handled as (Free (Error str)):

instance MonadError String DataStore where
  throwError str = errorDS str
  catchError (Free (ErrorDS str)) f = f str
  catchError x _ = x

But I am running into Overlapping Instances errors.

What is the proper way to make the DataStore monad and instance of MonadError?

Answer 1

The Free type already provides a MonadError instance for all free monads:

instance (Functor m, MonadError e m) => MonadError e (Free m) where { ... }

When you write type DataStore = ..., you are simply defining a type alias, which is basically a type-level macro. All uses of the DataStore type are replaced with its definition. This means that using DataStore is indistinguishable from using Free DataStoreF directly, so when you do this:

instance MonadError String DataStore where { ... }

…you are actually doing this:

instance MonadError String (Free DataStoreF) where { ... }

…and that conflicts with the instance defined above.

To circumvent that, you should define a newtype to produce an entirely fresh type that can have its own instances on it, unrelated to the ones defined on Free. If you use the GeneralizedNewtypeDeriving extension, you can avoid a lot of the boilerplate that would otherwise be required by a separate newtype:

{-# LANGUAGE GeneralizedNewtypeDeriving -}

data DataStoreF next = ...

newtype DataStore a = DataStore (Free DataStoreF a)
  deriving (Functor, Applicative, Monad)

instance MonadError String DataStore where { ... }

This should avoid the overlapping instance problem without the need to write out all the Functor, Applicative, and Monad instances manually.

Answer 2

Your instance and the instance given by the library:

instance (Functor m, MonadError e m) => MonadError e (Free m)

are indeed overlapping, but this does not mean that they are incompatible. Note that the above instance is 'more general' in a sense than yours - any type which would match your instance would match this one. When one uses the OverlappingInstances extension (or with modern GHC, an {-# OVERLAP{S/PING/PABLE} #-} pragma), instances may overlap, and the most specific (least general) instance will be used.

Without the extension, e.g. throwError "x" :: DataStore () gives the type error:

* Overlapping instances for MonadError [Char] (Free DataStoreF)
    arising from a use of `throwError'
  Matching instances:
    instance [safe] (Functor m, MonadError e m) =>
                    MonadError e (Free m)
      -- Defined in `Control.Monad.Free'
    instance [safe] MonadError String DataStore

but with the addition of a pragma

instance {-# OVERLAPS #-} 
  MonadError String DataStore where

the expression throwError "x" :: DataStore () still matches both instances, but since one is more specific than the other (the one you wrote) it is selected:

>throwError "x" :: DataStore ()
Free (Error "x")