Why can AccValidation not have a Monad instance?

Question

From the documentation of the validation package:

The AccValidation data type is isomorphic to Either, but has an instance of Applicative that accumulates on the error side. That is to say, if two (or more) errors are encountered, they are appended using a Semigroup operation.

As a consequence of this Applicative instance, there is no corresponding Bind or Monad instance. AccValidation is an example of, "An applicative functor that is not a monad."

It isn't evident to me why this is a consequence. I can imagine a Monad instance for AccValidation that behaves like Either - What would make this unlawful?

Answer 1

The (<*>) = ap exigence can be stated explicitly in terms of (>>=):

u <*> v = u >>= \f -> fmap f v -- [1]

Now, given the Functor and Applicative instances for AccValidation, we have:

fmap _ (AccFailure e) = AccFailure e -- [2]

AccFailure e1 <*> AccFailure e2 = AccFailure (e1 <> e2) -- [3]

If we make u = AccFailure e1 and v = AccFailure e2 in [1], we get:

AccFailure e1 <*> AccFailure e2 = AccFailure e1 >>= \f -> fmap f (AccFailure e2)

Substituting [2] and [3] into that leads us to:

AccFailure (e1 <> e2) = AccFailure e1 >>= \_ -> AccFailure e2 -- [4]

The problem is that it is impossible to write a (>>=) such that [4] holds. The left-hand side depends on an e2 value which must originate, on the right-hand side, from applying \_ -> AccFailure e2 :: Semigroup e => a -> AccValidation e b. However, there is nothing to which it can be applied -- in particular, e1 has the wrong type. (See the final two paragraphs of Cactus' answer for further discussion of this point.) Therefore, there is no way of giving AccValidation a Monad instance which is consistent with its Applicative one.