[Haskell-cafe] Monads from Functors

[Edward Kmett]

I think there is another way to view the ContT/Codensity/Monad generated by
a functor, in terms of an accumulating parameter that may be informative. I
kind of alluded to it in the post on Kan extensions.

Take for a moment, Yoneda f given in:

http://comonad.com/haskell/category-extras/src/Control/Functor/Yoneda.hs

> newtype Yoneda f a = Yoneda { runYoneda :: forall b. (a -> b) -> f b }

You can readily construct an instance of Functor for Yoneda without any
concern for the underlying instance on f.

> instance Functor (Yoneda f) where
>     fmap f m = Yoneda (\k -> runYoneda m (k . f))

> lowerYoneda :: Yoneda f a -> f a
> lowerYoneda m = runYoneda m id

Basically the operation of creating a value of type Yoneda f a requires you
to use the fmap for the functor, so there is a Mendler-style encoding going
on here, no magic dictionaries are required to use the resulting value.
Now what I find interesting is that Yoneda is basically carrying around an
accumulator for 'fmap' applications.

Basically it enforces the fusion rule that fmap f . fmap g = fmap (f . g) by
accumulating mappings and applying them in one go when you ask for the
result.

As an aside, when you extract a value out of (Yoneda f) uses the function it
has accumulated so far, from pushing computations. And it has to use the
secret valid version of fmap that you had to know to find a function that
had the signature (forall a. (a -> b) -> f b) so no work is saved, its just
fmap fusion.

When you make a Monad out of Yoneda, that Monad can 'push' the map along to
the next bind operation so it can come along for the ride, avoiding the need
for an extra (>>=) to liftM the function you want to map. (It still has to
appeal to the secret fmap you knew to make the Yoneda f a value!) Of course,
this steps outside of the principles I'm espousing in this post by using a
dictionary.

> instance Monad f => Monad (Yoneda f) where
>   return a = Yoneda (\f -> return (f a))
>   m >>= k = Yoneda (\f -> runYoneda m id >>= \a -> runYoneda (k a) f)

When you look at the definition for Codensity f a, what it effectively
supplies is a 'better accumulator', one which is large enough to encode
(>>=).

> newtype Codensity m a = Codensity { runCodensity :: forall b. (a -> m b)
-> m b }

> instance Monad (Codensity f) where
>   return x = Codensity (\k -> k x)
>   m >>= k = Codensity (\c -> runCodensity m (\a -> runCodensity (k a) c))

You then have to pass it a function of the type (a -> m b) to get the value
out. Effectively you tell it how to return by injecting something. And since
it can return and bind, you can define liftM thanks to the monad laws,
giving an admissable implementation of Functor:

 > instance Functor (Codensity k) where
>   fmap f m = Codensity (\k -> runCodensity m (k . f))

Again no dictionaries were harmed in the encoding of this function and the
type is no bigger than it needs to be to express these properties.

The Codensity monad above can be seen as just an instance of enforced bind
fusion, enforcing choice of association of (>>=). This consequence
is logical because the result of a CPS transform is invariant under choice
of reduction order.

The reason I mention this is that this scenario is just an instance of
a very general pattern of Mendler-style encoding. I have another example of
Mendler-style encoding, this time for recursion schemes near the bottom of:
http://knol.google.com/k/edward-kmett/catamorphisms/

I find this idiom to be rather effective when I want to enforce the
equivalent of a rewrite rule or law about a type or work around the
requirement that there can be only one instance of a particular typeclass.
Yoneda doesn't care that f implements Functor, only that it satisfies the
properties of a functor, and that fmap _could_ be defined for it. Codensity
doesn't care that f is a monad. Well, it does if you want to do any
computations with f, but you could have several different lifts to different
monad/applicative 'instances' over f, as long as you lift into the codensity
monad with a bind operation and lower back out with a return operation that
agree. The dictionary for Monad m is irrelevant to the construction of
Codensity m.

> liftCodensity :: Monad m => m a ->  Codensity m a
> liftCodensity m = Codensity (m >>=)

> lowerCodensity :: Monad m => Codensity m a -> m a
> lowerCodensity a = runCodensity a return

-Edward Kmett


On Thu, Apr 9, 2009 at 5:22 AM, Sebastian Fischer <
sebf at informatik.uni-kiel.de> wrote:

> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090409/3bf0f604/attachment.htm