How could we know that an applicative can't be a Monad?

Question

From the example of Validation (https://hackage.haskell.org/package/Validation), I'm trying to get an intuition of detecting how/why an applicative could not be a Monad (Why can AccValidation not have a Monad instance?)

Could you challenge my reasoning ?

I think about a monad in the way we handle behind the join (m ( m b) -> m b), let's develop my understanding with an example like Validation:

in data Validation err a, the functor structure is (Validation err). When you look at the definition of the bind for Monad and specializing the types for Validation you get the following :

(>>=)  :: m a -> (a -> m b) -> m b
(>>=)  :: (Validation err) a -> (  a -> (Validation err) b) -> (Validation err) b

if you beta reduce (>>=) you'll get :

m a -> (a -> m b) -> m b // if we apply (m a) in the monadic function  
m ( m b) -> m b

then to get the result of (>>=) which is m b, you'll use join :

join              :: (Monad m) => m (m a) -> m a
join x            =  x >>= id

If you play with the types you'll get :

join m ( m b ) = m ( m b) >>= (\(m b) -> m b -> m b) which gives m b

So that join just drop the outermost structure, only the value in the innermost type (the value of the innermost functor) is kept/transmitted through the sequence.

In a monad we can't pass some information from the functor structure (e.g Validation err) to the next 'action', the only think we can pass is the value. The only think you could do with that structure is short-circuiting the sequence to get information from it.

You can't perform a sequence of action on the information from the functor structure (e.g accumulating something like error..)

So I would say that an applicative that is squashing its structure with some logic on its structure could be suspicious as not being able to become a Monad ?

Answer 1

This isn't really an answer, but it's too long for a comment.

This and other referenced discussions in that thread are relevant. I think the question is posed sort of backwards: all Monads naturally give rise to an Applicative (where pure = return, etc); the issue is that most users expect/assume that (where a type is instance Monad) the Applicative instance is semantically equivalent to the instance to which the Monad gives rise.

This is documented in the Applicative class as a sort of law, but I'm not totally convinced it's justified. The argument seems to be that having an Applicative and Monad that don't agree in this way is confusing.

My experience using Validation is that it's a nightmare to do anything large with it, both because the notation becomes a mess and because you find you have some data dependencies (e.g. you need to parse and validate one section based on the parse of a previous section). You end up defining bindV which behave like an Error monad >>= since a proper Monad instance is considered dubious.

And yet using a Monad/Applicative pair like this does what you want: especially when using ApplicativeDo (I imagine; haven't tried this), the effect of writing your parser (e.g.) in Monadic style is that you can accumulate as many errors as possible at every level, based on the data dependencies of your parsing code. Haxl arguably fudges this "law" in a similar way.

I don't have enough experience with other types that are Applicative but not Monad to know whether there's a sensible rule for when it's "okay" for the Applicative to disagree in this way. Maybe it's totally arbitrary that Validation seems to work sensibly.

In any case...

I'm not sure how to directly answer your question. I think you start by taking the laws documented at the bottom of Applicative class docs, and flip them, so you get:

 return = pure
 ap m1 m2 = m1 <*> m2

If ap were a method of Monad and the above was a minimal complete definition then you'd simply have to test whether the above passed the Monad laws to answer your question for any Applicative, but that's not the case of course.