the Monoid instance for Ordering

I was just looking at the Monoid docs, when I found an instance that surprised me: Ordering.

Here is how it’s defined:

-- lexicographical ordering
instance Monoid Ordering where
        mempty         = EQ
        LT `mappend` _ = LT
        EQ `mappend` y = y
        GT `mappend` _ = GT

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.