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:
    January 5, 2010 at 10:39 am

    In the first example perhaps define:

    fromList = (msum . map return)

    to make Listing 1 more readable

  2. Ricardo Herrmann says:
    January 5, 2010 at 11:30 am

    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:
    January 5, 2010 at 12:14 pm

    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. Edward Z. Yang says:
    January 5, 2010 at 12:57 pm

    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:
    January 5, 2010 at 3:09 pm

    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. Edward Z. Yang says:
    January 5, 2010 at 3:18 pm

    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:
    January 10, 2010 at 12:42 pm

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

  8. roy_hu says:
    January 10, 2010 at 4:18 pm

    The state of the nondeterministic Turing Machine is defined as

    data State = StateA | StateB

    I was like, huh?

  9. roy_hu says:
    January 10, 2010 at 4:20 pm

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

  10. roy_hu says:
    January 10, 2010 at 10:20 pm

    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:
    January 10, 2010 at 10:37 pm

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

  12. Edward Z. Yang says:
    January 10, 2010 at 10:43 pm

    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:
    January 10, 2010 at 11:34 pm

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

  14. roy_hu says:
    January 11, 2010 at 12:14 am

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

  15. Edward Z. Yang says:
    January 11, 2010 at 12:20 am

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

  16. roy_hu says:
    January 11, 2010 at 12:35 am

    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:
    January 11, 2010 at 12:42 am

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

Leave a Comment