In the documentation for Data.Monoid
, it states the following laws should be satisfied:
mappend mempty x = x
mappend x mempty = x
mappend x (mappend y z) = mappend (mappend x y) z
mconcat = foldr mappend mempty
My understanding of these is that the first 2 are identity, and the third is associativity.
But what is the law in the fourth line? Identity again, but for mconcat
?
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
A monoid is a set that is closed under an associative binary operation and has an identity element such that for all , . Note that unlike a group, its elements need not have inverses. It can also be thought of as a semigroup with an identity element. A monoid must contain at least one element.
(1) N = {0,1,2,...} is a monoid with respect to addition. Simi- larly, N+ = N − {0} and N are both monoids with respect to multiplication. (2) For any set S, EndS, the set of all maps from S to itself, called endomorphisms, is a monoid with respect to composition.
In Haskell, the Monoid typeclass (not to be confused with Monad) is a class for types which have a single most natural operation for combining values, together with a value which doesn't do anything when you combine it with others (this is called the identity element).
Mathematically, the definition of a monoid requires the existence of something like mempty
and something like mappend
, satisfying the first three laws: left and right identity, and associativity.
The mconcat
method has been added to the class to reflect the fact that accumulation in a list is often what one does with monoids. The fourth law is the executable specification of mconcat
: indeed, that very law is the line of code which gives the default implementation of mconcat
. Making mconcat
a member of the class means that, per Monoid
instance, you are free to give mconcat
a more efficient implementation, just as long as it agrees with the default.
It's not clear to me that making mconcat
reimplementable in this way is a particularly big win. I'd tend to avoid mconcat
in favour of (the confusingly named) fold
.
The purpose of mconcat
is not to provide any more information about the monoid; it is an implementation detail. It is a convenience function, but one that might be implemented more efficiently than its default definition. When infinite lists are considered, "more efficient" can mean "possible".
Consider the Product
monoid. The following never terminates, using the default definition of mconcat
:
mconcat (map Product [0..])
even though it should be obvious that any list of integers containing 0 should produce 0. However, if you were to redefine the function as
mconcat = foldr (\acc v -> if acc == Product 0 then Product 0 else mappend acc v) empty
Then the product of an infinite list containing at least one zero would still terminate. (Of course, an infinite list of of non-zero values would still never terminate, but this mconcat
is still more efficient for large lists that contain an "early" zero.)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With