Tue Aug 16 14:47:50 CEST 2011

Kleisli arrows

According to Dan Piponi, Kleisli arrows and their composition are the
whole point of monads[1].  Dan's explanation is something like the

If you want to chain (a -> M b) and (b -> M c), a straightforward but
wrong thing to do is to use a function (M b -> b) that throws away all
the extras.  However, because M is a functor it is always possible to
use fmap :: (a -> b) -> (M a -> M b) to convert (b -> M c) to (M b ->
M (M c)) which composes nicely with (a -> M b).  The result of this is
that we end up with a double wrapping.  Therefore a monad needs to
have a function join :: M (M a) -> M a that restores the output of
this chain to something that can be chained again.  Summarized:

  (>=>) :: (Functor m, Monad m) =>
           (a -> m b) -> (b -> m c) -> (a -> m c)
  (>=>) f g = f .> (fmap g) .> join
    where (.>) = flip (.)

So how does this relate to the usual do notation?

    a <- ma
    b <- mb
    return $ a + b

or explicitly

  ma >>= \a ->
  mb >>= \b ->
  return $ a + b

This is not simply chaining of arrows.  The nesting here makes the
arrows somewhat special.  They are all arrows that go from some type
to the result type of the do expression.  The focus here is on the
result of the expression, i.e. monadic values (M a) instead of arrows
(a -> M b).

Maybe the following makes sense: using (>=>) is pointfree or
function-oriented programming, while using (>>=) or do is applicative
or value-oriented programming.

Anyways, in this light, comonads are straightforward to grasp, and as
Dan mentions, it's not clear if there is a "codo" because comonads
don't map well to the idea of binding structure.

[1] http://blog.sigfpe.com/2006/06/monads-kleisli-arrows-comonads-and.html
[2] http://en.wikipedia.org/wiki/Kleisli_category
[3] http://www.haskell.org/haskellwiki/Arrow_tutorial#Kleisli_Arrows