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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
