[prev in list] [next in list] [prev in thread] [next in thread] 

List:       haskell-cafe
Subject:    Re: [Haskell-cafe] monoid homomorphism
From:       Olaf Klinke <olf () aatal-apotheke ! de>
Date:       2022-09-22 19:32:17
Message-ID: 5f1c6b582439bc6fc67ef7ad4cdb9e9d381f6d47.camel () aatal-apotheke ! de
[Download RAW message or body]

> 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

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
[prev in list] [next in list] [prev in thread] [next in thread]