Lambda the Ultimate

type Cont a = (a -> T) -> T
return v = k -> k v
m >>= f = k -> m (v -> f v k)
callcc :: ((a -> Cont b) -> Cont a) -> Cont a
callcc f = k -> let g a = _ -> k a in f g k

This monad is maybe in a sense the "most powerful" monad, because once you have first-class continuations you can simulate everything else provided you pick a suitable answer type T. What monads let you do is less powerful things, that is, you don't have to go all the way to an extreme. The upshot is that you can expect better performance from your code.

See the following paper for more detail. He actually discusses monads vs. CPS.

Philip Wadler. The essence of functional programming. Invited talk, 19'th Symposium on Principles of Programming Languages, ACM Press, Albuquerque, January 1992.

As for arrows, you could say they are to monads as monads are to CPS. By defining different sorts of arrows, you can do less powerful things than monads do, and hence expect better performance and more optimization opportunities.

Maybe one way to regard the arrow paradigm is as "reified continuation passing-style", because the continuations become ADTs, so you can look into and examine them. (If you've read Friedman, Wand and Haynes' "Essentials of Programming Languages" (1st edition), this is sort of what they do in section 10.3, where they transform a CPS interpreter into a stack interpreter by representing continuations as data structures.) You can't do that with monadic values because the second argument of >>= is a function, and those are opaque. (Indeed, this is basically what motivated the introduction of arrows, I think.) And you certainly can't do it with CPS because _everything_ becomes a function.

Amusingly enough, my students were just given an exercise in which they have to take the CPS version of fact, and implement the continuations as ADTs (well, to make it more fun they have to use objects, and define an abstract class Cont).

Thanks, your response has been very helpful. However can't you treat a closure as an ADT or does haskell not allow that type of introspection?

I'm not sure exactly what you mean. Are you asking if function types are definable as Haskell datatypes? The answer is basically no, although you can define a datatype of lambda terms if you are willing to put up with de Bruijn notation and some difficulties with polymorphic recursion.

In Charity, though, higher-order function types are definable as "hidden" coalgebraic datatypes. In fact, HOF types are just the non-recursive special case, like sums and products are the non-recursive special cases for algebraic and coalgebraic datatypes. The more general recursive case is something like an object in OO terms, or a process: there is some internal state which is hidden and gets updated in each recursive step.

Anyway, Haskell does not support any introspection. You can't, for example, construct a function and examine the value of some binding in the closure.