Chapter 15: Monoid, Semigroup¶

15.1 Monoids and semigroups¶

One of the finer points of the Haskell community has been its propensity for recognizing abstract pattern in code which have well-defined, lawful representations in mathematics.

A word frequently used to describe these abstractions is algebra, by which we mean one or more operations and the set they operate over.

Over the next few chapters, we’re going to be looking at some of these.

This chapter will include:

Algebras!
Laws!
Monoids!
Semigroups!

15.2 What we talk about when we talk about algebras¶

An algebra refers to some operations and the set they operate over. These operations may have laws associated with them.

What does “operate over” mean?

https://en.wikipedia.org/wiki/Closure_(mathematics)

In mathematics, a set is closed under an opereration if performing that operation on members of the set always produces a member of that seflsame set.

For example, the positive integers are closed under addition, but not under subtraction. (1-2 is not a positive integer even though both 1 and 2 are positive integers.)

A set is closed under an operation if the operation returns a member of the set when evaluated on members of the set.

Sometimes the requirement that the operation be valued in a set is explicitly stated, in which case it is know as the axiom of closure.

For example, on may define a group as a set with a binary product operator obeying several axioms, including an axiom that the product of any two elements of the group is again a element.

In Haskell, these algebras can be implemented with typeclasses; the typeclasses define the operations. The set is the type the operations are for. Instance declarations define how each operation will perform for a given type or set.

15.3 Monoid¶

A monoid is a binary associative operation with an identity.

Binary

Takes two arguments.

Associative

An operator is considered mathematically associative if, given some expression with multiple contiguous occurrences of that operator, the order that they’re performed in won’t change the result.

Commutativity is a different concept than associativity. Commutativity is concerned with whether rearranging operands will change the result.

Associativity is where evaluating operations in a different order won’t change the result.

Commutativity is where reordering the position of operands won’t change the result.

Here is an example of an expression where the operator is associative but not commutative:
-- associative
·∾ ("Hey " ++ "you ") ++ "guys!" == "Hey " ++ ("you " ++ "guys!")
True

-- but not commutative
·∾ "Hey " ++ "you " ++ "guys!" == "guys!" ++ "you " ++ "Hey "
False
Here is an operation that is commutative but not associative:
·∾ absSub x y = abs (x - y)

·∾ a = 1
·∾ b = 2
·∾ c = 3

-- commutative
·∾ a `absSub` b  == b `absSub` a
True

-- but not associative
·∾ (a `absSub` b) `absSub` c  ==  a `absSub` (b `absSub` c)
False

Operation

A function, usually infix.

Identity

An “empty” value that when combined with any other value produces that other value.

An identity is a value with a special relationship with an operation: it turns the operation into the identity function. There are no identities without operations.

One example of this is the number $0$ for addition, since $0+x$ is always $x$, and $x+(-x) = 0$.

For multiplication, the identity value is $1$, since $1*x$ is always $x$, and $x*(x/x) = x*1$.

When mixing colors in Photoshop, clear is the identity color since mixing any color with clear results in that color, and mixing any color with the exact opposite of that color (a color with opposite RGB and opacity values) results in clear.

Monoid is the typeclass that generalizes these laws across types.

15.4 How Monoid is defined in Haskell¶

The typeclass Monoid is defined:

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

The mconcat class method has a default implementation of:

mconcat = foldr mappend mempty

The mappend class method has an infix synonym, spelled (<>), which is inherited from the Semigroup typeclass. Because of this, you don’t have to define mappend if the type already has an instance of Semigroup, it is automatically derived.

For your perusal, here is a link to the source code for Monoid in the base module. (It is also defined in Data.Monoid.)

15.6 What Integer doesn’t have a Monoid¶

Some types can be viewed as a monoid in more than one way. For example, both addition and multiplication are monoids for numbers. In these cases we often define newtypes to wrap those values and make them instances of Monoid, instead.

For numeric types, the newtypes Sum and Product are defined in Data.Monoid.

Here’s an example of their use:

·∾ import Data.Monoid

·∾ mappend 1 2
<interactive>:6:1: error:
    • Ambiguous type variable ‘a0’ arising from a use of ‘print’
      prevents the constraint ‘(Show a0)’ from being solved.
      Probable fix: use a type annotation to specify what ‘a0’ should be.
      These potential instances exist:
        instance (Show a, Show b) => Show (Either a b)
          -- Defined in ‘Data.Either’
        instance forall k (f :: k -> *) (a :: k).
                 Show (f a) =>
                 Show (Ap f a)
          -- Defined in ‘Data.Monoid’
        instance Show a => Show (First a) -- Defined in ‘Data.Monoid’
        ...plus 32 others
        ...plus 63 instances involving out-of-scope types
        (use -fprint-potential-instances to see them all)
    • In a stmt of an interactive GHCi command: print it

