Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 57 ยท Functors, applicatives and monads

Semigroups and Monoids

Learn Haskell's Semigroup and Monoid classes: combining values with <>, identity elements, Sum, Product, Any, All, mconcat and foldMap, with examples.

Adding numbers, joining strings and merging lists look like unrelated jobs. Yet they share a shape: you take two values of the same type and produce a third, and the grouping does not matter. (1 + 2) + 3 equals 1 + (2 + 3); ("a" ++ "b") ++ "c" equals "a" ++ ("b" ++ "c").

Haskell captures this with two small classes, Semigroup and Monoid. They are not as famous as monads, but you will use them constantly: they are how Haskell folds, aggregates and merges things in a uniform way.

Real Haskell is not installed here, so the Haskell blocks are read-only. The runnable examples are JavaScript stand-ins and say so.

Semigroup: combine two values

HASKELL
class Semigroup a where
  (<>) :: a -> a -> a

The operator <> must be associative: (x <> y) <> z == x <> (y <> z). That is the only law.

Lists and strings are semigroups where <> is ++:

HASKELL
[1, 2] <> [3]             -- [1,2,3]
"Hello, " <> "world"      -- "Hello, world"

Numbers are not directly semigroups, because there is more than one sensible way to combine them: add or multiply? Haskell does not choose. Instead, the Data.Monoid module gives wrapper types that pick one:

HASKELL
import Data.Monoid

Sum 3 <> Sum 4             -- Sum {getSum = 7}
Product 3 <> Product 4     -- Product {getProduct = 12}

Maybe a is a semigroup whenever a is: Just [1] <> Just [2] is Just [1,2], and Nothing is skipped.

One operator, many meanings

Sum Combine by adding.
Product Combine by multiplying.
String Combine by joining.
All / Any Combine with && or ||.

The type tells <> what to do.

1 / 2

Monoid: add an identity

A monoid is a semigroup with a neutral element called mempty:

HASKELL
class Semigroup a => Monoid a where
  mempty  :: a
  mconcat :: [a] -> a      -- has a default definition

The extra laws say that mempty does nothing on either side:

HASKELL
mempty <> x == x
x <> mempty == x

Identities for the common instances:

Type <> mempty
[a] and String ++ []
Sum Int + Sum 0
Product Int * Product 1
Any || Any False
All && All True

mconcat collapses a whole list with <>, starting from mempty, which is why the empty list is a safe input:

HASKELL
mconcat ["ab", "cd", "ef"]       -- "abcdef"
getSum (mconcat (map Sum [1 .. 10]))   -- 55
getAll (foldMap (All . even) [2, 4, 6])  -- True

The mempty matters: without it you could not say what an empty fold returns. sum [] is 0 because 0 is the identity of addition.

A stand-in monoid

A monoid in JavaScript is just a pair: a binary operation and an identity. Real Haskell picks the instance from the type and checks the class; here we pass the monoid explicitly. The Sum, Product, Any and All wrappers become four such objects.

JS Monoids as objects

Press Run (or Ctrl + Enter) to see the console output here.

No output.

foldMap: map, then combine

Very often you want to convert each element into a monoid value and then combine. That is foldMap:

HASKELL
foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m

getSum     (foldMap Sum [1, 2, 3])               -- 6
getAny     (foldMap (Any . (> 3)) [1, 5, 2])     -- True
foldMap show [1, 2, 3]                           -- "123"
length'    = getSum . foldMap (const (Sum 1))

You choose the "how to combine" by choosing the wrapper, not by changing the algorithm. The same traversal gives a sum with Sum, a product with Product, a yes/no question with Any or All. foldMap is available for any Foldable container, which the next lesson covers.

Other useful wrappers

  • First and Last (from Data.Monoid) keep the first or last Just they see.
  • Min and Max (from Data.Semigroup) combine by min and max. They are semigroups, not monoids, for types without a smallest or largest value, because there is no sensible mempty.
  • Ordering is a monoid: it picks the first result that is not EQ. That makes multi-key sorting concise:
HASKELL
import Data.List (sortBy)
import Data.Ord (comparing)

people = [("Ada", 36), ("Bob", 25), ("Cy", 36)]

sortBy (comparing snd <> comparing fst) people
-- [("Bob",25),("Ada",36),("Cy",36)]

Here <> on functions works too: a function a -> b is a semigroup when b is, so comparing snd <> comparing fst compares by the second field and breaks ties with the first.

JS Ordering as a monoid

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Writing your own instance

Give a type an instance when it has one natural way to combine. Here is a summary of statistics that merges two summaries:

HASKELL
data Stats = Stats { count :: Int, total :: Int } deriving Show

instance Semigroup Stats where
  Stats c1 t1 <> Stats c2 t2 = Stats (c1 + c2) (t1 + t2)

instance Monoid Stats where
  mempty = Stats 0 0

summarise :: [Int] -> Stats
summarise = foldMap (\x -> Stats 1 x)

-- summarise [4, 6, 10]  ==  Stats {count = 3, total = 20}

Because the combine is associative, the list could be split in chunks, summarised in parallel and merged later with <>. That property is a quiet reason monoids matter so much in big-data code.

Do not declare an instance whose <> is not associative. The compiler cannot detect it, but code like foldMap and mconcat is free to regroup and will give inconsistent answers. For example, subtraction is not associative, so there is no Semigroup for "subtract".

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which single law does Semigroup require?

    Only associativity is required. The identity element is what upgrades a semigroup to a monoid.
  2. 2. What is mempty for All?

    All combines with &&, whose identity is True: True && x is x.
  3. 3. What does getSum (foldMap Sum []) return?

    An empty fold gives mempty, and mempty for Sum is Sum 0.
  4. 4. Why does Haskell use wrappers like Sum and Product?

    A type can have only one instance per class, so wrappers let you select addition or multiplication.

Summary

  • Semigroup gives an associative <>; Monoid adds the identity mempty.
  • Lists and strings combine with ++; wrappers Sum, Product, Any, All, First, Last select the way numbers and booleans combine.
  • mconcat combines a list; foldMap f maps each element to a monoid and combines.
  • Ordering and functions are monoids, so comparing a <> comparing b sorts by several keys.
  • Always keep <> associative when writing instances.

Next: Foldable and Traversable.