loading...

Basics of Monoids in Haskell

aibhstin profile image Aibhstin ・4 min read

In a previous post I discussed the basics of the Semigroup typeclass in Haskell, being an abstraction of a common algebraic structure. In this post I will discuss the basics of the monoid data structure, as implemented in Haskell via the typeclass Monoid.

The connection between Semigroup and Monoid

Semigroup and Monoid are very closely connected concepts. Both represent algebraic structures consisting of a set of elements and a binary, associative operation. Monoids extend this algebraic structure with the addition of an identity element. Let's represent this algebraic structure like so:

(S, *, 0)

Here, S is the set of elements, * is the associative, binary operation and 0 is the identity element. I'm using * and 0 to represent the binary operation and the identity element in general, as opposed to multiplication and zero, following a convention from the book An Introduction to Category Theory by Harold Simmons (Which I strongly recommend). The laws that a monoid must obey are:

-- Identity
a1 * 0 = a1
0 * a1 = a1

-- Associativity
(a1 * a2) * a3 = a1 * (a2 * a3)

Given that a monoid is just a semigroup with an identitive element, any valid semigroup can be a monoid so long as such an identitive element is defined for it. Indeed, if we look at how Haskell defines the Monoid typeclass:

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

The {-# MINIMAL mempty #-} tells us that all we need to define a valid instance of the typeclass Monoid for a type a is to define mempty. This is because, given that a is a valid instance of Semigroup, it already has the necessary binary-associative operation.

To get the mempty of a certain type, you need to explicitly give mempty a type, like so:

GHCi> mempty :: String
""
GHCi> mempty :: Maybe String
Nothing

Data.Monoid

Haskell comes with the 'Data.Monoid' package. This is loaded with a bunch of useful extras to enhance your usage of Monoids in Haskell.

For example, in my post on Semigroups, I implemented the Sum and Product types to wrap around numerical types to implement specific semigroups. These types were not an original creation by me (I used them to explain a specific concept), and are actually pulled from Data.Monoid!

GHCi> import Data.Monoid
GHCi> Sum 5 <> Sum 4
Sum {getSum = 9}
GHCi> mappend (Sum 3) (Sum 10)
Sum {getSum = 13}
GHCi> mconcat [(Product 2), (Product 4), (Product 6)]
Product {getProduct = 48}

Think of boolean values now. Like numbers, there's two semigroups that can be defined for them. Data.Monoid deals with this by providing for you the wrapper types of Any and All.

GHCi> Any True <> Any False
Any {getAny = True}
GHCi> mappend (All True) (All False)
All {getAll = False}
GHCi> mconcat $ map All [True, True, True, False, True]
All {getAll = False}

You can also use these types with mempty. See how they differ, despite nominally being wrappers over the same type:

GHCi> mempty :: All
All {getAll = True}
GHCi> mempty :: Any
Any {getAny = False}
GHCi> mempty :: Sum Int
Sum {getSum = 0}
GHCi> mempty :: Product Int
Product {getProduct = 1}

A Weird Interlude

There's a couple of weird types defined in Data.Monoid. The first is called Dual. Here's what it does:

GHCi> mappend (Dual [1, 2, 3]) (Dual [4, 5, 6])
Dual {getDual = [4,5,6,1,2,3]}
GHCi> getDual $ mappend (Dual [1, 2, 3]) (Dual [4, 5, 6])
[4, 5, 6, 1, 2, 3]

The docs give a rather brief description:

The dual of a Monoid, obtained by swapping the arguments of mappend.

There's also Endo. Here's a quick example of its usage:

GHCi> let thing = Endo ([1, 2, 3] ++) <> Endo (++ [4, 5, 6])
GHCi> appEndo thing [101, 102, 103]
[1,2,3,101,102,103,4,5,6]

The monoid of endomorphisms under composition.

If you're anything like me then the first time you read that definition, your mind was probably quite blank, before slowly reading through each of the words again, looking back at the example, back to the definition, before finally having that little lightbulb moment.

💡

Dealing with Maybe

Data.Monoid also includes two very nice wrappers for dealing with Maybe values. A type of Maybe a has an instance of Monoid providing that a has an instance of Monoid. For example:

GHCi> mappend (Just "Hello") (Just "World")
Just "HelloWorld"
GHCi> mappend (Just $ Sum 3) (Just $ Sum 7)
Just (Sum {getSum = 10})

The new types we get for dealing with Maybe are First and Last. Like their names suggest, they allow you to retrieve the first or the last Just values from a sequence of Maybe. Like so:

GHCi> First (Just "Merhaba") <> First Nothing <> First (Just "Dunya")
First {getFirst = Just "Merhaba"}
GHCi> getFirst $ First (Just "Merhaba") <> First Nothing <> First 
      (Just "Dunya")
Just "Merhaba"

And the same with Last:

GHCi> Last (Just "Merhaba") <> Last Nothing <> Last (Just "Dunya")
Last {getLast = Just "Dunya"}
GHCi> getLast $ Last (Just "Merhaba") <> Last Nothing <> Last (Just 
      "Dunya")
Just "Dunya"

Data.Monoid includes a few more gifts, but these also involve other other core Haskell typeclasses, and I would prefer to go over them in their own post, just for them.

Monoidal Functions (Assuming 'monoidal' is even a word)

One often overlooked instance of Monoid is defined for functions of type
(a -> b), where b itself has an instance of Monoid defined.

GHCi> :i Monoid
...
instance Monoid b => Monoid (a -> b)
...

An example of using this instance of Monoid can actually be seen in my other post here, about "Monoidal FizzBuzz".

Key takeaways

  • A monoid is an algebraic structure consisting of a set of elements, an associative-binary operation, and an identity element.
  • A monoid is just a semigroup with the addition of an identitive element.
  • The minimal definition for an instance of monoid for a type a is simply mempty, as something must implement the semigroup typeclass before an instance of monoid can be defined.
  • Data.Monoid includes some useful wrappers for working with certain types that can have multiple valid monoids.

Posted on by:

aibhstin profile

Aibhstin

@aibhstin

I'm an Ethical Hacking & Cybersecurity student and a Haskell programmer.

Discussion

markdown guide
 

Shouldn't 1 be the identity element for multiplication? a1 * 0 != a1

 

For multiplication, 1 is indeed the identitive element. Here, * represents a generic associative-binary operation, and 0 represents a generic identitive element. I should have made this more clear in the post, I apologize.