title: Haskell Combining non-determinism with error handling
body: <p>Suppose I'm creating a simple interpreter that can throw errors, e.g.</p>
  <pre><code>type Error = String
  
  data Term = Con Int | Div Term Term
  
  eval :: (MonadError Error m) =&gt; Term -&gt; m Int
  eval (Con a) = return a
  eval (Div u v) = do
    a &lt;- eval u
    b &lt;- eval v
    if b == 0 then
      throwError &quot;Division by zero&quot;
    else
      return $ a `div` b
  </code></pre>
  <p>A typical choice of a concrete error handler, would be <code>Either Error</code>.</p>
  <pre><code>runEval :: Term -&gt; Either Error Int
  runEval = eval
  </code></pre>
  <p>Suppose now that I want to extend this interpreter to handle non-determinism. For example, I can add a term <code>Choice Term Term</code> that can either evaluate to its first or second argument.</p>
  <pre><code>data Term = Con Int | Div Term Term | Choice Term Term
  </code></pre>
  <p>I could then represent a concrete evaluation as <code>[Either Error Int]</code>, where each item in the list represents a possible evaluation. However, I'm struggling how I can add the <code>Choice</code> case to my <code>eval</code> function without modifying the <code>Con</code> and <code>Div</code> cases.</p>
  <h1>What I tried:</h1>
  <pre><code>eval :: (MonadError Error m, MonadPlus m) =&gt; Term -&gt; m Int
  -- The Con and Div cases remain unchanged.
  eval (Choice u v) = do
    w &lt;- return u `mplus` return v  -- pick either u or v
    eval w
  
  runEval :: Term -&gt; [Either Error Int]
  runEval = runExceptT . eval
  </code></pre>
  <p>However, this only returns the first possible outcome, and doesn't backtrack.</p>
  <pre><code>&gt; let t = Con 1 `Div` (Choice (Con 0) (Con 1))
  &gt; runEval t
  [Left &quot;Division by zero&quot;]
  </code></pre>
  <p>What I expected: <code>[Left &quot;Division by zero&quot;, Right 1]</code>.</p>
  <p>What is the right way to combine non-determinism and error-handling?</p>