## Are idiom morphisms monad morphisms?

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 $\mathbf M = \langle M, 0, +, - \rangle$ and $\mathbf N = \langle N, 1, *, ^{-1} \rangle$, and a function $\varphi : M \rightarrow N$ which is a monoid homomorphism (that is $\varphi(0) = 1$, and $\varphi(m_1 + m_2) = \varphi(m_1) * \varphi(m_2)$), one can prove that $\varphi$ is also a group homomorphism (that is, it additionally preserves inverses: $\varphi(-m) = \varphi(m)^{-1}$). 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
`
Explore posts in the same categories: Algebra, Haskell

1. know-how Says:

What Moggi think of this?

2. FiSi Says:

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.

• FiSi Says:

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.