Monoid

A monoid is an algebraic structure comprising a product of three things

  • a set;
  • a closed binary operation; and
  • an element of the set that is neutral with respect to that binary operation.

The binary operation must be associative.

In other words, a monoid is a semigroup with one additional requirement: the identity value.

Many sets form monoids under more than one operation. Integers, for example, form monoids under both sum and product operations, with 0 being the neutral element for addition and 1 being the identity for multiplication.

The Monoid class

In Haskell, monoids are represented by the Monoid class. Monoid is superclassed by SemigroupSince base-4.11.0.0., which means there is a Semigroup constraint on the Monoid class in the class definition. This means that in order to have a Monoid instance, a type must also have a Semigroup instance.Data.Monoid.

class Semigroup a => Monoid a where
  mempty :: a
  mappend :: a -> a -> a
  mconcat :: [a] -> a
  {-# MINIMAL mempty #-}

The mappend function was formerly part of the minimal complete definition of Monoid, and <> was its infix version; however, since all Monoids must also be Semigroups, the presence of mappend in Monoid is superfluous.The default implementation of mappend is mappend = (<>) since base version 4.11.0.0. The binary operation for a monoid is its implementation of <> from the Semigroup class. You may still use mappend if you prefer prefix functions in some cases, and for historical reasons, you’ll still see it in a lot of Haskell code.

Now the only thing that must be implemented for an instance of Monoid is mempty. As you can see, it’s not a function, In some senses, it is a function. Since a typeclass can also be conceived as a record of functions that is passed around implicitly, the Monoid a => constraint on mempty can be read as a function: it needs to be applied to a type in order to return the value. but nevertheless it’s very important: it defines the identity or neutral element with regard to the set and the particular operation. Thus, for numbers that form a monoid under addition, denoted with the Sum newtype, mempty would be Sum 0; for the Product newtype, it would be Product 1.

λ> Sum 2 <> Sum 0
Sum {getSum = 2}

λ> Sum 2 <> mempty
Sum {getSum = 2}

λ> Product 1 <> Product 5
Product {getProduct = 5}

λ> mempty <> Product 5
Product {getProduct = 5}

λ> Product 0 <> Product 5
Product {getProduct = 0}

mempty is return-type polymorphic and is useful in writing polymorphic functions where an identity value of some kind will be needed but the type cannot yet be known. For example, we see this commonly used in the pure implementation for Applicative instances on certain species of types, such as tuples:

instance Monoid a => Applicative ((,) a) where

    pure x =
        (mempty, x)

    (x, func) <*> (y, z) =
        (x <> y, func z)

    liftA2 func (x, z) (y, z') =
        (x <> y, func z z')

It’s worth noting that Monoid should obey right and left identity laws. It shouldn’t too be surprising given what we expect of an identity value; if it’s neutral with respect to the operation, it should be neutral regardless of whether it’s the first argument or the second.

mempty <> x = x
-- and --
x <> mempty = x

For example, it would be a truly unwanted surprise if multiplying by 1 gave you a different result depending on which position the 1 was in.

λ> mempty <> Product 5
Product {getProduct = 5}

λ> Product 5 <> mempty
Product {getProduct = 5}

This is particularly trivial, though, since multiplication is known to be commutative. Not all monoids are commutative! For example, list concatenation is associative but not commutative: changing the order of arguments in list concatenation gives different results.

λ> "Julie" <> "Moronuki"
"JulieMoronuki"

λ> "Moronuki" <> "Julie"
"MoronukiJulie"

However, it is still the case that its mempty behaves itself as both the right and left identity.

λ> "Julie" <> mempty
"Julie"

λ> mempty <> "Julie"
"Julie"

mconcat

In terms of Haskell history, Monoid precedes Semigroup, so mconcat is in the Prelude while sconcat is not. They are essentially the same function, however, but with mconcat requiring a standard list input instead of a NonEmpty.

mconcat :: Monoid a => [a] -> a

The single input of mconcat is a list; the type of the values in the list must be a monoid. The monoidal operation (the mappend, also known as (<>) from Semigroup) is used to reduce them to a single value.

If the argument is a list of list monoids, you get the original concat.The @ in this example is a type application, and the underscore is a type wildcard.

λ> :type mconcat @[_]
mconcat @[_] :: [[w]] -> [w]

λ> :type concat @[]
concat @[] :: [[a]] -> [a]

λ> mconcat ["julie", "moronuki"]
"juliemoronuki"

λ> mconcat [[1, 2], [4, 5]]
[1,2,4,5]

λ> concat [[1, 2], [4, 5]]
[1,2,4,5]

If your monoid is one of the arithmetic monoids, then mconcat is similar to the sum and product functions – both of which are in Prelude – although they accept any Foldable containers as inputs, not only lists.

λ> :type sum
sum :: (Foldable t, Num a) => t a -> a

λ> :type product
product :: (Foldable t, Num a) => t a -> a

λ> sum [3, 4, 5]
12

λ> product [3, 4, 5]
60

λ> mconcat [Sum 3, Sum 4, Sum 5]
Sum {getSum = 12}

λ> mconcat [Product 3, Product 4, Product 5]
Product {getProduct = 60}

Some monoidsPlease note that the First and Last types in Data.Monoid are different from those in Data.Semigroup. See the section below on the monoid newtypes for more information. “choose” an element to return (instead of “combining” them), such as the Boolean monoids Any and All or the Maybe monoids First and Last, and so will always return one of the elements that is actually in the list.

λ> mconcat [Any True, Any False, Any False]
Any {getAny = True}

λ> mconcat [All True, All False, All False]
All {getAll = False}

λ> mconcat [First (Just 3), First Nothing, First (Just 5)]
First {getFirst = Just 3}

λ> mconcat [Last (Just 3), Last Nothing, Last (Just 5)]
Last {getLast = Just 5}

Reducing a collection of values to a single value, often called reduce in other languages, is typically referred to as folding in Haskell. And, indeed, mconcat is further generalized by a function called fold from the Data.Foldable module.fold documentation in Data.Foldable.

λ> :type fold
fold :: (Foldable t, Monoid m) => t m -> m

λ> mconcat [Just "julie", Nothing, Just "moronuki"]
Just "juliemoronuki"

λ> fold [Just "julie", Nothing, Just "moronuki"]
Just "juliemoronuki"

λ> mconcat [First (Just 3), First Nothing, First (Just 5)]
First {getFirst = Just 3}

λ> fold [First (Just 3), First Nothing, First (Just 5)]
First {getFirst = Just 3}

λ> mconcat [Product 3, Product 4, Product 5]
Product {getProduct = 60}

λ> fold [Product 3, Product 4, Product 5]
Product {getProduct = 60}

There is a deep connection between monoids and folding functions. We’ve written about it from one perspective in the past, and we will no doubt write about it again.

Monoids and their identities

Since Semigroup now superclasses Monoid, all of the Monoid newtypes are also Semigroups, so in some sense, the only thing to know about their Monoid instances is what the mempty is. The newtypes will be covered in more detail below, but essentially mempty values come in two flavors: 1 and 0.

Sign up for access to the full page, plus the complete archive and all the latest content.