Monads vs. continuations
Newbie alert: I have some superficial familiarity with continuations as they occur in traditional denotational semantics, but certainly not a deep understanding. I also have a special interest in distributed and/or concurrent processing, so it only seemed natural to me that the monad concept was one I'd want to confront head on. Now, I warn you: I am quite new to Haskell (though I have some prior exposure to Scheme and a background in mathematics). Now, I've just started reading through Thompson's text and came across this example: goUntilEmpty :: IO () goUntilEmpty = do line <- getLine if (line == []) then return () else (do putStrLn line goUntilEmpty) Okay, this seems sensible enough. Loosely speaking, I see this code as getting a line, checking to see if it's empty. If it is, it just quits (returning the "empty" value). Otherwise, it prints line, and invokes itself through a *new* do statement. That seems awfully like using a continuation to track the input stream as part of the environment. But it seems obvious to me that here is something I'm not understanding here. I think of the do as providing an appropriate continuation (one in which the line just read is gone) to pass to the next call. Okay, maybe I'm taking things a bit too literally here, but I seem to recall that a monad is an algebraic object with right and left identity and an associative composition. I understand the monad here takes a value (()) and returns an object IO (), and do becomes a functor of sorts, taking ordinary functions and mapping them to new functions having their codomain in a new category (an instance of a monad?) This is where it seems to me that I must be getting the terminology wrong. Can someone help me out here? === Gregory Woodhouse gregory.woodhouse@sbcglobal.net "The most incomprehensible thing about the world is that it is at all comprehensible." --Albert Einstein (1879-1955)
On 31/10/05, Gregory Woodhouse <gregory.woodhouse@sbcglobal.net> wrote:
Newbie alert:
I have some superficial familiarity with continuations as they occur in traditional denotational semantics, but certainly not a deep understanding. I also have a special interest in distributed and/or concurrent processing, so it only seemed natural to me that the monad concept was one I'd want to confront head on. Now, I warn you: I am quite new to Haskell (though I have some prior exposure to Scheme and a background in mathematics). Now, I've just started reading through Thompson's text and came across this example:
goUntilEmpty :: IO () goUntilEmpty = do line <- getLine if (line == []) then return () else (do putStrLn line goUntilEmpty)
Okay, this seems sensible enough. Loosely speaking, I see this code as getting a line, checking to see if it's empty. If it is, it just quits (returning the "empty" value). Otherwise, it prints line, and invokes itself through a *new* do statement. That seems awfully like using a continuation to track the input stream as part of the environment. But it seems obvious to me that here is something I'm not understanding here. I think of the do as providing an appropriate continuation (one in which the line just read is gone) to pass to the next call.
Okay, maybe I'm taking things a bit too literally here, but I seem to recall that a monad is an algebraic object with right and left identity and an associative composition. I understand the monad here takes a value (()) and returns an object IO (), and do becomes a functor of sorts, taking ordinary functions and mapping them to new functions having their codomain in a new category (an instance of a monad?) This is where it seems to me that I must be getting the terminology wrong. Can someone help me out here?
Perhaps you're referring to a monoid. Since you seem to have some familiarity with category theory, check out http://en.wikipedia.org/wiki/Monad_%28category_theory%29 for a formal definition of monads and some background. Translating between notation, μ = join and η = return in Haskell. The application of the functor T to functions is called fmap, or liftM, which should always be equivalent. The functor behind a monad is always an endofunctor, that is, from the category to itself. In this case, you'll be interested in the category of Haskell types and Haskell-definable functions between them. For a much gentler description and one way in which monads relate to programming, check out http://www.haskell.org/hawiki/MonadsAsContainers which is an article that I wrote. For a different perspective on the programming aspects than presented by my article (both are important in practice) check out http://www.nomaware.com/monads/html/ Do notation is a shorthand for a bunch of algebraic operations which make the code look like imperative code. Desugaring goUntilEmpty results in something along the lines of: goUntilEmpty :: IO () goUntilEmpty = getLine >>= \line -> if line == [] -- better written as "null line" then return () else putStrLn line >>= \x -> goUntilEmpty where x >>= f = join (fmap f x), to write it in terms of the operations defined on wikipedia. Hope these links are useful to you :) - Cale
On Oct 31, 2005, at 3:02 AM, Cale Gibbard wrote:
Perhaps you're referring to a monoid. Since you seem to have some familiarity with category theory, check out http://en.wikipedia.org/wiki/Monad_%28category_theory%29 for a formal definition of monads and some background. Translating between notation, μ = join and η = return in Haskell. The application of the functor T to functions is called fmap, or liftM, which should always be equivalent.
The functor behind a monad is always an endofunctor, that is, from the category to itself. In this case, you'll be interested in the category of Haskell types and Haskell-definable functions between them.
This was actually quite helpful. If someone had told me that a monad was a functor in the first place, this would all have been much less mysterious. (BTW, I have indeed encountered adjoint functors, Hom and Tensor, in the context of algebraic topology, so the article did leave me with a bit more of a sense of having my feet on the ground.)
For a much gentler description and one way in which monads relate to programming, check out http://www.haskell.org/hawiki/MonadsAsContainers which is an article that I wrote.
This is an excellent article! I found it extremely useful and lucid. To be sure, it's going to take a bit more time to let all these ideas sink in, but I liked the approach of focusing on fmap and join (>>= always seemed mysterious). Believe it or not, though I've read that lists are monads, this is perhaps the first time I've seen it spelled out just how. === Gregory Woodhouse gregory.woodhouse@sbcglobal.net "It is foolish to answer a question that you do not understand." --G. Polya ("How to Solve It")
I don't know if this helps, but there's a straightforward way to understand the IO monad in terms of continuation passing. You can think of a value of type IO a as being a CPS expression with a hole in it; the hole is to be filled with a continuation which expects a value of type a. The only way to fill the hole is by using >>=, whose second argument is a continuation with another (nested) hole in it. So effectively with >>= you build a CPS expression from the outside in. The final continuation, which takes () and aborts the program, is ultimately filled in by the runtime system. This viewpoint doesn't work for other monads, since they always provide some sort of destructuring operations on monadic values, e.g. runState or the standard list deconstructors. But it works fine for IO provided you ignore the existence of unsafePerformIO and friends. -- Ben
On Oct 31, 2005, at 9:37 AM, Ben Rudiak-Gould wrote:
I don't know if this helps, but there's a straightforward way to understand the IO monad in terms of continuation passing.
You can think of a value of type IO a as being a CPS expression with a hole in it; the hole is to be filled with a continuation which expects a value of type a. The only way to fill the hole is by using >>=, whose second argument is a continuation with another (nested) hole in it. So effectively with >>= you build a CPS expression from the outside in. The final continuation, which takes () and aborts the program, is ultimately filled in by the runtime system.
This viewpoint doesn't work for other monads, since they always provide some sort of destructuring operations on monadic values, e.g. runState or the standard list deconstructors. But it works fine for IO provided you ignore the existence of unsafePerformIO and friends.
-- Ben
No, that's definitely helpful. The analogy in the case of IO was obvious, but I had a sense that it was getting in the way of understanding what a monad is (i.e., by leading me to focus on the wrong issues). === Gregory Woodhouse gregory.woodhouse@sbcglobal.net "One must act on what has not yet happened." --Lao Tzu
Gregory Woodhouse <gregory.woodhouse@sbcglobal.net> wrote in article <A7137C2A-EE7E-48E9-82F8-6CB87AF8E780@sbcglobal.net> in gmane.comp.lang.haskell.general:
Okay, this seems sensible enough. Loosely speaking, I see this code as getting a line, checking to see if it's empty. If it is, it just quits (returning the "empty" value). Otherwise, it prints line, and invokes itself through a *new* do statement. That seems awfully like using a continuation to track the input stream as part of the environment. But it seems obvious to me that here is something I'm not understanding here. I think of the do as providing an appropriate continuation (one in which the line just read is gone) to pass to the next call.
Given your understanding of continuations, it may be more appropriate for you to think in terms of not "do" but the underlying combinations of "return" and ">>=" that "do" is syntactic sugar for. It may also help to consider monads other than IO, for example the input and output monads described in Section 7.3 of Philip Wadler's article "Comprehending Monads". I suspect that your understanding described in the paragraph above is essentially correct. You can also find more information on the relation between continuations and monads in: - Section 7.4 of "Combinations Monads", - Andrzej Filinski's articles "Representing Monads" and "Representing Layered Monads", and his dissertation "Controlling Effects", - Philip Wadler's article "Monads and Composable Continuations", - Section 3.2 of Philip Wadler's article "How to Declare an Imperative". -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 2005-11-06 Against Exploiting the Environment in War http://tinyurl.com/adhg9 2005-11-20 Universal Children's Day http://www.un.org/depts/dhl/children_day/ 2005-11-25 Elimination of Violence Against Women http://tinyurl.com/drd57 2005-11-25 Buy Nothing Day http://www.buynothingday.co.uk/
participants (4)
-
Ben Rudiak-Gould -
Cale Gibbard -
Chung-chieh Shan -
Gregory Woodhouse