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
```

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)