Lambda the Ultimate

inactiveTopic Generalising Monads to Arrows
started 12/18/2002; 11:23:42 AM - last post 12/20/2002; 4:00:26 AM
Bryn Keller - Generalising Monads to Arrows  blueArrow
12/18/2002; 11:23:42 AM (reads: 1880, responses: 5)
Generalising Monads to Arrows
John Hughes, Generalising Monads to Arrows, in Science of Computer Programming 37, pp67-111, May 2000.

... The monad interface has been found to be suitable for many combinator libraries, and is now extensively used. Numerous benefits flow from from using a common interface ... It is therefore a matter of some concern when libraries emerge which cannot, for fundamental reasons, use the monad interface ... I sought a generalization of the monad concept that could also offer a standardised interface to libraries [that could not support a monadic interface]. My proposal, which I call arrows, is the subject of this paper. Pleasingly, the arrow interface turned out to be applicable to other kinds of non-monadic library also...

This paper introduces arrows, which are a generalization of monads. I mentioned this before when we were discussing the Fruit GUI toolkit (which uses arrows), but it really deserves a topic of its own. Full of motivating examples and thorough explanations.

Also, there are some other arrow resources:

Posted to theory by Bryn Keller on 12/18/02; 11:30:09 AM

Chris Clearwater - Re: Generalising Monads to Arrows  blueArrow
12/18/2002; 3:15:08 PM (reads: 884, responses: 3)
Does anyone know how arrows differ from continuation passing style ?

Frank Atanassow - Re: Generalising Monads to Arrows  blueArrow
12/19/2002; 8:02:26 AM (reads: 912, responses: 2)
You might first ask, "how do monads differ from CPS?" since they are quite close. Indeed, there is such a thing as a continuation monad. Given some type T of "answers", Cont is a monad:
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
So a value of type Cont a is a function which takes a continuation as its first argument. callcc passes to its argument f a function g which discards the current continuation and invokes the captured continuation k instead.

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.

Ehud Lamm - Re: Generalising Monads to Arrows  blueArrow
12/19/2002; 8:11:48 AM (reads: 914, responses: 0)
continuations become ADTs

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

Chris Clearwater - Re: Generalising Monads to Arrows  blueArrow
12/19/2002; 12:17:03 PM (reads: 924, responses: 0)
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?

Frank Atanassow - Re: Generalising Monads to Arrows  blueArrow
12/20/2002; 4:00:26 AM (reads: 797, responses: 0)
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.