# 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. 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. Nov 24 '12 at 0:17