Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://a-guide-to-the-purescript-numeric-hierarchy.readthedocs.io/en/latest/monoids.html below:

Website Navigation

• A guide to the PureScript numeric hierarchy

Monoids — A guide to the PureScript numeric hierarchy latest documentation

You are probably already aware of monoids (via the Monoid type class), since they come up quite often in programming. We’ll just quickly remind ourselves about what makes something a monoid and cover a few examples, but in a slightly more mathematically-oriented way. The main aim of this section is to make you a bit more comfortable about mathematical ideas and notations by using them to describe an idea which you are hopefully already familiar with. Another purpose of this section is to prepare you for the next section, in which we will talk about a specific kind of monoid which turns out to be rather important.

Here are a few rules about how adding integers together works:

• If we add together two integers, we always get another integer.
• It doesn’t matter what order we bracket up additions, we always get the same answer. That is, \((x + y) + z\) is always the same as \(x + (y + z)\) for any integers \(x, y, z\).
• Adding \(0\) to any integer yields the same integer.

Here are a few more rules about how multiplying integers works:

• If we multiply two integers, we always get another integer.
• It doesn’t matter what order we bracket up multiplications, we always get the same answer. That is, \((xy)z\) is always the same as \(x(yz)\) for any integers \(x, y, z\).
• Multiplying any integer by \(1\) yields the same integer.

Now, instead of integers, we will consider a different set: the set of truth-values \(\{T, F\}\). This set corresponds to the Boolean type in PureScript. Here are some rules for how the “logical and” operation \((\land)\) works on truth-values:

• If we apply the \(\land\) operation to two truth-values, we always get another truth-value.
• It doesn’t matter what order we bracket up \(\land\), we always get the same answer. That is, \((x \land y) \land z\) is the same as \(x \land (y \land z)\) for all \(x, y, z\).
• \(P \land T\) is always the same as \(P\), for any truth-value \(P\). If it’s not obvious what I mean by \(P \land T\), it means the same thing as the PureScript code p && true.

Hopefully a pattern will be starting to emerge: in each case, we have a set, an operation which gives us a way of combining two elements of that set to produce another element of the same set, and some rules that the operation should satisfy. The general definition of a monoid is as follows:

A monoid is a set \(M\), together with an operation \(*\), such that the following laws hold:

1. Closure. \(\forall x, y \in M.\; x * y \in M\).
2. Associativity. \(\forall x, y, z \in M.\; (x * y) * z = x * (y * z)\).
3. Identity. \(\exists e \in M.\; \forall x \in M.\; e * x = x * e = x\).

Looking back to the examples above, we have the monoids of:

• the integers under addition, where the set is \(\mathbb{Z}\), the operation is addition, and the identity element is \(0\),
• the integers under multiplication, where the set is \(\mathbb{Z}\), the operation is multiplication, and the identity element is \(1\),
• truth values under logical and, where the set is \(\{T, F\}\), the operation is \(\land\), and the identity element is \(T\).

The operation \(*\) corresponds to append in PureScript, and that the identity element (conventionally written \(e\)) corresponds to mempty in PureScript.

We will now look at a few non-examples of monoids and talk about why they fail to be monoids.

First, if we take the set of natural numbers which are less than 4, that is \(\{0, 1, 2, 3\}\), and take addition as the operation, this fails to be a monoid because it does not satisfy closure. To show this we need to find a pair of elements such that their sum is not in the set. One such choice is \(3 + 1\), which of course equals \(4\), which is not in the set. We say that a set is closed under an operation if performing that operation on two elements of the set always produces another element of the set; this is where the name “closure” comes from.

An example of something failing to be a monoid because the operation is not associative could be the set of floating point number values under addition. For example, try (0.1 + 0.2) + 0.3 in a console, and compare the result to 0.1 + (0.2 + 0.3).

An example of something failing to be a monoid because of a lack of an identity element could be the set of even numbers under multiplication. The first two laws are satisfied, but since 1 is not an even number, we don’t have an identity element.

A brief interlude on notation: if we want to refer to a specific monoid, we write it as a pair where the first element is the set and the second is the operation. For example, the monoid of integers under addition is written as \((\mathbb{Z}, +)\). If it is clear from context which operation we are talking about, we often omit the operation and just write the set, e.g. we might simply say \(\mathbb{Z}\) is a monoid.

Exercise 2.1. Consider the set of natural numbers together with the operation of subtraction: \((\mathbb{N}, -)\). This is not a monoid. Can you say which of the three laws fail to hold (it might be more than one) and why?

