# Are monoids useful in optimization?

Many common operations are monoids. Haskell has leveraged this observation to make many higher-order functions more generic (Foldable being one example).

There is one obvious way in which using monoids can be used to improve performance: the programmers is asserting the operation's associativity, and so operations can be parallelized.

I'm curious if there are any other ways a compiler could optimize the code, knowing that we're dealing with a monoid.

-
Coincidentally, the author of the HLearn library has a series of posts on this now. – Xodarap Nov 25 '12 at 16:03

The compiler can optimize exponentiation with monoids. Let $\oplus$ be a binary operator calculateable in constant time such that $\oplus$ and $a_1, a_2, ... \in A$ form a monoid. Then the operation

$$\bigoplus_{[1..n]} a_k = \underbrace{a_k \oplus a_k \oplus \dots \oplus a_k}_{\text{n times}}$$

which usually takes $\cal O(n)$ time can be evaluated with the square and multiply algorithm in only $\cal O(\log n)$ time if the compiler knows that $\oplus$ obeys the monoid laws.

-
Nice observation. Maybe you should specify that you are assuming that $a_k \oplus a_k$ can be computed in $O(1)$ time. – Zach Langley Nov 24 '12 at 0:17

If you are in the constant folding/constant propagation step, whenever you come up with the identity of the monoid, you can just ignore it if it's multiplying other non-constant expressions.

-
I was thinking about this - do you know if it's actually faster? – Xodarap Nov 24 '12 at 14:42
It could make a difference inside a loop, for example. – Roberto Mizzoni Nov 24 '12 at 21:25