Semigroup and Monoid

Semigroup and the operator <>

A Semigroup is a type whose values can be combined by a binary operator. The operator is <>, and the class has exactly one method:

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

String combines by concatenation, [a] by appending, a numeric wrapper by addition, and Maybe a by keeping the first Just. The point is that the operation is named by the type, not by the call site, so one function written with <> works on all of them.

Monoid and mempty

A Monoid is a Semigroup with a neutral element:

class Semigroup a => Monoid a where mempty :: a

"" is the neutral element of string concatenation, [] of appending, and Sum 0 of addition. Neutral means x <> mempty == x and mempty <> x == x, and the operator must also be associative; the lesson on the monad laws shows a broken instance and what it breaks. mconcat folds a list with <> and mempty, which is the line that makes an empty list work.

module Main (main) where import Data.Monoid (All (..), Any (..), Product (..), Sum (..)) main :: IO () main = do print ("abc" <> "def" :: String) print ([1, 2] <> [3, 4] :: [Int]) print (mempty :: String) print (mconcat ["a", "b", "c"] :: String) print (getSum (Sum 3 <> Sum 4 :: Sum Int)) print (getProduct (Product 3 <> Product 4 :: Product Int)) print (getAny (Any False <> Any True)) print (getAll (All True <> All False)) print (mempty :: [Int])

ghc -Wall -O1 -o monoid monoid.hs
./monoid

"abcdef"
[1,2,3,4]
""
"abc"
7
12
True
False
[]

The string type annotation is not decoration: the literals and the operator alone do not say which Monoid is meant, and the numeric wrappers exist for exactly that reason. A bare Int has no Semigroup instance, because the compiler cannot guess whether you mean addition or multiplication; Sum and Product are two newtypes that answer the question.

Sum, Product, Any and All

The numeric and boolean wrappers are the ones you reach for in a fold. They are newtypes with a single field, so getSum and friends cost nothing at run time, and they let foldMap do the job of a hand-written accumulator:

All of them are in Data.Monoid and re-exported by Data.Semigroup. The field accessors getSum, getAny and the rest unwrap the newtype so that print shows a number and not Sum {getSum = 7}.

A report of your own

A real use is a report that collects lines and counts problems. The two instances are four lines, and after them mconcat builds the whole report from pieces:

module Main (main) where data Report = Report { reportLines :: [String] , reportErrors :: Int } instance Semigroup Report where left <> right = Report (reportLines left <> reportLines right) (reportErrors left + reportErrors right) instance Monoid Report where mempty = Report [] 0 line :: String -> Report line text = Report [text] 0 problem :: String -> Report problem text = Report ["ERROR: " ++ text] 1 main :: IO () main = do let report = mconcat [line "start", problem "missing file", line "done"] mapM_ putStrLn (reportLines report) print (reportErrors report) print (reportLines (mempty :: Report))

ghc -Wall -O1 -o report report.hs
./report

start
ERROR: missing file
done
1
[]

The order of the lines follows the order of the pieces in the list, because mconcat folds from the right with <> and this instance appends. The count adds up on its own, and a caller that has no pieces gets mempty, which prints an empty list and zero errors: the same program handles the empty report with no special case.

FoldMap and the identity

The previous lesson used foldMap show and did not ask what makes it work. The answer is this class:

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

Every element is turned into a monoid value and the values are combined with <>, starting from mempty. The program below counts the occurrences of one word in a sentence with a newtype of its own, and the empty list shows the identity:

module Main (main) where newtype Count = Count Int deriving (Show) instance Semigroup Count where Count a <> Count b = Count (a + b) instance Monoid Count where mempty = Count 0 countWord :: String -> Count countWord "the" = Count 1 countWord _ = Count 0 main :: IO () main = do print (foldMap countWord (words "the cat and the hat")) print (mconcat (map Count [1, 2, 3 :: Int])) print (foldMap countWord ([] :: [String]))

ghc -Wall -O1 -o count count.hs
./count

Count 2
Count 6
Count 0

The last line is the reason mempty must exist: a fold over an empty list still has to answer, and it answers with the identity. The Semigroup instance alone would leave foldMap with no starting value, which is why the class hierarchy puts Semigroup above Monoid and not the other way round.

Exercises

  1. Write average :: [Double] -> Double with a Monoid that holds a sum and a count.
  2. Count the vowels of a string with foldMap and a Count newtype.
  3. Explain why foldMap (const (Any True)) answers whether a list is non-empty.
  4. Write a Semigroup instance for a pair of two monoids and check that mempty is the pair of both identities.
  5. Use Sum and Product to compute the sum and the product of the same list in one pass.
  6. Change the report so that a warning adds a line and no error, and run the program again.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What is the method of the Semigroup class?

    Answer

    (<>) :: a -> a -> a

    Semigroup has exactly one method and it combines two values of the same type.

  2. What is mempty for String?

    Answer

    ""

    The empty string is neutral for concatenation.

  3. Why does Int have no Semigroup instance?

    Answer

    The compiler cannot know whether you mean addition or multiplication, so Sum and Product exist

    Two reasonable operations would conflict, so the newtypes name the choice.

  4. What does this program print? module Main (main) where import Data.Monoid (Sum (..)) main :: IO () main = print (getSum (mconcat [Sum 1, Sum 2, Sum 3 :: Sum Int]))

    Answer

    6

    mconcat combines the three Sum values with the addition of the instance and getSum unwraps the result.

  5. What does mconcat [] return for a list of strings?

    Answer

    ""

    A fold over an empty list starts from mempty, which is the empty string here.

  6. Which type combines booleans with a logical and?

    Answer

    All

    All is the newtype whose semigroup is &&, while Any is ||.

  7. What does foldMap need from the result type?

    Answer

    A Monoid instance

    The signature is (Foldable t, Monoid m) => (a -> m) -> t a -> m, so the combining operation comes from the Monoid.

  8. What does this program print? module Main (main) where main :: IO () main = print (mempty :: [Int])

    Answer

    []

    The neutral element of list append is the empty list.

  9. What law must a Monoid instance satisfy with mempty?

    Answer

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

    mempty is the identity of the operation on both sides, and the compiler does not check it.

  10. What does the Report instance give a caller that has no pieces?

    Answer

    mempty, an empty list and zero errors

    mempty is the empty report, so the same code path handles it.

The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev