[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
    h . mconcat = mconcat . fmap f               (1)
[Z] ---------> Z
 |             |
 | fmap h      | h
 |             |
 v             v
[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
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.
    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. 


[*] 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
[1] https://hub.darcs.net/olf/haskell_for_mathematicians

More information about the Haskell-Cafe mailing list