Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the name of this monoid law?

Tags:

haskell

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?

like image 783
GreenSaguaro Avatar asked Sep 10 '16 09:09

GreenSaguaro


People also ask

Why is it called a monoid?

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.

What is a monoid explain?

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.

Which is an example for monoid?

(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.

What are monoids in Haskell?

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).


2 Answers

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.

like image 193
pigworker Avatar answered Oct 22 '22 19:10

pigworker


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.)

like image 32
chepner Avatar answered Oct 22 '22 19:10

chepner