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

Explore posts in the same categories: Algebra, Haskell

This entry was posted on March 10, 2012 at 11:46 am and is filed under Algebra, Haskell. You can subscribe via RSS 2.0 feed to this post's comments. You can comment below, or link to this permanent URL from your own site.

5 Comments on “Are idiom morphisms monad morphisms?”

know-how Says:

March 13, 2012 at 8:59 pm
What Moggi think of this?

Reply
FiSi Says:

March 15, 2012 at 8:16 pm
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!

Reply
- Maciej Piróg Says:
  
  March 16, 2012 at 2:40 am
  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.
  
  Reply
  - FiSi Says:
    
    March 16, 2012 at 12:12 pm
    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.
  - Maciej Piróg Says:
    
    March 16, 2012 at 5:07 pm
    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.

maciejcs