[Haskell-cafe] monoid homomorphism
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.
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
h . mconcat = mconcat . fmap f (1)
[Z] ---------> Z
| fmap h | h
[B] ---------> B
This commutative square subsumes Li-yao's two squares. Instantiate the
equation (1) with empty and two-element lists to recover Li-yao's
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.
mconcat . pure = id (2)
mconcat . concat = mconcat . fmap mconcat (3)
See also chapters in 6 and 7 in . There, the example is linear
functions between vector spaces, which are algebra homomorphisms of the
monad of formal linear combinations.
[*] 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
More information about the Haskell-Cafe