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
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
f :: M a -> N a
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
phi [0,1] >>= \x -> phi [0..x] = Nothing >>= \x -> phi [0..x] = NothingExplore posts in the same categories: Algebra, Haskell