An overview of functional design patterns, with a bit of math sprinkled in.

functional_patterns.md

Note: While this is public, this is mostly written for my own sake, to better understand these concepts in relation to their pure mathematical foundations. Comments and suggestions welcome!

---

Table of contents

• Introduction
• Monoids
  • Definition
  • Example 1: ints with addition
  • Example 2: strings with concatenation
  • Why do we care?
• Functors: WIP
• Monads: TODO
• Applicatives: TODO
• Sources

---

Introduction

This gist aims to give a brief overview of certain mathematical objects and why programmers care about them. The overall structure for each section will start with a definition for the object, then a few examples, followed by a list of properties that makes the object useful/interesting to programmers.

Some additional notes for this gist:

• Basic proof-reading and some mathematical maturity is assumed for the definitions.
• All of the examples use OCaml-style notation, although it shouldn't matter too much if you're unfamiliar with OCaml.
• We treat programming types as sets, i.e. int is the same as $\mathbb{Z}$.
  • Many of the definitions denote sets using $T$ for "type".

Monoids

Definition

A monoid is a set equipped with an associative binary operation and an identity element. More concretely, suppose we have:

• Some set $T$
• Some binary operator $\cdot\colon T\times T\to T$

This forms a monoid if for all ${a, b, c}\in T$, we have

$$ (a\cdot b)\cdot c = a\cdot (b\cdot c), \tag{Associativity} $$

and there exists some $e\in T$ such that

$$ e\cdot a = a\cdot e = a. \tag{Identity element} $$

For brevity, we write this monoid as $(T, \cdot, e)$.

Example 1: ints with addition

Consider the monoid $(\texttt{int}, +, 0)$. We can verify that this is a monoid, since for all ${a, b, c}\in \texttt{int}$, we have

$$ (a + b) + c = a + (b + c), \tag{Associativity} $$

and $0\in \texttt{int}$ satisfies

$$ 0 + a = a + 0 = a. \tag{Identity element} $$

Example 2: strings with concatenation

Let $\wedge$ denote the string concatenation operator. Consider the monoid $(\texttt{string}, \wedge, \texttt{""})$. We can verify that this is a monoid, since for all ${a, b, c}\in \texttt{string}$, we have

$$ (a\wedge b)\wedge c = a\wedge (b\wedge c), \tag{Associativity} $$

and the empty string $\texttt{""}\in \texttt{string}$ satisfies

$$ \texttt{""}\wedge a = a\wedge \texttt{""} = a. \tag{Identity element} $$

Why do we care?

Prototypical monoid for this section: $(\texttt{int}, +, 0)$. Keep in mind that everything discussed here extends to all monoids, including $(\texttt{int}, \cdot, 1)$, $(\texttt{string}, \wedge, \texttt{""})$, and beyond.

• List computation: Since addition is closed (i.e. adding two ints yields another int), we can apply the $+$ operator to an arbitrary number of ints (i.e. a list of ints), instead of just two. We do this by continually applying $+$ between our current sum and the next value in the list, until we have summed up the entire list.
  • Note: Since our operator takes in two arguments, what value should we start with for computation? Remember that monoids contain an identity element; in the case of summing ints, we can start with the value 0.
  • Note: This is sometimes called "reducing", since we can reduce a list of ints to a single int via repeated application of $+$.
• Incremental computation: Again, since addition is closed, we can incrementally compute the sum of ints. If we have a current sum and are given more ints to add, we don't have to recompute anything; we can simply add to our existing sum.
• Parallel computation: Since addition is associative, we can perform it in any arbitrary order. This lends itself very well to parallelizing the computation, since multiple cores can add parts of the list simultaneously, before the partial sums are added together.

Note: Combinations of monoids are also monoids! For example, consider the monoids $(\texttt{int}, +, 0)$ and $(\texttt{string}, \wedge, \texttt{""})$. We show that the set int * string forms a monoid, by defining a binary operation and identity element pairwise. Let $n_1, n_2\in \texttt{int}$ and $s_1, s_2\in \texttt{string}$. Then if we define $*$ by

$$ (n_1, s_1) * (n_2, s_2) = (n_1 + n_2, s_1\wedge s_2), $$

we get the monoid $(\texttt{int * string}, *, (0, \texttt{""}))$.

Functors

Sources

• The Functional Programmer's Toolkit - Scott Wlaschin