> **Puzzle 80.** Tell me a few more homomorphisms between monoids that you routinely use, or at least know.

Here are a couple programming examples.

In Haskell, in the base language there is a type class for Monoids defined in [`Data.Monoid`](https://hackage.haskell.org/package/base-4.11.1.0/docs/Data-Monoid.html).

Haskell has its own notation for Monoids. In Haskell, \\(I\\) becomes `mempty` and \\(\otimes\\) becomes `(<>)`.

Two of the monoids defined in `Data.Monoid` are `Monoid (First a)` and `Monoid [a]`. `First a` is also defined in `Data.Monoid`.

`First` is a [`newtype`](https://wiki.haskell.org/Newtype) wrapper around `Maybe a`. Its identity element is `First Nothing`. Its monoidal operation `(<>)` has the following definition

The other monoid instance is for *list*, the [free monoid](https://en.wikipedia.org/wiki/Free_monoid) over `a`. Its identity element is `[]` and monoidal operation is *list append* (ie, [`++`](https://hackage.haskell.org/package/base-4.11.1.0/docs/Prelude.html#v:-43--43-)).

There are two monoid homomorphisms between these types.

1. The first homomorphism is `First . listToMaybe :: [a] -> First a`. Here `listToMaybe` is defined in [`Data.Maybe.listToMaybe`](https://hackage.haskell.org/package/base-4.11.1.0/docs/Data-Maybe.html#v:listToMaybe).

This function tries to take the first element of a list. If there is such an element `a` then it gets wrapped in `First (Just a)`. If it does not exist (because the list is empty), then it returns `First Nothing`.

The *Monoid homomorphisms laws* in Haskell are defined by:

$$(\mathsf{First}\; .\; \mathsf{listToMaybe})\; (a\; \mathsf{<>}\; b) \equiv ((\mathsf{First}\; .\; \mathsf{listToMaybe})\; a)\; \mathsf{<>}\; ((\mathsf{First}\; .\; \mathsf{listToMaybe})\; b)$$

$$(\mathsf{First}\; .\; \mathsf{listToMaybe})\; (\mathsf{mempty}\; ::\; \mathsf{[}a\mathsf{]}) \equiv (\mathsf{mempty}\; :: \; \mathsf{First}\; a)$$

Hence this function is a monoid homomorphism.

2. The second homomorphism is in the opposite direction: `maybeToList . getFirst :: First a -> [a]`. This is the *right inverse* of `First . listToMaybe`, so:

$$(\mathsf{First}\; .\; \mathsf{listToMaybe})\; .\; (\mathsf{maybeToList}\; .\; \mathsf{getFirst}) \equiv \mathsf{id}$$

The function `maybeToList` is defined in [`Data.Maybe.maybeToList`](https://hackage.haskell.org/package/base-4.11.1.0/docs/Data-Maybe.html#v:maybeToList). It obeys the same monoid homomorphism laws as its left inverse.

Here are a couple programming examples.

In Haskell, in the base language there is a type class for Monoids defined in [`Data.Monoid`](https://hackage.haskell.org/package/base-4.11.1.0/docs/Data-Monoid.html).

Haskell has its own notation for Monoids. In Haskell, \\(I\\) becomes `mempty` and \\(\otimes\\) becomes `(<>)`.

Two of the monoids defined in `Data.Monoid` are `Monoid (First a)` and `Monoid [a]`. `First a` is also defined in `Data.Monoid`.

`First` is a [`newtype`](https://wiki.haskell.org/Newtype) wrapper around `Maybe a`. Its identity element is `First Nothing`. Its monoidal operation `(<>)` has the following definition

(First Nothing) <> x = x

(First (Just a)) <> _ = First (Just a)

The other monoid instance is for *list*, the [free monoid](https://en.wikipedia.org/wiki/Free_monoid) over `a`. Its identity element is `[]` and monoidal operation is *list append* (ie, [`++`](https://hackage.haskell.org/package/base-4.11.1.0/docs/Prelude.html#v:-43--43-)).

There are two monoid homomorphisms between these types.

1. The first homomorphism is `First . listToMaybe :: [a] -> First a`. Here `listToMaybe` is defined in [`Data.Maybe.listToMaybe`](https://hackage.haskell.org/package/base-4.11.1.0/docs/Data-Maybe.html#v:listToMaybe).

This function tries to take the first element of a list. If there is such an element `a` then it gets wrapped in `First (Just a)`. If it does not exist (because the list is empty), then it returns `First Nothing`.

The *Monoid homomorphisms laws* in Haskell are defined by:

$$(\mathsf{First}\; .\; \mathsf{listToMaybe})\; (a\; \mathsf{<>}\; b) \equiv ((\mathsf{First}\; .\; \mathsf{listToMaybe})\; a)\; \mathsf{<>}\; ((\mathsf{First}\; .\; \mathsf{listToMaybe})\; b)$$

$$(\mathsf{First}\; .\; \mathsf{listToMaybe})\; (\mathsf{mempty}\; ::\; \mathsf{[}a\mathsf{]}) \equiv (\mathsf{mempty}\; :: \; \mathsf{First}\; a)$$

Hence this function is a monoid homomorphism.

2. The second homomorphism is in the opposite direction: `maybeToList . getFirst :: First a -> [a]`. This is the *right inverse* of `First . listToMaybe`, so:

$$(\mathsf{First}\; .\; \mathsf{listToMaybe})\; .\; (\mathsf{maybeToList}\; .\; \mathsf{getFirst}) \equiv \mathsf{id}$$

The function `maybeToList` is defined in [`Data.Maybe.maybeToList`](https://hackage.haskell.org/package/base-4.11.1.0/docs/Data-Maybe.html#v:maybeToList). It obeys the same monoid homomorphism laws as its left inverse.