Sebastian Fischer sebf at informatik.uni-kiel.de
Tue Apr 14 04:17:29 EDT 2009

```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
effects defined elsewhere. That seems closely related to your

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

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

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

```