Monoids and Foldables

In this and the coming chapters, we change gear from Haskell language features to Haskell programming/design patterns. These patterns are ways of structuring commonly occurring programming problems or situations and communicating about them to other Haskell programmers. Although they show some similarities with the classical object-oriented (OO) design patterns that were introduced by the Gang of Four (GoF), there are many differences as well.

Firstly, while OO programming (OOP) design patterns were devised by software engineers for software engineers, Haskell’s patterns are essentially concepts drawn from the mathematical fields of abstract algebra and category theory repurposed for (functional) programming. Besides being an astounding use of abstract mathematics in otherwise non-mathematical day-to-day programming, this has a number of consequences:

• OOP design patterns came about in a somewhat ad hoc fashion in the last 30-35 years. In contrast...

Semigroups and monoids

We start this chapter with two fairly elementary abstractions: semigroups and monoids. These are both standard concepts in the field of mathematics called algebra, and we are all familiar with examples of semigroups and monoids from primary school arithmetic (though not necessarily with the general concept). What is perhaps less well-known is that semigroups and monoids are also omnipresent in (functional) programming.

Semigroups

A semigroup is an s type with a (<>) binary operator:

GHC.Base
class Semigroup s where
  (<>) :: s -> s -> s

The binary operator must obey one law: associativity.

Associativity

This law states that when combining more than two values, the positioning of parentheses does not matter:

x <> (y <> z) == (x <> y) <> z

For this reason, the parentheses are usually omitted, and we simply write x <> y <> z.

Instances

The list type forms a semigroup with the (++) operator:

GHC.Base
instance Semigroup [a] where
  (<>) = (++)

The following example demonstrates the associativity of this operator:

*Main> [1,2] <> ([3] <> [4,5])
[1,2,3,4,5]
*Main> ([1,2] <> [3]) <> [4,5]
[1,2,3,4,5]

Likewise, numeric types form a semigroup with addition (+) but also with multiplication (*). Indeed, we have this, for example:

*Main> (1 + 2) + 3
6
*Main>...

Kinds and type constructors

We have already studied and used types extensively. They allow us to distinguish between different forms of values in a way that can be used to document and automatically check our code. Kinds do the same thing one level up: they are a way of distinguishing different forms of types.

Proper types

The simplest and most ubiquitous group of types are so-called proper types. These are what we meant when we used the word type earlier in this book. Probably all the types that come to your mind are proper types: Int, Bool, [Char], Float -> String, and so on.

The kind associated with proper types is written *. This kind is often pronounced type, and in recent years, GHC has provided Type as a synonym for * in the Data.Kind module.

We can check the kind of a type in GHCi with the :kind command (or :k for short):

*Main> :kind Int
Int :: *
*Main> :kind Bool -> (Char, Float)
Bool -> (Char, Float) :: *

Another term for proper types is...

Foldables

Foldables are type constructors of the * -> * kind that represent collections of elements and come equipped with particular functionality.

The Foldable type class

The functionality that should be provided by a foldable is captured in the Foldable type class. This type class is a so-called type constructor class because it ranges over t type constructors rather than proper types:

Data.Foldable
class Foldable t where
  fold     :: Monoid m => t m -> m
  foldMap  :: Monoid m => (a -> m) -> t a -> m
  foldMap' :: Monoid m => (a -> m) -> t a -> m
  foldr    :: (a -> b -> b) -> b -> t a -> b
  foldr'   :: (a -> b -> b) -> b -> t a -> b
  foldl    :: (b -> a -> b) -> b -> t a -> b
  foldl'   :: (b -> a ...

Case study – Sortedness

We now perform a small case study designing an algorithm to check whether a collection is sorted.

Sorted lists

The more directed definition for checking whether a list is sorted makes use of explicit recursion and distinguishes three cases:

sorted :: Ord a => [a] -> Bool
sorted []       = True
sorted [x]      = True
sorted (x:y:zs) = x <= y && sorted (y:zs)

Empty and one-element lists are always sorted. A two-or-more-element list is sorted if the first two elements are in ascending order and if the tail is sorted.

We would like to carry this definition over to other Foldable collections. Unfortunately, it does not fit the structurally recursive pattern of foldr or foldMap that is supported by other foldables. The reason is that the definition distinguishes the one-element list from other non-empty lists.

An attempt with structural recursion

Let us attempt...

Summary

In this chapter, we have explored two basic algebraic structures that occur frequently in functional programs: semigroups and monoids. While these are interesting patterns on their own, they turn out to be particularly useful for aggregating the elements of collections. For that purpose, we have introduced the notion of type constructors, types of higher kinds that allow us to separate the collection type from its element type. Next, we have explored the Foldable constructor type class for collections whose elements can be extracted into a list. Its minimal complete definition based on foldMap turns out to be a Swiss Army knife that can be conveniently instantiated with different monoids to accomplish all manner of aggregation tasks. Finally, we have developed a custom monoid to tackle a new task, checking the sortedness of foldable collections.

Chapter 10, Functors, Applicative Functors, and Traversables, continues with a hierarchy of type classes for type constructors...

Questions

1. What is a semigroup?
2. What is a monoid?
3. What are some examples of semigroups and monoids?
4. What are type constructors?
5. What is a foldable?

Further reading

• The Data.Semigroup library documentation: https://hackage.haskell.org/package/base-4.18.0.0/docs/Data-Semigroup.html
• The Data.Monoid library documentation:

  https://hackage.haskell.org/package/base-4.18.0.0/docs/Data-Monoid.html

• The Data.Foldable library documentation: https://hackage.haskell.org/package/base-4.18.0.0/docs/Data-Foldable.html

Answers

1. A semigroup is an s type with a (<>) binary associative operator. In Haskell, it is modeled by the following type class:

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

   This is subject to the following associativity law:

(x <> y) <> z = x <> (y <> z)

2. A monoid is a semigroup (that is, type m with a (<>) binary associate operator) that also has a neutral element (aka identity), mempty. In Haskell, it is modeled by the following subclass of Semigroup:

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

   This is subject to the two identity laws:

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

3. The following table lists examples from the standard libraries we have covered. The first column gives the names of the types (possibly subject to type class constraints). The second column lists the names of the newtype wrappers, in case there are multiple possibilities for the...