[Haskell] Monads vs. continuations

[Cale Gibbard]

On 31/10/05, Gregory Woodhouse <gregory.woodhouse at 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