Abusing Monoids: Monoidal predicate combinators

There is always another abstraction…

One of the nice things about the succinct ways we have in Haskell for writing functions is that our predicates can read very naturally:

We can compose a chain of functions that produce a Bool with normal function composition:

But often you want to compose predicates logically, with and, or and not, for example:

And that is when things start to get ugly. While the syntax is lightweight, it still gets noisy enough to get in the way of our meaning. Even more annoyingly, when we decide to abstract the predicates we are composing, we don’t gain any clarity. Imagine the decision process for deciding if a patron:

Can be served a drink in a bar:

That is ok, but having to thread the patron argument to the two predicates and combine the results, well, it all feels a bit low level! Where is the abstraction? We have abstracted out the predicates themselves, but we can’t abstract their composition. Can this not be more declarative? Perhaps our ideal syntax would be:

So much nicer! And seriously, expressing intent like this means that logic is clearer, less obscured by the ceremony of argument passing, and hopefully easier to get right.

When all you have is functions, everything looks like composition

Given we know the type of what we want to do, hoogle is the obvious place to begin one’s search. I remember searching in Hoogle for a function of the appropriate type:

so that I could create (<&>) as f (&&), before realising that this could be done in a couple of different ways.

The most obvious one (and the one that is used all the time in real code) is with Functors and Applicatives (see below for a brief discussion), which is natural given the ‘fmappy’ kind of thing we are trying to do here - we are trying to apply a function (in this case (&&)) under some other kind of object, in this case two functions.

Today if you search in Hoogle you there is an answer to this query (apply2Way - a function in an obscure and dated package called yjtools), and it still doesn’t suggest Applicatives, which is unfortunate. So let’s go ahead and find our own way to address this desire, without resorting to Applicatives at all. Perhaps surprisingly, Monoids are a perfectly suitable (if slightly round-about) way forwards. This is surprising because Applicatives and Monoids have different kinds, * -> * vs *, and yet we can encode this little boolean algebra using either abstraction.

When two (predicates) become one

For this, we need to remind ourselves that monoids let us combine two similar things. Examples of this are concatenating two strings, unioning two sets, adding two numbers. The monoid class has the following methods:

We are trying to combine two similar things! Specifically, two predicates into a third either by way of (&&) or (||). We can be clear about this by naming that idea:

Can we treat our Pred as a Monoid? Yes! And the key is that along with the obvious things, such as strings and sets and numbers, functions also form a monoid, as long as they produce a monoid (here written as lambdas to make it clear that we are taking and returning functions):

The mappend instance is particularly interesting: it enables us to compose two functions to produce a third, but not in serial as with (.), but in parallel.

Unfortunately our Pred a is not a Monoid yet, because there is no (one) Monoid instance for Bool. In fact there are two. The second piece of the puzzle is that because there are multiple monoid instances for some data types, their different instances are associated with newtypes, to allow us to specify which one we mean.

Numbers have Sum and Product, representing the monoids (+, 0) and (*, 1) respectively. Objects with orderings (members of the Ord) have the semigroup instances Min and Max (where (<>) is min and max) as well as Monoid instances if they are Bounded. Bools have All and Any, representing the monoids (&&, True) and (||, False). With this in mind we can create our little predicate combinators:

The combine helper just encapsulates the common logic for mappending two Pred a, by allowing the isomorphic functions that select the monoid to be passed in. With this we get:

and now we can compose complex conditions in their own terms, producing a simple boolean DSL, capable of handling even complex nested conditions:

While the higher kinded typeclasses of Functors and Applicatives are a more natural fit for functions, it is always satisfying to see that the same thing can be approached from different directions.

Postscript: The Applicative Approach

The (more obvious) Applicative solution:

Like with Monoids, it is helpful to remind ourselves of the Applicative and Functor instances for (->), the type of functions, here with the specialised signatures added for clarity, and reminding ourselves that (->) is written in infix notation, so that (->) a b and a -> b are equivalent:

While we don’t see our (<&>) here just yet, it is worth remembering that the type of pure (&&) <*> isOldEnough would be:

and if we have a Person -> Bool -> Bool, we can use use <*> again on a second predicate:

or, more simply (and making use of <$>, the infix synonym for fmap:

Can I get a lift here?

When all the infix operators start making your eyes bleed, we can use liftA2 from the Applicative class, which does exactly this:

If we look back at the fearsome type signature from before:

It should hopefully jump out at us that the last three values are all of the same shape, differing only in their final parameter - i.e. they are all forms of d -> ?. This should have triggered our senses earlier, and helped us discover this solution lurking in the Functor/Applicative/Monad hierarchy, by noting that we are trying to lift the function (a -> b -> c) so that it operates on (d -> a) and (d -> b) and (d -> c), i.e. lifting it into the (->) d Functor.

which means (if we can be bothered considering how trivial this is), we could simply have defined (<&>) = liftA2 (&&) in the very beginning.