·∾ mappend (Sum 1) (Sum 5)
Sum {getSum = 6}

·∾ mappend (Product 5) (Product 5)
Product {getProduct = 25}

·∾ mappend (Sum 4.5) (Sum 3.4)
Sum {getSum = 7.9}

Newtype declarations are used rather than data declarations because it constrains the constructor to a single argument, signals intent, and can still be used to define unique instance declarations against (like data declarations, but unlike type aliases). Additionally, newtypes don’t have any overhead.

15.7 Why bother?¶

Having a name for this pattern of composition allows us to communicate about it, and look up existing solutions that use it. Once we know our problem is monoidal, we can refer to research papers outside of programming to find new approaches to solving our problem.

Monoids are also useful because they provide a common interface. This way we don’t have to remember a bunch of operations for combining things that are unique to each type.

Here is a more concrete example usage of monoids that is currently way beyond my comprehension: https://apfelmus.nfshost.com/articles/monoid-fingertree.html

15.8 Laws¶

Algebras are defined by their laws and are used principally for their laws. Laws make up what algebras are. Laws primarily exists to make it easier to reuse components by making how they can be combined predictable. Who wouldn’t want that?

Here are the laws for Monoid. Remember that (<>) is a synonym for mappend.

Right identity: x <> mempty = x
Left identity: mempty <> x = x
Associativity: x <> (y <> z) = (x <> y) <> z (Semigroup law)
Concatenation: mconcat = foldr (<>) mempty

15.9 Different instances, same representation¶

A few types support multiple monoidal operations, which are implemented as instances on a newtype named after the operation.

All and Any are the newtypes for Bool’s monoids:

·∾ import Data.Monoid

-- newtype All = All { getAll :: Bool }
·∾ All True <> All True
All {getAll = True}
·∾ All True <> All False
All {getAll = False}

-- newtype Any = Any {getAny :: Bool}
·∾ Any True <> Any False
Any {getAny = True}
·∾ Any False <> Any False
Any {getAny = False}

First and Last are from Data.Monoid are newtypes for Maybe values. There are replacements in Data.Semigroup for both First and Last, so their use is discouraged by the documentation.

First returns the leftmost non-nothing value:

-- newtype First a = First {getFirst :: Maybe a}
·∾  getFirst $ First (Just "hello") <> First Nothing <> First (Just "world")
Just "hello"
·∾  getFirst $ First (Just 1) <> First (Just 2)
Just 1

Last returns the rightmost non-nothing value:

·∾  getLast (Last (Just "hello") <> Last Nothing <> Last (Just "world"))
Just "world"

15.10 Reusing algebras by asking for algebras¶

We can leverage existing types with instances of Monoid to write composite types. This has the advantage of making mappend easier to write, since the wrapped component types already have well defined behaviour for how to combine them using mappend.

15.10.1 Exercise: Optional Monoid¶

Write the Monoid instance for our Maybe type renamed to Optional.

data Optional a
  = Nada
  | Only a
  deriving (Eq, Show)

instance Monoid a => Monoid (Optional a) where
  mempty = undefined
  mappend = undefined

Expected output:

Prelude> Only (Sum 1) `mappend` Only (Sum 1)
Only (Sum {getSum = 2})

Prelude> Only (Product 4) `mappend` Only (Product 2)
Only (Product {getProduct = 8})

Prelude> Only (Sum 1) `mappend` Nada
Only (Sum {getSum = 1})

Prelude> Only [1] `mappend` Nada
Only [1]

Prelude> Nada `mappend` Only (Sum 1)
Only (Sum {getSum = 1})

Ok, here is my attempt:

module Lib where
import Data.Monoid


data Optional a = Nada | Only a deriving (Eq, Show)


instance Monoid a => Monoid (Optional a) where
  mempty = Nada
  mappend = (<>)

-- (<>) must be defined for Semigroup or we'll get
-- a compiler error that GHC can't infer how (<>)
-- will behave from the definition of mappend in
-- the Monoid instance.
instance Monoid a => Semigroup (Optional a) where
  (<>)   Nada     Nada    =   Nada
  (<>)   Nada   (Only b)  =  (Only b)
  (<>) (Only a)   Nada    =  (Only a)
  (<>) (Only a) (Only b)  =  (Only (a `mappend` b))

