Monoids – Haskell

Monoids are a fundamental concept in Haskell, often used in functional programming to model and work with combining operations. They provide a simple and elegant way to represent values that can be combined together in an associative manner, along with a neutral “identity” element.

In this article, we’ll explore what monoids are, how they work in Haskell, and where they can be applied effectively.

What is a Monoid?

In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element.

A monoid is a mathematical concept with the following properties:

1. An Associative Binary Operation: A function (<>) that combines two values of the same type in a way that the order of operations doesn’t matter. That is:

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

for all a, b, and c.

2. An Identity Element: A special value mempty such that:

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

for all x.

In Haskell, monoids are captured by the Monoid type class.

The Monoid Type Class in Haskell

The Monoid type class is defined in the Data.Monoid module (or more recently in Prelude module for GHC 8.4+). Its definition looks like this:

class Semigroup m => Monoid m where
    mempty  :: m
    mappend :: m -> m -> m
    mconcat :: [m] -> m
    mconcat = foldr mappend mempty

Key Components:

• mempty: The identity element of the monoid.
• mappend: The binary operation for combining two monoid values (usually aliased as (<>) from Semigroup).
• mconcat: A utility function that combines a list of monoid values into a single value.

Example: Monoids in Action

1. Numbers and Addition

The sum of numbers forms a monoid, where:

• mempty = 0 (the additive identity).
• (<>) or mappend = (+).

Haskell provides the Sum type as a monoid for addition:

import Data.Monoid (Sum(..))

exampleSum :: Sum Int
exampleSum = Sum 5 <> Sum 10 <> Sum 20  
-- Result: Sum 35

Here, Sum wraps integers and allows them to be combined as a monoid using addition.

2. Numbers and Multiplication

Similarly, multiplication is a monoid with:

• mempty = 1 (the multiplicative identity).
• (<>) = (*).

Haskell provides the Product type for multiplication:

import Data.Monoid (Product(..))

exampleProduct :: Product Int
exampleProduct = Product 5 <> Product 10 <> Product 2  -- Result: Product 100

Monoids for Common Data Types

1. Lists

Lists in Haskell are monoids with:

• mempty = [] (empty list).
• (<>) = (++) (list concatenation).

Example:

exampleList :: [Int]
exampleList = [1, 2] <> [3, 4] <> [5]  -- Result: [1, 2, 3, 4, 5]

2. Strings

Strings are just lists of characters ([Char]), so they form a monoid with:

• mempty = "" (empty string).
• (<>) = (++) (string concatenation).

Example:

exampleString :: String
exampleString = "Hello, " <> "world!"  
-- Result: "Hello, world!"

3. Booleans

Booleans form monoids under two operations:

• Logical AND (All):
  • mempty = True
  • (<>) = (&&)
• Logical OR (Any):
  • mempty = False
  • (<>) = (||)

Example:

import Data.Monoid (All(..), Any(..))

exampleAll :: All
exampleAll = All True <> All False <> All True  
-- Result: All False

exampleAny :: Any
exampleAny = Any True <> Any False <> Any False  
-- Result: Any True

Custom Monoids

You can define your own monoids by implementing the Monoid type class. For example:

Defining a Monoid for Vectors (2D Points)

data Vector = Vector Int Int
    deriving (Show)

instance Semigroup Vector where
    (Vector x1 y1) <> (Vector x2 y2) = Vector (x1 + x2) (y1 + y2)

instance Monoid Vector where
    mempty = Vector 0 0

Usage

exampleVector :: Vector
exampleVector = Vector 1 2 <> Vector 3 4 <> mempty  -- Result: Vector 4 6

Why Monoids Are Useful

1. Combining Values

Monoids provide a uniform way to combine values. Whether you’re adding numbers, concatenating lists, or merging data, monoids ensure consistency and reduce boilerplate.

2. Reducing Lists

The mconcat function is particularly useful for reducing a list of monoid values into a single value:

exampleMconcat :: Sum Int
exampleMconcat = mconcat [Sum 1, Sum 2, Sum 3]  
-- Result: Sum 6

3. Abstraction and Composability

Monoids abstract the concept of combination, making your code more generic and composable. Libraries like Foldable and Traversable often rely on monoids for aggregations.

4. Parallelism

The associative nature of monoids makes them ideal for parallel computations. For instance, when combining large datasets, monoids allow efficient splitting and merging.

Monoids in the Wild: Practical Applications

1. Logging Use mappend to combine log messages into a single cohesive log entry.
2. Configuration Combine configuration options using monoids to ensure default settings are preserved while allowing overrides.
3. Data Aggregation Use monoids to combine statistical data, such as computing the total, average, or maximum.
4. Parsing Combine parsers or intermediate parsing results using monoids for modular and reusable parsing logic.

Explain Monoids Like I’m Five Years Old (ELI5)

Imagine you have a box of toys (this is your set of things), and you’re allowed to combine these toys in a certain way (this is your operation).

To call this combination a monoid, two rules need to be true:

1. Associative Rule: It doesn’t matter how you group things when combining. For example, if you’re stacking toy blocks:
   • Combining (Block A + Block B) + Block C is the same as Block A + (Block B + Block C).
   • The order stays the same, but how you group doesn’t matter.
2. Identity Element: There’s a special toy (the identity) that doesn’t change anything when you combine it with another toy. For example:
   • If you have an empty block (let’s call it “Invisible Block”), stacking it with any other block doesn’t change the stack.

Example: Imagine your toys are numbers:

• The operation is addition (+).
• The identity element is 0, because adding 0 to any number doesn’t change it.

This setup is a monoid because:

• Addition is associative: (1 + 2) + 3 = 1 + (2 + 3).
• 0 is the identity: 5 + 0 = 5.

In Haskell, monoids are useful for combining things like numbers, strings, or lists in a structured way.

Summary

Monoids in Haskell are a powerful abstraction for combining values in an associative manner, with an identity element for simplicity. By leveraging the Monoid type class, you can write more generic, reusable, and composable code. Whether you’re working with numbers, strings, lists, or custom data types, monoids provide a consistent framework for combining data.

Understanding and applying monoids in your Haskell programs can greatly enhance your ability to work with structured and modular code.

💡 Helpful References

LearnYouAHaskell - Monoids
https://learnyouahaskell.github.io/functors-applicative-functors-and-monoids.html#monoids