Edward Kmett wrote:
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. [...] Now what I find interesting is that Yoneda is basically carrying around an accumulator for 'fmap' applications. [...] 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 (>>=).
Indeed an insightful perspective! Ryan Ingram wrote:
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
Ha! Nice damper. So the interesting part is not that one gets a monad for free but that one gets a monad for free that can be combined with effects defined elsewhere. That seems closely related to your MonadPrompt. Thanks for the pointer.
You may as well do the following:
data MPlus a = Zero | Pure a | Plus (MPlus a) (MPlus a) instance Monad MPlus where ... instance MonadPlus MPlus where ...
mkAlternative :: forall f a. Alternative f => (forall m. MonadPlus m => m a) -> f a
(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)
Well, you can use return, bind, mzero and mplus.. I'd consider this *really* monad. You are right, that your version is equivalent to the "generic" MonadPlus instance which (only) eliminates the intermediate data structure.
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 :)
I'm not sure which other effects can be lifted without bind and which need lift. But anyway, there is a lift function that can be used if necessary. Non-determinism is one interesting effect that does not need lift. The generic MonadPlus (ContT t) instance buys you a lot, if you are interested in non-determinism and search. Inspired by all your replies I have applied ContT to a type for difference lists which resulted in the well known two-continuation model for depth first search -- refactoring it modularly into two different parts that are useful on their own. Replacing one of those parts lead to a CPS implementation of breadth-first search that I have not been aware of previously. Please tell me if you have seen this implementation before. I have written about it: http://www-ps.informatik.uni-kiel.de/~sebf/haskell/stealing-bind.html
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 >>=. [...] I know this was a pretty in-depth example, so I hope I've made it clear :)
Yes, thanks! Cheers, Sebastian