Comments on A Neighborhood of Infinity: The Mother of all Monads

Secret Agent for the Dumb, >>= basically applies ...

2009-12-03T17:54:57.769-08:00

Secret Agent for the Dumb,

>>= basically applies a function to each element of a list, and then flattens the entire result. But I think you got that already.

you lost me a bit at "ex8". I think what I see is ...

2009-04-19T18:15:00.000-07:00

you lost me a bit at "ex8". I think what I see is that [10,20] >>= fred is a bind in the LIST monad, and not in the continuation monad, as is the final "return" in "runCont ex8 return." I think "fred" has type "x->[x]" so [10,20]>>=fred means 'bind [10,20] to x, build [[10,20]] and flatten one level, producing [10,20]", which, if memory serves, is what the >>= of the list monad does. Have I got it?

sigfpe/rory:As a sketch for how 'ContT is terminal...

2009-01-05T10:08:00.000-08:00

sigfpe/rory:

As a sketch for how 'ContT is terminal':

If you discard the information about the return value's type through quantification (using a forall, or less safely just using the current continuation in a 'very limited' manner) then you can view ContT as a right Kan extension of a functor F along itself. That can be viewed as a limit taken pointwise over a comma category - just invert the colimit example in the wikipedia article on Kan extensions to take a limit of Ran instead a colimit of Lan. That limit is a terminal object in a category of cones.

ContT is slightly larger than this, in that you CAN abuse the current continuation. That said, to define a codensity monad and lift/lower monadic actions into it as you have done, you do not use that extra functionality.

The fact that you can lift any monad into it (by CPS transformation) is just a consequence of the existence of the codensity monad, ContT is actually a bit bigger than it needs to be.

This is all just another way to say that a CPS transformation can always be applied.

And you can take away from this, somewhat tongue in cheek, that continuations are slightly more complicated than they need to be to do the job. ;)

Roly,> What does all this mean categorically?I had...

2009-01-02T18:02:01.502-08:00

Roly,

> What does all this mean categorically?

I had the same thought as you - Cont must be terminal or final in some category. But I haven't figured out what category that is.

Great post!>Many languages with support for contin...

2008-12-30T05:17:00.000-08:00

Great post!

>Many languages with support for continuations should be extensible to support monads
I'd phrase it a little differently: language with support of continuations automatically supports monads with natural syntax.
Perhaps it is worth to mention that one needs delimited control operators to simulate monadic do-notation (in case of Control.Monad.Cont the 'runCont' function is a control delimiter).

If you look in category-extras there is actually a...

2008-12-28T11:45:00.000-08:00

If you look in category-extras there is actually a monad that boxes up this functionality and reflects this idea; the "codensity monad," aka the monad generated by a functor basically represents a CPS transform.

http://hackage.haskell.org/packages/archive/category-extras/0.53.5/doc/html/src/Control-Monad-Codensity.html

Your run corresponds to my lowerCodensity and i corresponds to liftCodensity.

The rest just relies on the fact that:

newtype Codensity m a = Codensity { runCodensity :: forall b. (a -> m b) -> m b }

which can also be read as forall r. ContT (m r) a is a monad regardless of m, (it doesn't even have to be a functor!)

This monad has nice performance characteristics, because it just reflects a CPS transform of the code.

A variation on the presentation is available here:

http://www.haskell.org/haskellwiki/Performance/Monads

Since this represents a CPS transform of the code and is a monad in its own right if the bind operation of the monad is expensive, as in say most free monads, you can change the asymptotic behavior of code that is running in the monad.

Janis Voigtlaender has a paper on the topic, in which you'll recognize the type 'C' that he uses as the Codensity monad above.

http://wwwtcs.inf.tu-dresden.de/~voigt/mpc08.pdf

Moreover, if you are looking for a window to understanding Kan extensions, you can view the codensity monad as the right Kan extension of a functor along itself.

What does all this mean categorically? I haven't ...

2008-12-25T02:11:00.000-08:00

What does all this mean categorically? I haven't yet tried to understand what monad morphisms are (other than that they must be natural transformations that preserve the extra structure of a monad), but does the continuation monad turn out to be initial or terminal in a suitable category?

I wrote a monads module in scheme few years ago. ...

2008-12-25T01:22:00.000-08:00

I wrote a monads module in scheme few years ago. I wanted to use it for all monads, but Scheme had no namespace or type class. Therefore, the only way is extract the core part of monads (the mother of all monads). This is the major code:

(define bind
(lambda (a b)
(lambda (k)
(a (lambda v ((apply b v) k))))))

(define return
(lambda v
(lambda (k)
(apply k v))))

(define run-IO
(lambda (m)
(m values)))

(define run-State
(lambda (m . s)
(apply (m (lambda r (lambda _ (apply values r)))) s)))

(define State-set
(lambda v
(lambda (k)
(lambda s
(apply (apply k s) v)))))

(define return-List
(lambda l
(lambda (k)
(apply append (map k l)))))

(define run-List
(lambda (m)
(m list)))

I didn't know it is correct or not. After I read you post, I understand I've acturally written a Cont monad and work out other monads with it, same as what you did. You solved my long time question!

AliPang: If you're on Gentoo (or perhaps some othe...

2008-12-24T19:17:00.000-08:00

AliPang: If you're on Gentoo (or perhaps some other *nix with a conservative package manager), you may have to install dev-haskell/mtl (or your *nix's equivalent package name), since GHC does not pull it in as a dependency. Be forewarned, if you are indeed using Gentoo, it may take awhile to compile.

AliPang,Try copying this entire post into a file c...

2008-12-24T17:50:00.073-08:00

AliPang,

Try copying this entire post into a file called test.lhs and running that in ghci. If that doesn't work, I wonder if you're missing some libraries. (I only know about ghc.)

I wanted to learn more about continuations for a w...

2008-12-24T17:36:00.000-08:00

I wanted to learn more about continuations for a while. But how do you get Haskell to recognize Control.Monad.Cont? I get a "Could not find module" error when I try to use it.

(And, no, I couldn't find anything useful through Google, though I will happily accept a "Let me google that for you" link :P)

Ah, I missed the total cleverness of i. Thanks!

2008-12-24T17:18:00.000-08:00

Ah, I missed the total cleverness of i. Thanks!

Anonymous,fred is the same in ex2 and ex3. In both...

2008-12-24T17:08:52.945-08:00

Anonymous,

fred is the same in ex2 and ex3. In both cases it's equal to "show . (+1)".

Inside "<- Cont (\fred -> ...)" fred is the function that does everything up to and including the last argument to the surrounding runCont, which in this case is "show". The stuff in the do-block just adds 1.

Of course in ex3 fred isn't actually used.

You can use the identity id instead of show if you don't want to do anything in particular to the result.

augustss,You expecting some kind of failure for st...

2008-12-24T17:00:15.455-08:00

augustss,

You expecting some kind of failure for state? The code is agnostic about the choice of monad so it'll work for any monad, right?

(runState $ run $ do { a <- i $ get ; i $ modify (+1) ; i $ return a }) 10

I noticed that you don't simulate the state monad....

2008-12-24T14:27:00.000-08:00

I noticed that you don't simulate the state monad. :)

I'm a little confused by ex3. What exactly is fre...

2008-12-24T14:13:00.000-08:00

I'm a little confused by ex3. What exactly is fred in this example? The partially applied function '(+) a' i.e. '(+) 1'?