Browse to the project directory and run stack test to verify it works.

15.10.4 The problem of orphan instances¶

An orphan instance is when an instance is defined for a datatype and typeclass, but not in the same module as either the typeclass or datatype declaration.

This can lead to situations where there are multiple conflicting instances for the typeclass/type pair. Even if you haven’t imported conflicting instances, if they exist at all it is no longer safe to assume you know what class methods will do anymore.

Avoid this; It’s bad juju, and GHC will warn you when it happens. If you don’t own the typeclass or the datatype, and you need an instance, create it against a newtype of the type, instead.

There are a few solutions for addressing orphan instances:

You defined the type but not the typeclass? Put the instance in the same module as the type so that the type cannot be imported without its instances.
You defined the typeclass but not the type? Put the instance in the same module as the typeclass definition so that the typeclass cannot be imported without its instances.
Neither the type nor the typeclass are yours? Define your own newtype wrapping the original type and now you’ve got a type that “belongs” to you for which you can rightly define typeclass instances. There are means of making this less annoying which we’ll discuss later.

15.11 Madness¶

Using a lightly edited example from the Wikipedia article on Mad Libs:

“exclamation! he said adverb as he
jumped into his car noun and drove
off with his adjective wife”

We can make this into a function, like the following:

module Madness where
import Data.Monoid


type Verb        = String
type Adjective   = String
type Adverb      = String
type Noun        = String
type Exclamation = String


madlibbin' :: Exclamation -> Adverb -> Noun -> Adjective -> String
madlibbin' e adv noun adj =
  e    <> "! he said " <>
  adv  <> " as he jumped into his car " <>
  noun <> " and drove off with his " <>
  adj  <> " wife."


-- Now refactor the madlibbin' function using mconcat.
madlibbinBetter' :: Exclamation -> Adverb -> Noun -> Adjective -> String
madlibbinBetter' e adv noun adj =
  mconcat [ e, "! he said "
          , adv, " as he jumped into his car "
          , noun, " and drove off with his "
          , adj, " wife." ]

15.12 Better living through QuickCheck¶

import Data.Monoid
import Test.QuickCheck

monoidAssoc :: (Eq m, Monoid m) => m -> m -> m -> Bool
monoidAssoc a b c =
  a <> (b <> c) == (a <> b) <> c

main = quickCheck
  (monoidAssoc :: String -> String -> String -> Bool)

15.13 Semigroup¶

A semigroup is a binary associative operation. Unlike monoid, it does not require an identity value.

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

…and we’re left with one law, associativity:

(a <> b) <> c == a <> (b <> c)

Although it’s not mentioned in the book, there are a few more class methods:

·∾ :info Semigroup
type Semigroup :: * -> Constraint

