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!
newtype Sort a =
Sort {
getSorted :: [a]
} deriving (Show, Eq)
-- So long as the elements can be ordered we can combine two sorted lists using mergeSort
instance (Ord a) => Monoid (Sort a) where
mempty = Sort []
mappend (Sort a) (Sort b) = Sort $ mergeSort a b
-- simple merge sort implementation
mergeSort :: Ord a => [a] -> [a] -> [a]
mergeSort [] xs = xs
mergeSort xs [] = xs
mergeSort (x:xs) (y:ys)
| y < x = y : mergeSort (x : xs) ys
mergeSort (x:xs) ys = x : mergeSort xs ys
-- We'll keep the 'Sort' constructor private and expose this smart constructor instead so we can
-- guarantee that every list inside a `Sort` is guaranteed to be sorted.
-- We could use a simple sort function for this, but might as well use mergeSort since
-- we already wrote it.
toSort :: [a] -> Sort a
toSort = foldMap (Sort . pure)Let's try it out:
> toSort [1, 5, 2, 3] `mappend` toSort [10, 7, 8, 4]
Sort {getSorted = [1,2,3,4,5,7,8,10]}
> foldMap (toSort . pure) [5, 2, 3, 1, 0, 8]
Sort {getSorted = [0,1,2,3,5,8]}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!
Hopefully you learned something 🤞! If you did, please consider checking out my book: It teaches the principles of using optics in Haskell and other functional programming languages and takes you all the way from an beginner to wizard in all types of optics! You can get it here. Every sale helps me justify more time writing blog posts like this one and helps me to continue writing educational functional programming content. Cheers!