Monoidal Sorting


Jul 22, 2018

As I dive deeper into functional programming I'm beginning to think that monoids can solve most problems. In general monoids work well in combination with other structures and algorithms, for instance Finger Trees, and folds!

This post is just yet-another-demonstration of how adaptable monoids can really be by solving a problem most people wouldn't immediately associate with monoids.

Sorting

We're going to write a wrapper around lists which rather than the traditional monoid for lists (concat) instead sorts the two into each other; not much to talk about really, lets see the code!

Let's try it out:

Nothing too complicated really! mappend over sorted lists just sorts the combined list; we have the benefit in this case of knowing that any list within a Sort is guaranteed to be sorted already so we can an efficient merge sort algorithm. This doesn't make much difference when we're appending small sets of values together, but in particular cases like FingerTrees where intermediate monoidal sums are cached it can really speed things up!

Just like that we've got a cool monoid which sorts lists for us, and by combining it with foldMap we can easily sort the values from any foldable structure. One other benefit here is that since we know monoids are associative, if we have a huge list of elements we need sorted we can actually split up the list, sort chunks in parallel and combine them all and we have a guarantee that it'll all work out.

Anyways, that's about it for this one, nothing to write home about, but I think it's fun to discover new monoids!