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
About these ads

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.

5 responses to “Are idiom morphisms monad morphisms?

  1. know-how

    What Moggi think of this?

  2. FiSi

    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

        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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: