First idea: We really want to be able to mix the “normal function” category and the Kleisli category. (I see where this is headed…)

We want to map transformations between categories. Typically one category will be more featureful, so transformations only go one way.

-- Gabriel calls this "map". I like "lift"
lift :: Monad m => (a -> b) -> (a -> m b)
lift f = return . f

Note that the reverse is impossible in general ((a -> m b) -> (a -> b)).

To combine our logic, then:

f      ::              a ->   b
lift f :: (Monad m) => a -> m b
g      :: (Monad m) => b -> m c
g <=< lift f :: (Monad m) => a -> m c

This is wasteful (gets in the way of compiler optimizations):

h <=< lift g <=< lift f :: Monad m => a -> m d

However, we factor out lift (we assume this):

h <=< lift (g . f)

We also assume that g <=< lift id <=< f = g <=< f. This is easy to prove, since (return is the identity of Kleisli composition)

lift id = return . id = return

Proof:

  g <=< lift id <=< f
= g <=< return <=< f
= g <=< f :: Monad m => a -> m c

A functor transforms one category into another category. Above, normal functions monadic functions.

Source category \(A\) must obey these laws:

• Left identity: \(1_A \circ_A f = f\)
• Right identity: \(f \circ_A 1A = f\)
• Associativity: \((f \circ_A g) \circ_A h = f \circ_A (g \circ_A h)\)

Destination category must also obey these laws:

• Left identity: \(1_B \circ_B f = f\)
• Right identity: \(f \circ_B 1B = f\)
• Associativity: \((f \circ_B g) \circ_B h = f \circ_B (g \circ_B h)\)

Then a functor defines lift to convert each component in the source category into a component of the destination category.

Covariant functor laws:

• lift must map \(\circ_A\) to \(\circ_B\) (composition law):
  • \(lift (f \circ_A g) = lift( f ) \circ_B lift( g )\)
• lift must map \(1_A\) to \(1_B\) (identity law):
  • \(lift (1_A) = lift(1_B)\)

Interesting insight:

In other words, functors serve as adapters between categories that promote code written for the source category to be automatically compatible with the destination category. Functors arise every time we write compatibility layers and adapters between different pieces of software.

Consider the category of lists along with list concatenation, where \(\circ = (++)\) and \(1 = []\); and the category of addition where \(\circ = (+)\) and \(1 = 0\).

length and concat are functors:

length (xs ++ ys) = length xs + length ys
length [] = 0
concat (x ++ y) = concat x ++ concat y
concat [] = []

The haskell Functor typeclass defines fmap, which works like lift and must satisfy the same laws.

Gabriel says that Functors make our code “automatically future proof” but I think it’s more appropriate to say “easily adaptable” (via fmap).

Monad morphisms

Say I want to use iteratees from iteratees and enumerator. Must define some function morph that transforms from one representation to the other:

NB. this is something crazy, specifically in code2. Love it.

import qualified Data.Enumerator as E
import qualified Data.Iteratee.Base as I

morph :: I.Iteratee a m b -> E.Iteratee a m b

But say that iteratee has sa faster Monad instance, so I want to use that whenever possible:

f :: a -> I.Iteratee s m b
g :: b -> I.Iteratee s m c
h :: c -> E.Iteratee s m d

-- Hypothetically slower, since it uses E.Iteratee's bind
code1 :: a -> E.Iteratee s m d
code1 a = do b <- morph $ f a
             c <- morph $ g b
             h c

-- Hypothetically faster, since it uses I.Iteratee's bind
code2 :: a -> E.Iteratee s m d
code2 a = do c <- morph $ do b <- f a
                             g b
             h c

Doing nothing should also translate, i.e. (morph $ return x = return x)

Rewrite in point-free style:

code1 = h <=< (morph . g) <=< (morph . f)
code2 = h <=< (morph . (g <=< f))
morph . return = return

lift = (morph .)
lift return = return

-- ie. (not in original post)
--   h <=< lift g <=< lift f
-- = h <=< lift (g <=< f)

So here we have a functor, but this time between Kleisli categories.

A monad morphism is a function of the form:

morph :: (Monad m, Monad n) => forall r . m r -> n r

such that lift = (morph .) defines a functor between two Kleisli categories. Monad morphisms are special cases of natural transformations.

Note: the monad transformer laws:

lift :: (Monad m, MonadTrans t) => m r -> t m r
(lift .) :: (Monad m, MonadTrans t) 
         => (a -> m b) -> (a -> t m b)
(lift .) return = return
(lift .) (f >=> g) = (lift .) f >=> (lift .) g

So monad transformers are a special subset of monad morphisms, and the monad transformer laws are just the functor laws! When using monad transformers, you are using a functor between the base monad’s Kleisli category and the transformed one’s Kleisli category.

This can be used anywhere you’re using categories to begin with; keep it in the back of your mind!

Discussion on reddit and some criticism of the article