Between Applicative and Monad

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.

About these ads

2 comments on “Between Applicative and Monad

  1. Reiner Pope says:

    I think your ifB for ZipList doesn’t behave correctly with respect to _|_; it is too strict. We get

    > ifB (pure True) x _|_ = _|_ /= x

    I think it is actually quite difficult to remove the _|_. To remove it, ‘ifB bs xs ys’ cannot look at ys until it comes across a ‘False’ in bs. So, we would have to use lazy pattern matching on ys, such as

    > ifB (b:bs) ~(x:xs) ~(y:ys) = (if b then x else y):ifB bs xs ys

    But, if the first False occurs in bs after the list ys has stopped, the lazy pattern matches on ys will be suddenly refuted, giving us another _|_. For example,

    > ifB [True,False] [0] [1] = _|_

    The only way to avoid this is to ensure that bs is at most as long as xs and ys. This almost requires that we use fixed-length lists. But in that case, we actually have a Monad instance, where ‘join’ takes the diagonal.

  2. Reiner Pope says:

    Whoops. The last line was wrong. It should read

    > ifB [True,False] [0] [1] = 0:_|_

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s