On Mon, Jun 6, 2011 at 9:19 AM, Brent Yorgey wrote:

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

I take it you would prefer the following signature class (Applicative m) => Monad m where -- -- Regards, KC

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

On 6/6/11 7:05 PM, Casey McCann wrote:

On Mon, Jun 6, 2011 at 5:32 PM, Matthew Steele wrote:

...

...

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.

How would it violate the laws for Identity or Reader?

It wouldn't violate the laws for those (or other benign effects, given a suitable definition of "benign"), but it'd clearly violate the laws for things like Writer, ST, IO,... -- Live well, ~wren