class Semigroup a where
  (<>)    :: a -> a -> a
  sconcat :: NonEmpty a -> a
  stimes  :: Integral b => b -> a -> a
  {-# MINIMAL (<>) #-}

·∾ :doc sconcat
Reduce a non-empty list with '<>' The default
definition should be sufficient, but this can be
overridden for efficiency.

>>> import Data.List.NonEmpty
>>> sconcat $ "Hello" :| [" ", "Haskell", "!"]
"Hello Haskell!"

·∾ :doc stimes
Repeat a value @n@ times.

Given that this works on a 'Semigroup' it is allowed
to fail if you request 0 or fewer repetitions, and
the default definition will do so.

By making this a member of the class, idempotent
semigroups and monoids can upgrade this to execute
in \(\mathcal{O}(1)\) by picking @stimes =
'Data.Semigroup.stimesIdempotent'@ or @stimes =
'stimesIdempotentMonoid'@ respectively.

>>> stimes 4 [1]
[1,1,1,1]

15.13.2 NonEmpty, a useful datatype¶

One useful datatype that can’t have a Monoid instance but does have a Semigroup instance is the NonEmpty list type. It is a list datatype that can never be an empty list.

data NonEmpty a  =  a :| [a]

There is no empty list to serve as an identity for any operation over a NonEmpty list, yet there is still a binary associative operation: two NonEmpty lists can still be concatenated.

·∾ (1 :| [2,3]) <> (4 :| [5,6])
1 :| [2,3,4,5,6]
·∾ :info (<>)
class Semigroup a where
  (<>) :: a -> a -> a
  ...
        -- Defined in ‘GHC.Base’
infixr 6 <>
·∾ :info (:|)
data NonEmpty a = a :| [a]      -- Defined in ‘GHC.Base’
infixr 5 :|

You can read more about it here, on hoogle.

15.14 Strength can be weakness¶

The strength of an algebra usually refers to the number of operations it provides. Making an algebra stronger may in turn require enforcing more laws, which means that fewer types can have legal instances of it. Generally, it is better to have multiple smaller algebras than one larger one. Some types defy uniform generalization, but have efficient machine-level representations.

15.15 Chapter exercises¶

15.15.1 Semigroup exercises¶

Given a datatype, implement the Semigroup instance. Add Semigroup constraints to type variables where needed. Use the Semigroup class from the semigroups library (or from base if you are on GHC 8) or write your own. When we use (<>), we mean the infix mappend from the Semigroup typeclass.

Note We’re not always going to derive every instance you may want or need in the datatypes we provide for exercises. We expect you to know what you need and to take care of it yourself by this point.

Validate all of your instances with QuickCheck. Since Semigroup’s only law is associativity, that’s the only property you need to reuse. Keep in mind that you’ll potentially need to import the modules for Monoid and Semigroup and to avoid naming conflicts for the (<>) depending on your version of GHC.

data Trivial = Trivial deriving (Eq, Show)

instance Semigroup Trivial where
  _ <> _ = undefined

instance Arbitrary Trivial where
  arbitrary = return Trivial

semigroupAssoc :: (Eq m, Semigroup m)
               => m -> m -> m -> Bool
semigroupAssoc a b c =
  a <> (b <> c) == (a <> b) <> c

type TrivAssoc = Trivial -> Trivial -> Trivial -> Bool

main :: IO ()
main = quickCheck (semigroupAssoc :: TrivAssoc)

Ok, I’ve restructured things a bit, but here is an implementation of arbitrary for Trivial, as well as instance of Monoid for Trivial.

data Trivial = Trivial deriving (Eq, Show)

instance Semigroup Trivial where
  _ <> _ = Trivial

instance Monoid Trivial where
  mempty = Trivial
  mappend = (<>)

instance Arbitrary Trivial where
  arbitrary = return Trivial :: Gen Trivial

Here are the tests, moved to a separate module:

  describe "Trivial" $ do
    context "Semigroup laws" $ do
      prop "(<>) is associative"
        ((\a b c -> a <> (b <> c) == (a <> b) <> c)
         :: Trivial
         -> Trivial
         -> Trivial
         -> Bool)
      it "mempty exists for Trivial, and is Trivial" $ do
        (mempty :: Trivial) `shouldBe` Trivial

newtype Identity a = Identity a

Ok, here is an instance:

newtype Identity a = Identity a deriving (Eq, Show)

instance Semigroup a => Semigroup (Identity a) where
  (<>) (Identity x) (Identity y) = Identity (x <> y)

instance Arbitrary a => Arbitrary (Identity a) where
  --
  -- arbitrary :: Arbitrary a => Gen (Identity a)
  --
  -- arbitrary        = return $ Identity arbitrary
  -- Gen (Identity a) = Gen    ( Identity    ?     )
  -- .....................................   a
  -- ..................................... Gen a
  arbitrary = do
    x <- arbitrary
    return (Identity x)

and here is the test:

  describe "Identity" $ do
    context "Semigroup laws" $ do
      prop "(<>) is associative"
        ((\a b c -> a <> (b <> c) == (a <> b) <> c)
         :: Identity (Sum Int)
         -> Identity (Sum Int)
         -> Identity (Sum Int)
         -> Bool)

data Two a b = Two a b

Hint Ask for another Semigroup instance.

  describe "Two a b" $ do
    context "Semigroup laws" $ do
      prop "(<>) is associative for Two"
        ((\a b c -> a <> (b <> c) == (a <> b) <> c)
         :: Two (Sum Int) (Sum Int)
         -> Two (Sum Int) (Sum Int)
         -> Two (Sum Int) (Sum Int)
         -> Bool)

data Three a b c = Three a b c

  describe "Three a b c" $ do
    context "Semigroup laws" $ do
      prop "(<>) is associative for Three"
        ((\a b c -> a <> (b <> c) == (a <> b) <> c)
         :: Three (Sum Int) (Sum Int) (Sum Int)
         -> Three (Sum Int) (Sum Int) (Sum Int)
         -> Three (Sum Int) (Sum Int) (Sum Int)
         -> Bool)

newtype BoolConj = BoolConj Bool

What it should do:

·∾ (BoolConj True) <> (BoolConj True)
BoolConj True

·∾ (BoolConj True) <> (BoolConj False)
BoolConj False

newtype BoolDisj = BoolDisj Bool