Patterns
Let's begin by trying to identify a common pattern unifying all default values. If I were to name a few types, most people would agree on the following default values:
- Int: 0
- Bool: False
- [a]: [], the empty list
- Text: "", the empty Text string (if you use OverloadedStrings)
Well, we can discern a common pattern: all these default values seem to correspond to something "empty". But what does it really mean to be "empty"?
Well, for numbers it is obvious why we consider 0 empty. If you add 0 to any number n, you get back n, signifying that 0 must be empty:
0 + n = n n + 0 = nWe can extend this same reasoning to the other values to justify why we consider them empty. For example, if you append "" to any Text string str, you get back str, signifying that "" added nothing:
"" `append` str = str str `append` "" = strSimilarly, the empty list adds nothing when you concatenate it:
[] ++ xs = xs xs ++ [] = xs... and False does nothing when you (||) it:
False || b = b b || False = bThe pattern is obvious: in every case we have some empty default value, which we will call mempty, and some combining function, which we will call mappend, that satisfy the following two equations:
mempty `mappend` x = x x `mappend` mempty = xThis is a Monoid, and Haskell's Data.Monoid module defines mempty and mappend in the Monoid type class:
class Monoid m where mempty :: m mappend :: m -> m -> m... and also provides a convenient infix operator for mappend:
(<>) :: (Monoid a) => a -> a -> a m1 <> m2 = m1 `mappend` m2
Emptiness
Not all types have a unique Monoid instance. For example, Bool has two separate Monoid instances and we must use the Any or All newtypes from Data.Monoid to distinguish which one we prefer.
The Any monoid corresponds to the one we chose above, where False is the empty value and (||) is the combining operation:
newtype Any = Any { getAny :: Bool } instance Monoid Any where mempty = Any False (Any b1) `mappend` (Any b2) = Any (b1 || b2)However, there is a dual monoid where True is the "empty" value and (&&) is the combining operation:
newtype All = All { getAll :: Bool } instance Monoid All where mempty = All True (All b1) `mappend` (All b2) = All (b1 && b2)Similarly, numbers have two separate Monoid instances, and we use the Sum or Product monoids to distinguish which one we prefer.
newtype Sum a = Sum { getSum :: a } instance (Num a) => Monoid (Sum a) where mempty = Sum 0 (Sum n1) `mappend` (Sum n2) = Sum (n1 + n2) newtype Product a = Product { getProduct :: a } instance (Num a) => Monoid (Sum a) where mempty = Product 1 (Product n1) `mappend` (Product n2) = Product (n1 * n2)Monoids teach a valuable lesson: there is no such thing as an intrinsically empty value. Values are only empty with respect to a specific combining operation. We can choose more exotic default values to be mempty, but if we must select an unusual mappend to justify their emptiness then that suggests that we chose the wrong defaults.
So the next time you find yourself needing a Default type class, chances are that you actually should use the Monoid type class instead. The Monoid class forces us to demonstrate why our default is truly empty by also providing the associated combining operator. This basic sanity check discourages us from defining "ridiculous" defaults.
Monoids everywhere :)
ReplyDeleteYeah. :)
DeleteSurprisingly useful for such a simple concept, especially once you start generalizing it to Alternatives and Categories.
FYI readers: there's actually a Default type class [1] which uses mempty for most of the stuff.
ReplyDelete[1] http://hackage.haskell.org/packages/archive/data-default/0.5.3/doc/html/Data-Default.html