On Wed, Apr 8, 2009 at 11:22 AM, Sebastian Fischer
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]
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! 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. The CPS transfrom in ContT also has the nice property that it makes most applications of >>= in the underlying monad be right-associative. This is important for efficiency for some monads; especially free monads; the free monad discussed by jcc has an O(n^2) running cost for n left-associative applications of >>=. -- ryan