[Haskell-cafe] Can it be proven there are no intermediate "useful" type classes between Applicative Functors & Monads?

[Brent Yorgey]

On Sun, Jun 05, 2011 at 12:51:47PM -0700, KC wrote:
> If new intermediate classes crop up then there would be no point in fixing
> 
> class (Applicative m) => Monad m where
> 
> since it would have to be changed if new intermediate classes are
> found.

There actually is at least one intermediate class that I know of,

  class Applicative m => Branching m where
    branch :: m Bool -> m a -> m a -> m a

subject to the laws

  branch (m *> pure True)  t f == m *> t
  branch (m *> pure False) t f == m *> f

or something like that.  The idea is that Applicative computations
have a fixed structure which is independent of intermediate results;
Monad computations correspond to (potentially) infinitely branching
trees, since intermediate results (which could be of an infinite-sized
type) can be used to compute the next action; but Branching
computations correspond to *finitely* branching trees, since future
computation can depend on intermediate results, but only one binary
choice at a time.

However, I doubt this qualifies as "useful" no matter how you define
it, although I would not be sad to be proven wrong.  In any case, I
think it is ethically indefensible to procrastinate in doing something
good just in case you might miss an opportunity to do something
perfect later.

-Brent