Last night in #haskell, there was some interesting discussion going on, in which we discovered a class of data structures that seems to fit in between Applicative and Monad. A foreword though: Most of the credit for this article should go to Brent Yorgey, Cale Gibbard, Peaker and Tristan Seligmann – the article is the product of a discussion with them last night in which they did most of the work.

### Why doesn’t Applicative cut the mustard

One of the major drawbacks of Applicative is that you can’t make choices without evaluating too much. If we attempt to use `liftA3 if'`

, we find that we evaluate both branches, no matter what we get back from our predicate.

### So just use Monad, right?

Well no, bind/join give us too much power, they let us make choices between an infinite number of functions, we only want the ability to make a choice between a finite number of branches.

We can define this class then:

class Applicative b => Branchy b where ifB :: b Bool -> b a -> b a -> b a

We can add a pair of laws to this that force this to really be an if like operation, and to make sure that we get lazyness properly:

ifB (pure True ) x y = x ifB (pure False) x y = y

These laws though may not be complete in getting us to a useful class. Cale has suggested this additional law to get us closer, but holes in the laws are a definite place to do some work hashing this out.

f <*> ifB b x y = ifB b (f <*> x) (f <*> y)

So then, do we actually have something useful here? For that, we would have to find two things – an Applicative which is not a Branchy (to show that we’ve not just reinvented applicatives), and a Branchy that’s not a Monad. Well, clearly `Const a`

is not a Branchy, a `Const a Bool`

does not actually contain a Bool with which to decide which branch to take. And, here’s the useful Branchy that’s not a monad:

instance Branchy ZipList where ifB (ZipList ps) (ZipList xs) (ZipList ys) = ZipList $ zipWith3 if' ps xs ys

### Using Either instead

Andrea Vezzosi commented this morning that the interface would be rather nicer if rather than using `ifB`

, we used `eitherB :: b (Either c d) -> b (c -> e) -> b (d -> e) -> b e`

. While each can be implemented in terms of the other, `eitherB`

allows for a little more efficiency. The following implementation of `eitherB`

evaluates the either twice:

eitherB fe fl fr = ifB (isLeft <$> fe) ((.fromLeft) <$> fl) ((.fromRight) <$> fr) <*> fe

This version of the class also makes the connection with ArrowChoice rather clearer.

I’d really appreciate everyone’s comments on this topic.