MonadPlus instance for Control.Eff when Exc is member

In monad transformers, we have

instance (Monad m, Monoid e) => MonadPlus (ExceptT e m)

In extensible effects, there is no such thing as

instance (Monoid e) => MonadPlus (Eff (Exc e :> r))

I've tried implementing it, in vain. Here is what I have so far:

instance (Monoid e) => MonadPlus (Eff (Exc e :> r)) where
  mzero = throwExc mempty
  a `mplus` b = undefined $ do
                  resultA <- runExc a
                  case resultA of
                    Left l -> runExc b
                    Right r -> return $ Right r

There are 2 issues:

for mzero, GHC complains as follows:

Could not deduce (Monoid e0) arising from a use of ‘mempty’
  from the context (Monad (Eff (Exc e :> r)), Monoid e)

Why doesn't GHC match e0 with e ?

Answer (provided in comment): turn on ScopedTypeVariables

for mplus, undefined should be replaced with the inverse function of runExc, but I can't find it in the API of extensible-effects. Did I miss something ?

Rationale: I want to be able to write a <|> b within Member (Exc e) r => Eff r a, meaning:

try a
if a throws ea, try b
if b throws eb, then throw mappend ea eb

This requires an Alternative instance, which is why I am attempting to implement a MonadPlus instance in the first place.

Note: I'm using GHC 7.8.3 .

Thank you in advance for your help.

Solution

I think you may be confused about extensible effects and the desired instance MonadPlus (Eff (Exc e :> r)) shows the confusion.

If you wish to build a non-deterministic computation and also throw exceptions, you can do that already without any need for new instances. I think I may be partly responsible for the confusion by defining separate mzero' and mplus' which are fully equivalent to those in MonadPlus. Anyway, because of this equivalence, you can simply write

instance Member Choose r => MonadPlus (Eff r) where
    mzero = mzero'
    mplus = mplus'

The instance says: A computation that has a Choose effect, among others, is an instance of the MonadPlus computation. Let me stress the part ``among others''. The computation may have other effects, for example, throw exceptions. The MonadPlus instance above covers that case, as well as all others.

Thus, to use non-determinism and exceptions, you just use mplus, mzero (or mplus', mzero') along with throwExc. There is no need to define any new instances - in stark contrast with Monad Transformers.

Of course you have to decide how you want your exceptions to interact with non-determinism: should an exception discard all choices or only remaining choices? This depends on how you order your handlers, which effect gets handled first. Moreover, you can write a handler for both Choose and Exc effects (to keep the already made choices upon an exception and discard the remaining -- thus modeling Prolog's cut). The code of the library (and the code accompanying the paper) has examples of that.

Edit in reply to the amended question: If all you need is <|>, it can be implemented simply, without MonadPlus or cut. This operator is merely a form of exception handling, and is implementable as the composition of two catchError. Here is the full code

alttry :: forall e r a. (Typeable e, Monoid e, MemberU2 Exc (Exc e) r) =>
          Eff r a -> Eff r a -> Eff r a
alttry ma mb =
  catchError ma $ \ea ->
  catchError mb $ \eb -> throwError (mappend (ea::e) eb)

If the computation ma finishes successfully, its result is returned. Otherwise, mb is tried; it it finishes successfully, its result is returned. If both fail, the mappend-ed exception is raised. The code directly matches the English specification.

We use MemberU2 in the signature rather than Member to ensure that the computation throws only one type of exceptions. Otherwise, this construction is not very useful. I used the original implementation Eff.hs. That file also contains the test case.

BTW, with extensible effects there is no need to define or use type classes like MonadPlus, MonadState, etc. These type classes were intended to hide the concrete layout of the MonadTransformer stack. With extensible effects, there is nothing to hide. The crutches are no longer needed.