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

On Mon, Jun 6, 2011 at 3:39 PM, Casey McCann wrote:

On Mon, Jun 6, 2011 at 12:19 PM, Brent Yorgey 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