[Haskell-cafe] Monads from Functors
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
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
More information about the Haskell-Cafe
mailing list