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

[Casey McCann]

On Mon, Jun 6, 2011 at 12:19 PM, Brent Yorgey <byorgey at seas.upenn.edu> wrote:
> 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.

Is this truly an intermediate variety of structure, though? Or just
different operations on existing structures? With Applicative, there
are examples of useful structures that truly can't work as a Monad,
the usual example being arbitrary lists with liftA2 (,) giving zip,
not the cartesian product. Do you know any examples of both:

1) Something with a viable instance for Branching, but either no Monad
instance, or multiple distinct Monad instances compatible with the
Branching instance
2) Same as above, except for a viable Applicative instance without a
single obvious Branching instance

In other words, an implementation of branch for some type that's not
obviously equivalent to one of these definitions:

branchMonad mb t f = do { b <- mb; if b then t else f }
branchApplicative = liftA3 (\b t f -> if b then t else f)

I can certainly believe that such an example exists, but I can't think
of one. In particular, it doesn't seem to be possible for ZipList (the
obvious almost-instance does not quite do what you may think it does).

If memory serves me, sometimes the limited nature of Applicative
allows a more efficient implementation than Monad, and in such cases I
can easily believe that branch could be made more efficient than the
generic form based on Monad. But that's not terribly persuasive for
creating a type class, I don't think.

- C.