> **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.
Version 2.1.8p2
