I was just looking at the Monoid
docs, when I found an instance that surprised me: Ordering
.
Here is how it’s defined:
1 2 3 4 5 6 

Without the comment I don’t know if I would have gotten it right away, but check this out:
Prelude> :m + Data.Monoid
Prelude Data.Monoid> zipWith compare "asff" "asdf"
[EQ,EQ,GT,EQ]
Prelude Data.Monoid> let compare' s = mconcat . zipWith compare s
Prelude Data.Monoid> compare' "asff" "asdf"
GT
A string comparison function can be defined using the comparisons of corresponding letters (, numbers, etc.) as Monoids.
It’s easy to see how mappend
defined above works, when you think of it
applied as a left fold on [EQ,EQ,GT,EQ]
. But here is the really cool result:
it follows from the definition of a Monoid…
mappend x (mappend y z) = mappend (mappend x y) z
that the reduction can take place in any order:
Prelude Data.Monoid> EQ `mappend` EQ `mappend` GT `mappend` EQ
GT
Prelude Data.Monoid> EQ `mappend` (EQ `mappend` GT) `mappend` EQ
GT
Prelude Data.Monoid> EQ `mappend` ((EQ `mappend` GT) `mappend` EQ)
GT
Prelude Data.Monoid> (EQ `mappend` (EQ `mappend` GT)) `mappend` EQ
GT
Prelude Data.Monoid> ((EQ `mappend` EQ) `mappend` GT) `mappend` EQ
That surprised me!
The wikipedia page for Lexicographical order has some awesome information, and nice illustrations that give a good intuition about this stuff.