Haskell Combining non-determinism with error handling

Question

Suppose I'm creating a simple interpreter that can throw errors, e.g.

type Error = String

data Term = Con Int | Div Term Term

eval :: (MonadError Error m) => Term -> m Int
eval (Con a) = return a
eval (Div u v) = do
  a <- eval u
  b <- eval v
  if b == 0 then
    throwError "Division by zero"
  else
    return $ a `div` b

A typical choice of a concrete error handler, would be Either Error.

runEval :: Term -> Either Error Int
runEval = eval

Suppose now that I want to extend this interpreter to handle non-determinism. For example, I can add a term Choice Term Term that can either evaluate to its first or second argument.

data Term = Con Int | Div Term Term | Choice Term Term

I could then represent a concrete evaluation as [Either Error Int], where each item in the list represents a possible evaluation. However, I'm struggling how I can add the Choice case to my eval function without modifying the Con and Div cases.

What I tried:

eval :: (MonadError Error m, MonadPlus m) => Term -> m Int
-- The Con and Div cases remain unchanged.
eval (Choice u v) = do
  w <- return u `mplus` return v  -- pick either u or v
  eval w

runEval :: Term -> [Either Error Int]
runEval = runExceptT . eval

However, this only returns the first possible outcome, and doesn't backtrack.

> let t = Con 1 `Div` (Choice (Con 0) (Con 1))
> runEval t
[Left "Division by zero"]

What I expected: [Left "Division by zero", Right 1].

What is the right way to combine non-determinism and error-handling?

Answer 1

The root of the problem is the MonadPlus instance for ExceptT.

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

It doesn't piggyback on a MonadPlus instance of the base monad m. Instead of that, it requires a Monoid instance from the error e.

And mplus doesn't return the collection of all failures and successes. Instead of that, it returns either the first success or the monoidal combination of all the failures:

ghci> throwError ['a'] `mplus` throwError ['b'] :: Except String ()
ExceptT (Identity (Left "ab"))
ghci> throwError ['a'] `mplus` throwError ['b'] `mplus` return () :: Except String ()
ExceptT (Identity (Right ()))
ghci> return 'a' `mplus` return 'b' :: ExceptT () [] Char
ExceptT [Right 'a']

What we could try is to define our own monad having the MonadPlus instance we want (while reusing all other instances from ExceptT through deriving, to avoid boilerplate).

{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
import Control.Applicative
import Control.Monad
import Control.Monad.Trans
import Control.Monad.Except

newtype OopsT e m a = OopsT { runOopsT :: ExceptT e m a }
    deriving stock (Show)
    deriving newtype (Show,Functor,Applicative,Monad,MonadError e,MonadTrans)

-- We delegate on the Alternative/Monadplus instance of the base monad m
instance MonadPlus m => Alternative (OopsT e m) where
    empty = OopsT (ExceptT empty)       
    OopsT (ExceptT xs) <|> OopsT (ExceptT ys) = OopsT (ExceptT (xs <|> ys)

instance MonadPlus m => MonadPlus (OopsT e m) where
    mzero = empty       
    mplus = (<|>)

runEval :: Term -> [Either Error Int]
runEval = runExceptT . runOopsT . eval

Now it seems to work as intended:

ghci> let t = Con 1 `Div` (Choice (Con 0) (Con 1))
ghci> runEval t
[Left "Division by zero",Right 1]

---

One potentially troubling aspect of the MonadPlus instance for OopsT is that it doesn't seem to satisfy the v >> mzero = mzero law mentioned in the documentation. For example:

ghci> (mzero :: OopsT Char [] Int)
OopsT {runOopsT = ExceptT []}
ghci> throwError 'c' >> (mzero :: OopsT Char [] Int)
OopsT {runOopsT = ExceptT [Left 'c']}

Perhaps we could use the equivalent Alternative instance instead, which doesn't seem to require that law?