Exercise 2.2. The set of rational numbers is the set of numbers which can be written as the ratio of two integers \(\frac{a}{b}\). There is a short-hand notation for this set too: \(\mathbb{Q}\) (for “quotient”). Show that \((\mathbb{Q}, +)\) is a monoid by checking each of the three laws. What is the identity element?

Exercise 2.3. (Harder) Prove that a monoid can only have one identity element. To do this, first suppose that you have two elements of some monoid; call them, say, \(e\) and \(e'\), and then show that if they are both identity elements then they must be equal to each other. Be careful here: it’s not enough to take one specific example of a monoid and show that it only has one identity element. You have to construct an argument which will work for any monoid, which means you aren’t allowed to assume anything beyond what is in the definition of a monoid.

Note

In general, if we want to prove that there is a unique element of some set which has some particular property, we do this by taking two arbitrary elements of the set, assuming that they both have this property, and then showing that they must be equal.

Since monoids have a unique identity element, we can talk about the identity element of a monoid, rather than just an identity element.

Consider the set \(\{e\}\), which contains precisely one element, \(e\). We can define an operation \(*\) on this set as follows:

\[e * e = e\]

That’s all we need to do to define \(*\), because there are no other possible values to consider. Then, \(\{e\}\) is a monoid. It’s not very interesting which is why it gets called the trivial monoid. This corresponds exactly to the Unit type in PureScript; the Unit type has precisely this Monoid instance too.

Let \(X\) be any set, and consider the set of functions from \(X\) to \(X\), which we denote by \(\mathrm{Maps}(X, X)\). If we take function composition \(\circ\) as our operation, we have a monoid \((\mathrm{Maps}(X, X), \circ)\). Let’s check this:

1. Closure. The composite of two functions from \(X\) to \(X\) is itself a function from \(X\) to \(X\), so closure is satisfied.
2. Associativity. Function composition is associative, so associativity is satisfied.
3. Identity. The identity function \(e : X \rightarrow X\) defined by \(e(x) = x\) for all \(x \in X\) is the identity element with respect to function composition, so identity is satisfied.

This may seem a bit abstract, so here’s a concrete example. We will take the set \(X\) to be the set \(\{A, B\}\) which contains just two elements. (The elements \(A\) and \(B\) don’t really mean anything here, they’re just symbols.) Then there are four functions from \(X\) to \(X\):

• The identity function \(e(x) = x\),
• The constant functions \(f_A\) and \(f_B\), which ignore their argument and always return \(A\) and \(B\) respectively, and
• The swapping function \(f_{swap}\), which sends \(A\) to \(B\), and \(B\) to \(A\).

In PureScript:

e :: X -> X
e x = x
  -- or simply e = identity

fA :: X -> X
fA _ = A
  -- or simply f1 = const A

fB :: X -> X
fB _ = B
  -- or simply f2 = const B

fSwap :: X -> X
fSwap A = B
fSwap B = A

Here are a few examples of how the monoid operation works in this monoid:

\[ \begin{align}\begin{aligned}f_A \circ f_B = f_A\\f_B \circ f_{swap} = f_B\\f_{swap} \circ f_{swap} = e\end{aligned}\end{align} \]

(check that you agree).

This monoid is implemented in PureScript in the module Data.Monoid.Endo, which is part of the purescript-prelude library.

We now move on to the last example of a monoid in this chapter:

Exercise 2.4. Let \((M, *)\) be any monoid, and let \(X\) be any set. Define an operation \(\star\) on the set \(\mathrm{Maps}(X, M)\) — that is, the set of functions from \(X\) to \(M\) — as follows:

\[f \star g = x \mapsto f(x) * g(x)\]

On notation: the arrow (\(\mapsto\)) can be read “maps to”. The mathematical notation \(x \mapsto x + 4\) means essentially the same thing as the PureScript code \x -> x + 4, that is, it denotes a function.

That is, the star product \(\star\) of two functions \(f\) and \(g\) is a new function which applies both \(f\) and \(g\) to its argument, and then combines the results using the monoid operation \(*\) from the monoid \(M\). Prove that \((\mathrm{Maps}(X, M), \star)\) is a monoid; what is the identity element?

The monoid in this exercise is also implemented in PureScript’s Prelude; in fact it is the default Monoid instance for functions, written as Monoid b => Monoid (a -> b).

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4