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
The mention of "business logic" at the beginning of this blog entry led me to believe it would address the sort of "default" one sees in typical "business logic", e.g. a default preference such as a blank screen saver. But the clear context (in the post, once I actually read it, as well as in Monoid itself), is of a value that causes a binary operation to simply yield its other argument, a "no effect" element, which of course describes "mempty".
ReplyDeleteThe Default typeclass itself requires no such context of a binary operator, yet all the -- ahem -- default instances provided dutifully supply either numeric zero or mempty, appearing to demonstrate that really, we're again intending the "noEffect" mathematical kind of default, not default screen savers. (And why would you specify a default screen saver using a typeclass instance anyhow, LOL?) Seems to me a strong case for using Monoid instead of Default (which as I understand it, is Gabriel's point).
Maybe a nicer name for Monoid's identity element would have been "noEffect". Of course, when we get to Group, it takes on a somewhat expanded role; it's now also the result of combining an element with its inverse. What's the best name for that role -- "ash", "detritus"...? What one name covers both roles? Maybe "nothing"? Oops, taken. Maybe not. How about just "mappend"? Sigh.
One of the reason that the `Default` instances tend to provide empty values anyway, even though they are not required to, is because they have to pick something that is universally useful since the type class instance has to be canonical for that type. If you have to pick only one value then the most obvious choice is the a value which is more distinguished than the rest, which is the "empty" value.
DeleteI think "empty" would be a fine name for the empty value (if it weren't already taken by the Alternative class)
That last "mappend" should have been "mempty".
ReplyDelete