ezyang’s blog

the arc of software bends towards understanding

Adventures in Three Monads

I've been busy at work over this winter break working on an article for The Monad Reader, entitled "Adventures in Three Monads." The material will overlap the second part of my IAP talk Haskell Typeclasses that I will be delivering under the auspices of SIPB IAP.

The article itself is a literate Haskell file, and contains sample code I've cribbed from the various Haskell applications I've written over my year long flirtations with the language: included is code and explanation for the probabilistic Turing machine I built in order to brute-force a 6.004 assignment. (To the course staff: the code is incomplete enough that it's not equivalent to publishing all of the solutions; intrepid readers will still have to write a search function themselves.)

I'll be keeping a pre-print of the article available in my public directory. Questions, comments and suggestions would be greatly appreciated!

17 Responses to “Adventures in Three Monads”

  1. T_S_ says:

    In the first example perhaps define:

    fromList = (msum . map return)

    to make Listing 1 more readable

  2. Ricardo Herrmann says:

    Hi, just to let you know your evensList example will actually return odds ;-)

    I have just skimmed it, but will read it as soon as I can. The logict paper is very good but maybe it scares some people away (as there’s only 1 package in hackage that depends on it (http://bifunctor.homelinux.net/~roel/cgi-bin/hackage-scripts/revdeps/logict-0.3#direct)), and maybe now more programmers will start using it after reading your article.

  3. Anonymous says:

    About a third of the way down on page 2: “If the type signature is speci ed to be [a], the original list operations fall out again.” Could you reword this? What type signature? What does “fall out again” mean?

    Bottom of page 10: “Note that they still are data constructors, so we can still use pattern matching, we can’t return any old value (it has to be of type GADTExample a), …”, but about a third of the way down on page 11: “As mentioned before, the return type need not be GADTExample a.” Looks like a contradiction.

    Listing 14: Where does “prompt” come from?

  4. Thanks for all of your comments! I’ve updated the article accordingly. Ricardo, very good catch. :-)

    Re Anonymous “If the type signature is speci ed to be [a], the original list operations fall out again.” The list monad is an instance of MonadPlus. So any operator on MonadPlus, say mplus or mzero, has a generic type, but if you (by inference or explicitly) narrow the type to the list, you’ll find that it is equivalent to whatever type-specific function it corresponds to. I’ve tried to make this a little clearer in the article.

  5. Ricardo Herrmann says:

    Hi, I thought you had already submitted the final version to TMR … in case not, how about using guards in Listing 1 to make it more idiomatic, since it mentions MonadPlus right after the example ? Just my 2 cents …

  6. I was thinking about that, and I decided to explicitly write out the if…then…else, because it showed use of mzero/return, rather than a sort of magical (to those who don’t quite understand its operation) guard operator. I guess it would be a good thing to mention, though.

  7. roy_hu says:

    On page 3, “A Turing machine a consists of a tape, …”

  8. roy_hu says:

    The state of the nondeterministic Turing Machine is defined as

    data State = StateA | StateB

    I was like, huh?

  9. roy_hu says:

    You defined choices in Listing 7. It’s a duplication of fromList from Listing 1.

  10. roy_hu says:

    On page 8, the sequence should be 0,1,0,2,0,1,0,3,0,1,0,2,(0,1,)0,4,0,…
    You missed the numbers between the parentheses.

  11. roy_hu says:

    The meaning of “faux monads” isn’t clear to me.

  12. Hey Roy,

    Thanks for the great comments! You should redownload the PDF, because I’ve made some updates (for example, I removed “faux monad” because both you and Brent Yorgey mentioned that it was confusing.)

  13. roy_hu says:

    On page 15, There *are* also Applicative and Functor versions, …

  14. roy_hu says:

    FYI, the page numbers in my comments correspond to the latest PDF. But I didn’t check “faux monad” in it.

  15. Excellent. I’ve updated the PDF accordingly with your comments.

  16. roy_hu says:

    Could you talk more about the Turing Machine’s state? I didn’t see any reference to the “StateA | StateB” thing.

    Also, I’m interested in “the ordering being sensitive to monad transformations”, although you deleted it. Could you talk more about it on your blog?

  17. roy_hu says:

    I’m honored to be placed in the acknowledgements. Could you put in my real name, Wei Hu?

Leave a Comment