[Haskell-cafe] monoid homomorphism
Olaf Klinke
olf at aatal-apotheke.de
Thu Sep 22 19:32:17 UTC 2022
> Hello every one,
> I'm reading "Programming with Categories Brendan Fong Bartosz Milewski David I. Spivak"
> and here there's an example of monoid in Haskell:
>
> Consider the monoids Z× � (Z, 1, ×) and BAND � (B, true, AND). Let
> is_odd : Z → B be the function that sends odd numbers to true and even numbers to
> false. This is a monoid homomorphism. It preserves identities because 1 is odd, and
> it preserves composition because the product of any two odd numbers is odd, but the
> product of anything with an even number is even.
>
>
> I'd like representing it graphically I mean the object Zx and arrows about is_odd function,
> but I do not know how can do it.
>
> This is a valid example of monoid homomorphism and I'd like to know
> the Haskell implementation and the corresponding categorically view.
>
> Thanks
> Co
Extending Li-yao's excellent answer, you could draw a single diagram
using the free monoid monad. Disregarding non-termination and infinite
lists, the free monoid is the list monad [*]. Every monoid has a
structure map, namely
mconcat :: Monoid m => [m] -> m
satisfying equations (2) and (3) below. A function h :: z -> b between
monoids is a monoid homomorphism iff it commutes with the structure
map:
h . mconcat = mconcat . fmap f (1)
mconcat
[Z] ---------> Z
| |
| fmap h | h
| |
v v
[B] ---------> B
mconcat
This commutative square subsumes Li-yao's two squares. Instantiate the
equation (1) with empty and two-element lists to recover Li-yao's
squares, where
mconcat [] = mempty,
mconcat [x,y] = x `mappend` y.
In "Programming with Categories" terminology: Monoid homomorphisms are
[]-Algebra homomorphisms (Definition 4.9). What is not contained in
"Programming with Categories" are the Eilenberg-Moore algebra laws.
Namely,
mconcat . pure = id (2)
mconcat . concat = mconcat . fmap mconcat (3)
See also chapters in 6 and 7 in [1]. There, the example is linear
functions between vector spaces, which are algebra homomorphisms of the
monad of formal linear combinations.
Olaf
[*] Mathematically, the free monoid over a set A is the set of finite
words in the alphabet A, with the empty word as 'mempty' and
concatenation of words as 'mappend'. E.g. the free monoid over Char is
Text.
[1] https://hub.darcs.net/olf/haskell_for_mathematicians
More information about the Haskell-Cafe
mailing list