[Haskell-cafe] Monads from Functors

[Sebastian Fischer]

Hi all,

thanks for pointing me at the Codensity monad and for mentioning the
lift operation! I'll try to sum up what I learned from this thread.

In short:

What I find interesting is

   1. you can express the results of monadic computations using
      functors that do not themselves support the `>>=` operation. You
      only need an equivalent of `return`.

and

   2. a variety of *non-*monadic effects (e.g., non-determinism) can be
      lifted to this "monad for free", so you get, e.g., a
      non-determinism *monad* even if all you have is a non-determinism
      *functor*.

Here is the long version:

Because `ContT` makes a monad out of anything with kind `* -> *`, we
also get instances for `Functor` and `Applicative` for free. We could
use the `Monad` instance to get them for free by
`Control.Applicative.WrappedMonad` but defining them from scratch
might be insightful, so let's try.

We could define an instance of `Functor` for `ContT t` as follows.

     instance Functor (ContT t)
      where
       fmap = liftM

But let's see what we get if we inline this definition:

     fmap f a
   = liftM f a
   = a >>= return . f
   = ContT (\k -> unContT a (\x -> unContT (return (f x)) k))
   = ContT (\k -> unContT a (\x -> unContT (ContT ($f x)) k))
   = ContT (\k -> unContT a (\x -> k (f x)))

That leads to the `Functor` instance described in the first post on
Kan extensions by Edward Kmett.

 > instance Functor (ContT t)
 >  where
 >   fmap f a = ContT (\k -> unContT a (k.f))

We also get an Applicative instance for free:

     instance Applicative (ContT t)
      where
       pure  = return
       (<*>) = ap

If we inline `ap` we get

     f <*> a
   = f `ap` a
   = f >>= \g -> a >>= \x -> return (g x)
   = ContT (\k1 -> unContT f (\x1 -> unContT (a >>= \x -> return (x1  
x)) k1))
   = ...
   = ContT (\k -> unContT f (\g -> unContT a (\x -> k (g x))))

So, a direct Applicative` instance would be:

 > instance Applicative (ContT t)
 >  where
 >   pure x  = ContT ($x)
 >   f <*> a = ContT (\k -> unContT f (\g -> unContT a (\x -> k (g x))))

The more interesting bits are conversions between the original and the
lifted types. As mentioned earlier, if `f` is a pointed functor, then
we can convert values of type `ContT f a` to values of type `f a`.

     runContT :: Pointed f => ContT f a -> f a
     runContT a = unContT a point

Ryan Ingram pointed in the other direction:

  > You are missing one important piece of the puzzle for ContT:
  >
  > ~~~
  > lift :: Monad m => m a -> ContT m a
  > lift m = ContT $ \k -> m >>= k
  > ~~~
  >
  > This >>= is the bind from the underlying monad.  Without this
  > operation, it's not very useful as a transformer!

That is a fine reason for the *class* declaration of `MonadTrans` to
mention `Monad m` as a constraint for `lift`. But as `ContT t` is a
monad for any `t :: * -> *`, a constraint `Monad t` on the *instance*
declaration for `Monad (ContT t)` is moot. This constraint is not
necessary to define `lift`.

 > instance MonadTrans ContT
 >  where
 >   lift m = ContT (m>>=)

Ryan continues:

  > Without lift, it's quite difficult to get effects from the
  > underlying Applicative *into* ContT.  Similarily, your MonadPlus
  > instance would be just as good replacing with the "free"
  > alternative functor:
  >
  > ~~~
  > data MPlus a = Zero | Pure a | Plus (MPlus a) (MPlus a)
  > ~~~
  >
  > and then transforming MPlus into the desired type after runContT;
  > it's the embedding of effects via lift that makes ContT useful.

Let's see whether I got your point here. If we have a computation

     a :: Monad m => m a

and we have a pointed functor `f`, then we can get the result of the
computation `a` in our functor `f` because `runContT a :: f a`.

If we now have a computation with additional monadic effects (I use
non-determinism as a specific effect, but Edward Kmett shows in his
second post on Kan extensions how to lift other effects like Reader,
State, and IO)

     b :: MonadPlus m => m b

then we have two possibilities to express the result using `f` if `f` is
also an alternative functor.

   1. If `f` is itself a monad (i.e. an instance of MonadPlus), then
      the expression `runContT (lift b)` has type `f b`. (Well, `b`
      itself has type `f b`..)

   2. If `f` is *not* a monad, we can still get the result of `b` in
      our functor `f` (using the `MonadPlus` instance from my previous
      mail), because `runContT b` also has type `f b`.

Clearly, `runContT (lift b)` (or `b` itself) and `runContT b` may
behave differently (even if they both (can) have the type `f b`)
because `ContT` 'overwrites' the definition for `>>=` of `f` if `f`
has one. So it depends on the application which of those behaviours is
desired.

Ryan:

  > The CPS transfrom in ContT also has the nice property that it makes
  > most applications of >>= in the underlying monad be
  > right-associative.

Do you have a specific reason to say *most* (rather than *all*) here?
Because if we have a left-associative application of `>>=` in `ContT`,
then we have:

     (a >>= f) >>= g
   = ContT (\k1 -> unContT (a >>= f) (\x1 -> unContT (g x1) k1))
   = ContT (\k1 ->
       unContT (ContT (\k2 -> unContT a (\x2 -> unContT (f x2) k2)))
               (\x1 -> unContT (g x1) k1)
   = ContT (\k1 -> unContT a (\x2 -> unContT (f x2) (\x1 -> unContT (g  
x1) k1)))
   = ContT (\k1 -> unContT a (\x2 ->
       unContT (ContT (\k2 -> unContT (f x2) (\x1 -> unContT (g x1)  
k2)))
               k1))
   = ContT (\k1 -> unContT a (\x2 -> unContT (f x2 >>= g) k1))
   = a >>= (\x -> f x >>= g)

Cheers,
Sebastian