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