During the last Algebra of Programming meeting we were talking about idioms (applicative functors), monads, traversals, and such. At one moment a definition of **idiom morphism** appeared on the whiteboard, which is a function (a brave person might even say `natural transformation’) of type (for applicative `M`

and `N`

)

f :: M a -> N a

which respects the following:

f . pure = pure
f (mf <*> mx) = f mf <*> f mx

I was wondering: Sometimes it is the case that homomorphisms of simpler algebraic structures (for example, monoids) are authomatically homomorphisms of more complicated structures (for example, groups).

Indeed, given two groups and , and a function which is a monoid homomorphism (that is , and ), one can prove that is also a group homomorphism (that is, it additionally preserves inverses: ). Furthermore, monads give rise to applicative functors (via `pure = return`

and `(<*>) = ap`

). Of course, there is a notion of **monad morphism**, which is a function (for monads `M`

and `N`

)

f :: M a -> N a

subject to:

f . return = return
f (m >>= k) = f m >>= f . k

So maybe being an idiom morphism is sufficient to be a monad morphism?

It didn’t sound very probable, but it was most certainly something worth examining. A positive answer would be of a nontrivial use, since monad morphisms play a central role in the theory of monad transformers. Sadly, no happy ending here. Idiom morphisms **don’t** need to be monad morphisms. A counterexample:

phi :: [a] -> Maybe a
phi xs | odd (length xs) = Just (head xs)
| otherwise = Nothing

This function is an idiom morphism (hint: `<*>`

preserves the parity of the product of the lengths of its arguments), while it is not a monad morphism:

phi ([0,1] >>= \x -> [0..x])
=
phi [0,0,1]
=
Just 0

while

phi [0,1] >>= \x -> phi [0..x]
=
Nothing >>= \x -> phi [0..x]
=
Nothing

### Like this:

Like Loading...

### About Maciej Piróg

I am a functional programmer. I believe in large cardinals, axiom of choice, and that "P=NP" will not be solved in my lifetime. I think that category theory is abstract nonsense, and that is why it gives me this Monty-Python-style feeling of amusement.

What Moggi think of this?

I guess part of the reason (/rationale/whatever) behind this difference stems from the fact that inverses in groups can be fully characterised by monoid-level equations (i.e., x = -y iff x + y = y+ x = 0); so the monoid homomorphism would just “float through” these equations, preserving the truth of the equation. In the case of monads, however, I can’t readily see how one could characterise the join-related equations (which barely, if at all, involve function types).

Wonder if you could give some (category-theoretical?) presentation of functors for which this sort of morphism “lifting” holds?

Also, first! 😉

nLab says (http://ncatlab.org/nlab/show/homomorphism) that it is a “coincidence” that monoid morphisms (and even semigroup morhisms) between two groups are necessarily group morphisms, so I wouldn’t expect any fancy characterisation/presentation here.

Sorry, but what they say doesn’t make half a sense to me. One, if φ is not a monoid morphism, it can’t be a group morphism either; two, I cannot see how you can construct a semigroup morphism from a monoid into something that’s does not have a monoid structure. Also, consider that if φ : (M, +) →(A, ×) and (M, +, 0) forms a monoid, then (A, ×, φ(0)) forms one, since you have

[blockquote]φ(m) = φ(m + 0) = φ(m) × φ(0).[/blockquote]

And indeed, in this case the characterisation of neutral element is given in terms of semiring-based equations only, much like the inverses for groups. That said, I could have made some embarrassing mistake above, so feel free to point it out.

One: I think what they say is that given two groups (M, *, ^-1, 1) and (N, +, -, 0), every function f : M -> N satisfying f (m0 * m1) = f m0 + f m1 is a group homomorphism. But, given two monoids, (M, *, 1) and (N, +, 0), a function f : M -> N satisfying the same equation is not necessarily a monoid homomorphism. For example, consider M = ({a,e}, *, e) ,where a*a=a, a*e=a, e*a=a, e*e=e. A function f : M -> M defined as f x = a satisfies the equation (since f (x*y) = a = a*a = f x * f y), but is not a monoid homomorphism (it does not preserve e).

The thing about isomorphism is that given (M, *, 1) and (N, +, 0) and a bijectoin f : M -> N which satisfies the equation, f is a monoid isomorphism. Proof: Let’s assume that f w = 0, for w \in M. We calculate for any m:

w * m =

g (f w) * g (f m) =

g (f (g (f w) * g (f m))) =

g (f (g (f w)) + f (g (f m))) =

g (f w + f m) =

g (0 + f m) =

g (f m) =

m

so w is an identity, so w = e, so f e = 1, so f is a monoid homomorphism (and a bijection, hence it is an isomorphism). (QED)

I dont’t think they want to say anything more than that.