ezyang's blog

the arc of software bends towards understanding

Adventures in Three Monads

January 1, 2010

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 Comments

  1. T_S_

    In the first example perhaps define:

    fromList = (msum . map return)

    to make Listing 1 more readable

  2. Ricardo Herrmann

    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

    About a third of the way down on page 2: “If the type signature is specied 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

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

    Re Anonymous “If the type signature is specied 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
    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
    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
    On page 3, “A Turing machine a consists of a tape, …” ^
  8. roy_hu

    The state of the nondeterministic Turing Machine is defined as

    data State = StateA | StateB

    I was like, huh?

  9. roy_hu
    You defined choices in Listing 7. It’s a duplication of fromList from Listing 1.
  10. roy_hu
    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
    The meaning of “faux monads” isn’t clear to me.
  12. Edward Z. Yang

    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
    On page 15, There are also Applicative and Functor versions, …
  14. roy_hu
    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
    Excellent. I’ve updated the PDF accordingly with your comments.
  16. roy_hu

    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
    I’m honored to be placed in the acknowledgements. Could you put in my real name, Wei Hu?