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

[Matthew Steele]

On Mon, Jun 6, 2011 at 3:39 PM, Casey McCann <syntaxglitch at gmail.com> wrote:
> 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

I think Branching is to Monad what ArrowChoice is to ArrowApply.
Branching allows the shape of the computation to depend on run-time
values (which you can't do with Applicative), but still allows only a
finite number of computation paths.  By purposely making a functor an
instance of Branching but _not_ of Monad, you allow it to have some
amount of run-time flexibility while still retaining the ability to
"statically" analyze the effects of a computation in that functor.

> branchApplicative = liftA3 (\b t f -> if b then t else f)

This definition doesn't satisfy the laws given for the Branching
class; it will execute the effects of both branches regardless of
which is chosen.

Cheers,
-Matt