Monoids - Algebra Driven Design

Here's another interesting monoid from chris penner:
https://chrispenner.ca/posts/monoid-sort

the funny thing is that

toSort :: [a] -> Sort a
toSort = foldMap (Sort . pure)

seems to essentially be an insertion sort

He mentions them in his post, but anybody who wants to see a really compelling use-case for monoids should look at finger trees.

That's the thing behind Data.Seq, right?

Data.Sequence rather

Yes, Data.Sequence is basically a finger tree where our monoid is Sum and we map each element to 1.

looks like he has a post on those too
https://chrispenner.ca/posts/intro-to-finger-trees

I'm not sure that tosort function justifies itself vs concat/join-collection with sort.

E.g why not just define what sort means over collection at that point? Is tosort in addition to sort in some way?

I guess this is more of an exploratory thing than a practical one :smile:

This is parallelizable! :)
nvm got confused

You could do Sort . sort right?

Oh wait no the concat isn't going to work :thinking:

Oh no that's fine

I think the idea was just to use the mergeSort function he already defined earlier. In an actual library, yeah, you'd define the smart constructor as toSort = Sort . sort

James Sully said:

the funny thing is that

toSort :: [a] -> Sort a
toSort = foldMap (Sort . pure)

seems to essentially be an insertion sort

The specific implementation of sort you get out is related to the implementation of foldMap.

You could define a variant of foldMap that recursively splits a list in half and merges them together with mconcat or <>.
This is normally a bad idea because we have to

1. Traverse the list to find its length

   Automatically fails here on infinite lists, even if <> can short circuit

2. Juggle around multiple intermediate values instead of 1 single accumulator (bad for efficiency/stack overflows)

but for certain monoids, we can get an improvement.

-- WARNING: UNTESTED CODE, DON'T USE THIS IN PRACTICE
import Data.List (splitAt)

foldMap' :: Monoid b => (a -> b) -> [a] -> b
foldMap' f xs = reduce . fmap f $ xs

reduce :: Monoid b => [b] -> b
reduce xs = reduceFirstN (length xs) xs

reduceFirstN :: Monoid b => Int -> [b] -> b
reduceFirstN 0 xs = mempty
reduceFirstN _ [x] = x
reduceFirstN n [x, y] | n > 1 = x <> y
reduceFirstN len xs = left' <> right'
    where
      halfLen = len `quot` 2
      (left, right) = splitAt halfLen xs
      left' = reduceFirstN halfLen left
      right' = reduceFirstN (len - halfLen) right

If you use this toSort = foldMap' (Sort . pure) you basically get classical merge sort something much more like classical merge sort.
(I'm still worried that my looping over the left half of the list messes up the nlog n time because splitting linked lists is slow)

Huh, true, I guess I was assuming that foldMap works left to right, but associativity of monoids means we clearly don't need to necessarily.

Your choice of what foldMap to use is like your choice of what sort to use.
It shouldn't affect the answer you get but it can impact the performance of your code.
(Modulo non-termination because you made your code too strict)

As a corollary, because foldMap' should produce the same results as foldMap does, you can

1. Benchmark your code
2. Replace 1 or more foldMaps with foldMap's
3. Make sure your code doesn't crash/infinite loop now because foldMap' isn't as lazy as foldMap is
4. Pick the faster option

and you don't need to worry about your answers changing.

I'm confused daniel, you said the problem was you need to traverse the list. But your implementation knows the length.

Efficiency in sort depends on pre existing knowledge of the type and collection.

I don't yet read Haskell so I'm inferring a lot.

drew verlee said:

I'm confused daniel, you said the problem was you need to traverse the list. But your implementation knows the length.

Efficiency in sort depends on pre existing knowledge of the type and collection.

I don't yet read Haskell so I'm inferring a lot.

There are 2 problems with my foldMap'.
They are caused by the following function calls

1. length xs and
2. splitAt halfLen xs

The problem with length xs is that this only works for non-infinite lists.
For example

countingNums :: [Integer]
countingNums = [1..]

Is a list of all Positive Integers.

If you try to compute its length, you'll take infinite time because you'll never reach the end of the list where you would stop and return how long it is.

We can still do useful things with this list, for example

all even countingNums

immediately returns False because even 1 is False so it can stop without inspecting the rest of the list.

(Fun-fact: all ??? infiniteList will never return True, it will either return False when it finds the first False element or it will take forever as it tries to find a False element or the (non-existent) end of the list)

The second issue is about what it means to be "classical merge-sort".

My foldMap' implementation splits the list in half.
This is close to what you would do in a traditional language, but in those languages, you would normally have either

• A pointer to the beginning of the array + a length or
• A start and stop index to that section of the array

The problem here is that [a] is a linked list in Haskell.
If I make a left and right pair of linked lists (which is what I do), I have to loop over each element in the left half of the list, to copy it to a new shorter list.
But, this means that my foldMap' merge-sort as defined here will probably take O(n^2) time because it is making copies of our linked list.

If I try using offsets into the list to avoid the copying, I'll suffer from the O(n) indexing time for random elements in a linked list, which is probably even worse.

Can I solve both of these and traverse the linked list in a way that avoids the indexing time and splitAt time cost, almost certainly yes but it would dramatically increase the complexity of my answer.

Likewise, there are ways to avoid asking for the length of the list but my answer would get much more alien in exchange for better handling long/infinite linked lists.

p.s. The simplest way to fix the second problem (but still fail the infinite list one) is to do a one-time conversion to a Data.Vector and use that for O(1) time splitAts and then convert back to a linked list at the end.

In addition to

1. Parallelism and
2. finger-trees and
3. alternative foldMaps for different performance profiles

Another way to benefit from monoids is the famous Exponentiation by Squaring algorithm.

You can use this algorithm to solve many problems in lg n time, pretty quickly.
If you define

pow :: Monoid a => a -> Int -> a
pow _ 0 = mempty
pow x n = x <> pow x (n - 1)

So pow x n is x <> ... <> x n times, then we can compute pow x n in lg n <>s by rewriting pow with the Exponentiation by squaring algorithm instead of the naive one I wrote above.

The most famous use-cases for this are fast exponentiation of modular arithmetic and matrix powers.

You can also use it to write a lg n time Fibonacci function like I wrote in this reddit comment or solve the Knight's dialer in lg n time.

Side-note:
If you don't require the ability to compute the 0th power of a value, we can relax the Monoid a restriction to a Semigroup a restriction.
That's because the only difference between Monoid and Semigroup is whether or not mempty needs to be defined and we only need to have mempty for the 0 case.