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?

Gosser

What instance do you imagine? Note that the applicative instance for Either accumulates on the non-error side. – Higherup

You can't to run later "stages" if an earlier stage failed. With Applicative, you can still compute the later stages even if you can't apply them to get a successful result (and thus you can know if the computation of the later stages failed). With Monad, each stage returns the next one, so you don't even know what the later stages are supposed to be. – Lashandralashar

@Higherup The applicative for Either doesn't "accumulate" at all in the same sense that AccValidation accumulates, right? – Gosser

@ChrisMartin While ap = (<*>) is part of the contract of the Monad class, as stated by the documentation you linked to, it isn't, strictly speaking, a monad law -- it's just that it would be horribly confusing if it didn't hold. Here is a highly relevant question, with answers and comments that approach the issue from many different perspectives. – Inessive

Answer 1

Mechanically, the Either-ish Monad instance for AccValidation would be

-- The (Monoid err) context is not used for anything, 
-- it's just there to satisfy the Applicative super-instance
instance (Monoid err) => Monad (AccValidation err) where
    return = AccSuccess
    AccFailure err >>= f = AccFailure err
    AccSuccess x >>= f = f x

which would mean we have

AccFailure err1 <*> AccFailure err2 = AccFailure (err1 <> err2)
AccFailure err1 `ap` AccFailure err2 = AccFailure err1

which breaks the monad law of <*> = ap.

Intuitively, it can't be made a monad because in a monad, the effect (i.e. the validation failures) of a computation can depend on previously bound results. But in the case of a failure, there is no result. So Either has no choice than to short-circuit to failure in that case, since there is nothing to feed to the subsequent functions on right-hand sides of (>>=)s.

This is in stark contrast to applicative functors, where the effect (in this case, the validation failures) cannot depend on other results, which is why we can get all validation failures without having to feed results (where would they come from?) from one computation to the other.

Oswin

isn't ap just an alias for <*> like fmap/<$>? – Gynaecology

@Gynaecology Not exactly. ap is (<*>) implemented using the Monad methods. ap is to (<*>) what liftM is to fmap. – Inessive

Answer 2

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.

Inessive