Accumulating independent errors

Mar. 13 2017haskell

The 'Either' monad short-circuits as soon as we encounter a single Left. This can be a little limiting when we're using it for error handling! When errors have nothing to do with one another, it would be nice to report as many independent errors as possible.

This can be done fairly easily if our program is in applicative style. If an expression is in Either and we never need to inspect a Right using (>>=), we can compute every value in the expression and list all the lefts. There are a couple of validation functors around Hackage that will do this for you. However, applicative style is not the most intuitive thing. I've been writing Haskell for a couple of years, for work and pleasure. Applicative only started to feel intuitive when it was buying me something: when a library forced me into applicative style, or when it drastically improved results or error reporting. Lately I'll jump through all kinds of hoops to make a program applicative, but it took a while to develop this zeal.

Far more commonly, I'll write a bunch of code in Either or EitherT, because I can't easily express the data flow without the monad. I'll finish my work, and test all my functions. Then, I'll need to chuck it at a batch workload. Suddenly, short-circuiting is not all that helpful! Won't somebody think of the users?

This post uses an error-accumulating applicative functor to implement some handy Either combinators, including one I use quite heavily, sequenceEither. The final implementation uses the Errors type from transformers, a package most any Haskell project transitively depends on.

Implementing apply

We're interested in accumulating independent errors.

The most common data structures for accumulating things include lists, vectors, arrays, difference lists, and sets. These types All of these bar Set form Haskell monoids. So, let's restrict our error type to Monoid, for expedience. You might also accept Semigroup or just pass around an associative function.

When dealing with an independent set of expressions, we can usually call on an Applicative. The key (<*>) function (apply) encodes a finite pipeline of function application with linear data dependency, meaning functions in the pipeline can't branch on their arguments. We decide what we're getting up front, then process it with a pure function. If the error-throwing expressions are truly unrelated, there's probably an Applicative somewhere.

Let's first implement apply given the Monoid constraint, and specialised to Either:

applyE :: Monoid e => Either e (a -> b) -> Either e a -> Either e b
applyE f x =
  case (f, x) of
    (Left e, Right _) ->
      Left e
    (Right _, Left e) ->
      Left e
    (Left e1, Left e2) ->
      Left (e1 <> e2)
    (Right g, Right y) ->
      Right (g y)

... and examining this in GHCi, we see it works well enough:

λ> (,,) `fmap` Left [10] `applyE` Right True `applyE` Left [43] :: Either [Int] (Bool, Bool, Bool)
Left [10,43]
λ> (,,) `fmap` Right False `applyE` Right True `applyE` Right False :: Either [Int] (Bool, Bool, Bool)
Right (False,True,False)

Trying and failing to implement bind

If you're unfamiliar with the beef between Applicatives and Monads, like I am every second Thursday, it's worth sitting down with GHC for five minutes and trying to implement bind / (>>=) while retaining every error that appears in a Left. It can't be done, because we have no a with which to construct a b:

bindE :: Monoid e => Either e a -> (a ->  Either e b) -> Either e b
bindE e1 f =
  case e1 of
    Right g ->
	  f g
    Left e ->
	  case f _ of {- how to fill this hole? -}
	    Right _ ->
		  Left e
	    Left d ->
		  Left (e <> d)

So, since we can keep Either's fmap and we can implement (<*>) with our error-accumulating semantics, we've earned ourselves Functor and Applicative instances. However, since bindE didn't really work out, Monad is out of the question. Applicative functors are indeed the right tool for this job.

The Errors type in transformers

Ross Paterson added lifted applicatives to the transformers package at some point, looks like it was around 2010, in the Control.Applicative.Lift namespace. If I weren't so lazy, I'd figure out the lower version bounds for you. Alas! It's been there long enough. It's already in your dependency tree.

A lifted applicative extends another applicative with an additional constructor, Other.

We also need to understand the Constant functor, from Data.Functor.Constant. As a functor, Constant is designed to always discard its arguments. The Applicative instance for Constant only exists when the type parameter has a Monoid instance. When that is the case, ap is essentially the same as mappend / (<>).

In short, Lift (Constant x) a is a Functor isomorphic to Either x a, and an Applicative where ap is equivalent to applyE from earlier. It is provided in Control.Applicative.Lift as the Errors type synonym.

If you're writing programs directly in applicative style, you might want to create your own newtype around Errors to avoid the type synonym. It's a little unfortunate that it leaks the implementation details of Lift and Constant. Nevertheless! Despite subtle niggles like naming and newtypes, transformers is always there for you.

Accumulating errors in Either with Errors

Suppose we work mostly in Either, but have some join points at which we combine big groups of expressions (like a batch data processor, or a type checker). We want to lazily maximise error reporting at the last second without restructuring everything to be Applicative.

First, let's make sure we know how to hoist expressions into Errors:

import Control.Applicative.Lift
import Data.Either
import Data.Functor.Constant
import Data.Monoid

hoistErrors :: Either e a -> Errors e a
hoistErrors e =
  case e of
    Left es ->
      Other (Constant es)
    Right a ->
      Pure a

Now, let's use it to traverse something:

-- | Like 'sequence', but accumulating all errors in case of at least one 'Left'.
sequenceEither :: (Monoid e, Traversable f) => f (Either e a) -> Either e (f a)
sequenceEither =
  runErrors . traverse hoistErrors
λ> sequenceEither [Left [10], Right True, Left [43]]
Left [10, 43]
λ> sequenceEither [Right True, Right False, Right True]
Right [True, False, True]

(I really love sequenceEither, and use it all the time. It's not much, but it works magic. I hope someone out there finds it useful!)

We might also want to have the monad transformer version handy. This one is in terms of ExceptT, since we're all using that these days. I find it very useful for top-level application logic.

-- | Evaluate each action in sequence, accumulating all errors in case of a failure.
-- Note that this means each action will be run independently, regardless of failure.
sequenceExceptT ::
    (Monad m, Monoid x, Traversable t)
  => t (ExceptT x m a)
  -> ExceptT x m (t a)
sequenceExceptT es = do
  es' <- lift (traverse runExceptT es)
  ExceptT (return (sequenceEither es'))


There is quite a bit of prior art on this topic that you might want to look at, various validation functors with varying dependency footprints, bells and whistles. I won't mention them here, because Errors is fine.