[Haskell-cafe] Monads from Functors

[Sebastian Fischer]

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