Jaguarpaw Blog - Associative operations are function composition in disguise

by Tom Ellis on 18th November 2011

Associative operations are function composition in disguise

Last month on Haskell Reddit, Gabriel Gonzalez wrote

I protect myself from bugs by using composition in any category as much as possible.

I’ve heard you say things like this on a few occasions. As far as I can tell, the only information content to your statements are that “associative operations are good” :). I don’t see what that observation has to do with category theory specifically. Plain ol’ categories are not the only algebra containing associative operations.

It seems that categories just one algebraic structure among many that provide associative operations. That started me wondering. Can we represent all other associative structures as categories? The answer is “yes”. Categories are the only structure that provides associative operations, at least for a class of associative structures so broad that I can’t see how to extend it. In fact, you don’t need arbitrary categories to encode associative operations. You just need the category of functions.

Let’s take a simple example. A Monoid is a type with an associative operation (<>) and identity mempty. It is well known that “multiplication” under (<>) can be replaced with function composition in the following way

g1 <> g2 <> ... <> gn = ((g1 <>) . (g2 <>) . ... . (gn <>)) mempty

so we can define

liftMon :: Monoid m => m -> (m -> m)
liftMon g = (g <>)

unliftMon :: Monoid m => (m -> m) -> m
unliftMon f = f mempty

Then unliftMon . liftMon = id, and

unliftMon (liftMon g1 . liftMon g2 . ... . liftMon gn)
          = g1 <> g2 <> ... <> gn

So the monoid “multiplication” can actually be encoded as function composition. What about when we have more than one associative operation? That is, what do we do with an expression of the form

x1 `op1` x2 `op2` x3 `op3` ... `opn` xn+1

where the operations are mutually associative in the sense that the value of the expression does not depend on how we bracket subexpressions? Consider the following, almost trivial, definitions.

liftVal :: a -> (a -> b -> c, b) -> c
liftVal x ((.*), y) = x .* y

liftOp :: (d -> c -> e) -> c -> (d -> c -> e, c)
liftOp (.*) z = ((.*), z)

(<|) :: a -> b -> a
x <| y = x

unliftVal :: ((a -> () -> a, ()) -> a) -> a
unliftVal f = f ((<|), ())

(<|) is const in disguise. Observe that unliftVal . liftVal = id even if we don’t assume any associativity conditions. Further note that

(liftVal x . liftOp (.*)) y = liftVal x ((.*), y) = x .* y

liftVal x . liftOp (.*) = (x .*)

Now manipulate our expression

x1 `op1` x2 `op2` x3 `op3` ... `opn` xn+1
= x1 `op1` x2 `op2` x3 `op3` ... `opn` xn+1 <| ()
= x1 `op1` (x2 `op2` (x3 `op3` ( ... (xn `opn` (xn+1 <| ())) ... )))
= ((x1 `op1`) . (x1 `op2`) . (x3 `op3`) . ... . (xn `opn`) . liftVal xn+1) ((<|), ())
= (liftVal x1 . liftOp `op1` . liftVal x2 . liftOp `op2` . liftVal x3
          . liftOp `op3` . ... liftVal xn . liftOp `opn` . liftVal xn+1)  ((<|), ())
= unliftVal (liftVal x1 . liftOp `op1` . liftVal x2 . liftOp `op2` . liftVal x3
          . liftOp `op3` . ... liftVal xn . liftOp `opn` . liftVal xn+1)

That’s hard to read, so rewrite it as

lV = liftVal
lO = liftOp
u = unliftVal

x1 `op1` x2 `op2` x3 `op3` ... `opn` xn+1
= u (lV x1 . lO `op1` . lV x2 . lO `op2` . lV x3 . lO `op3`
           . ... lV xn . lO `opn` . lV xn+1)

It’s still not easy to read, but does highlight the takeaway message: categories capture everything needed for families of mutually associative operations. And not just categories in general, but the category of function composition is enough.

I would be interested if anyone can tell me if there is a larger class of associative algebraic structures that I should consider.