On Wed, Apr 8, 2009 at 5:20 PM, Ben Franksen wrote:

Sebastian Fischer wrote:

...

 > {-# LANGUAGE Rank2Types #-}

Dear Haskellers,

I just realized that we get instances of `Monad` from pointed functors and instances of `MonadPlus` from alternative functors.

Is this folklore?

 > import Control.Monad  > import Control.Applicative

In fact, every unary type constructor gives rise to a monad by the continuation monad transformer.

 > newtype ContT t a = ContT { unContT :: forall r . (a -> t r) -> t r }  >  > instance Monad (ContT t)  >  where  >   return x = ContT ($x)  >   m >>= f  = ContT (\k -> unContT m (\x -> unContT (f x) k))

Both the `mtl` package and the `transformers` package use the same `Monad` instance for their `ContT` type but require `t` to be an instance of `Monad`. Why? [^1]

Maybe because this is needed to prove monad laws?

<snip derivation>

So, that wasn't the reason. It really is a monad.

In general, ContT r m a is equivalent to Cont (m r) a, and their corresponding Monad instances are also equivalent. But Cont r is a monad for any r, which implies that ContT r m must be a monad for any r and m. -- Dave Menendez http://www.eyrie.org/~zednenem/

On Thu, 2009-04-09 at 01:24 +0200, Ben Franksen wrote:

BTW, is this (ContT t) somehow related to the 'free monad' over t?

The free monad over t is just data FreeMonad t a = Return a | JoinLift (t (FreeMonad t a)) instance Functor t => Monad (FreeMonad t) where return = Return Return x >>= f = f x JoinLift a >>= f = JoinLift ((>>= f) <$> a) lift :: Functor t => t a -> FreeMonad t a lift a = JoinLift (return <$> a) So they're obviously different. Here's what free monads are for: picking a functor f so that FreeMonad f becomes a randomly chosen monad :), we could define data IOStmt a = GetChar (Char -> a) | PutChar Char a instance Functor IOStmt where fmap f (GetChar g) = GetChar (f . g) fmap f (PutChar ch x) = PutChar ch (f x) getCharStmt :: IOStmt Char getCharStmt = GetChar id putCharStmt :: Char -> IOStmt () putCharStmt ch = PutChar ch () type IO = FreeMonad IOStmt getChar :: IO Char getChar = lift getCharStmt putChar :: Char -> IO () putChar = lift . putCharStmt jcc

On Thu, Apr 9, 2009 at 2:22 AM, Sebastian Fischer wrote:

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`.

Sure, but you can also do the same much more simply: mkPointed :: Pointed f => forall f a. (forall m. Monad m => m a) -> f a mkPointed m = point $ runIdentity m

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.

My point was slightly more general; what I was saying was there is not a huge use for the "generic" MonadPlus using Alternative, because without "lift", you have a hard time embedding any other effects from the applicative into the continuation use. You may as well do the following:

data MPlus a = Zero | Pure a | Plus (MPlus a) (MPlus a) instance Monad MPlus where return = Pure Zero >>= k = Zero Pure a >>= k = k a Plus a b >>= k = Plus (a >>= k) (b >>= k) instance MonadPlus MPlus where mzero = Zero mplus = Plus

mkAlternative :: forall f a. Alternative f => (forall m. MonadPlus m => m a) -> f a mkAlternative m = convertPlus m where convertPlus :: forall b. MPlus b -> f b convertPlus Zero = empty convertPlus (Pure a) = pure a convertPlus (Plus a b) = convertPlus a <|> convertPlus b

(all this code is really saying is that being polymorphic over MonadPlus is kind of dumb, because you aren't really using Monad at all) Without any way to lift other effects from the underlying functor into ContT, I don't really see how the "generic" ContT MonadPlus instance buys you much :)

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?

Yes, because

runContT ( (lift (a >>= f)) >>= g ) still has a left-associative >>=.

Now of course that looks silly, but things aren't as simple as they seem; in particular I ran into this first when using Control.Monad.Prompt[1] (which is really just a sophisticated Cont monad with a nice interface)

data MPlus m a = Zero | Plus (m a) (m a)

instance MonadPlus (RecPrompt MPlus) where mzero = prompt Zero mplus x y = prompt (Plus x y)

runPlus :: forall a. RecPrompt MPlus r -> [r] runPlus = runPromptC ret prm . unRecPrompt where ret :: r -> [r] ret x = [x]

prm :: forall a. MPlus (RecPrompt MPlus) a -> (a -> [r]) -> [r] prm Zero k = [] prm (Plus a b) k = (runPlus a ++ runPlus b) >>= k -- this >>= is in the list monad

Now, consider runPlus ((mplus mzero (a >>= f)) >>= g), which uses the Plus "effect"; this will reduce to (runPlus (a >>= f)) >>= k where k is the continuation that runs g using "ret" and "prm" to convert to a list; the result still may have a left-associated >>= in it, depending on the value of "a" and "f". However, you're limited to at most one left associative bind per "recursive" lifted operation; the other binds will all be right-associative. I know this was a pretty in-depth example, so I hope I've made it clear :) -- ryan [1] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/MonadPrompt

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@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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe