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:
- Sum adds, Product multiplies.
- Any is a logical or, All is a logical and.
- First and Last keep the first or the last Just of a fold.
- Ordering is a monoid too, which is why maximum and sort can be written with it.
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
- Write average :: [Double] -> Double with a Monoid that holds a sum and a count.
- Count the vowels of a string with foldMap and a Count newtype.
- Explain why foldMap (const (Any True)) answers whether a list is non-empty.
- Write a Semigroup instance for a pair of two monoids and check that mempty is the pair of both identities.
- Use Sum and Product to compute the sum and the product of the same list in one pass.
- 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.
-
What is the method of the
Semigroupclass?Answer
(<>) :: a -> a -> aSemigroup has exactly one method and it combines two values of the same type.
-
What is
memptyforString?Answer
""The empty string is neutral for concatenation.
-
Why does
Inthave noSemigroupinstance?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.
-
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.
-
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.
-
Which type combines booleans with a logical and?
Answer
AllAll is the newtype whose semigroup is &&, while Any is ||.
-
What does
foldMapneed from the result type?Answer
A
MonoidinstanceThe signature is
(Foldable t, Monoid m) => (a -> m) -> t a -> m, so the combining operation comes from the Monoid. -
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.
-
What law must a Monoid instance satisfy with mempty?
Answer
x <> mempty == xandmempty <> x == xmempty is the identity of the operation on both sides, and the compiler does not check it.
-
What does the
Reportinstance give a caller that has no pieces?Answer
mempty, an empty list and zero errorsmempty 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