Monads in Python (with nice syntax) | Hacker News Reader

Monads in Python (with nice syntax)

valuedlessons.com

92 pointsllambda48 comments

This approach to the "do" syntax requires that the function implementer know the monad type a priori.

That defeats some of the purpose of monad as general abstraction. One of the big ideas here, as far as I'm concerned, is that monads represent an abstraction over a common structure of programs. Lists, Maybes, threading models, etc, all share this same language of structuring computations. This is significant because it means that one can build functions which manipulate those structures, and then those structures can be deployed generically. Depending on how you're counting, that means third-order abstraction.

For instance, consider liftM from Control.Monad:

  -- | Promote a function to a monad.
  liftM   :: (Monad m) => (a1 -> r) -> m a1 -> m r
  liftM f m1              = do { x1 <- m1; return (f x1) }

This represents a common idea across e.g. both List and Maybe. I've got a function of values. I want to turn it into a function of Lists / Maybes. Well, liftM recognizes the similarity of List's and Maybe's structure and provides a single implementation suitable for both places.

The decorator described in this article cannot function at liftM's level of abstraction: at least as far as I can tell (as a non-Python programmer), it requires a monad type parameter. If that's true, I think it's missing a key idea behind the power of monads.

Not really. Python doesnt have typeclasses so liftM would be a fucntion receiving the monad dictionary as an explicit parameter. At that point, you can pass that dictionary to the decorator:

    def liftM(m, f, x):
        @do(m)
        def doNotationBody():
           ...
        ...

Can anyone explain to me how the continuation Monad is working there? As far as I know there's no way to return from the same yield twice, which is what a callcc would need to do. I'm going to carry on trying to puzzle it out but a pointer would be helpful!

EDIT: I just tried out the code and it doesn't support multiple returns. Isn't that pretty much the thing that defines the Continuation Monad or am I just not getting it?

Technically, it is still a continuation, even if it does not match the behavior of Haskell's continuation monad.

http://c2.com/cgi/wiki?SingleUseContinuation

I didn't know that, thanks. Seems less useful though.

What's the correct term for a continuation as I understand them? (eg: as they are in Haskell, Ruby, Scheme etc)

Continuations that are not single use are usually called multi-shot continuations.

Single shot continuations are very useful though. They are enough for a very large percentage of the situations you would use continuations for while being much more efficient to implement (no need to save the stack)while also being more reasonable theretically in other situations(call/cc can be used to break some important invariants when it interacts with mutablestate and other things like that. Its kind of subtle)

This is missing the one thing that all other "let me explain monads to you" articles is missing: a real example of what problems monads solve. As far as I know, a monad is some kind of mathematical construct that is very useful when solving mathematical proofs, but has no use for the every day programmer. The examples in these kinds of articles are always completely abstract. You can very easily describe a database by using the "customer/phone number" example, yet I've never seen such an example with monads.

http://www.haskell.org/haskellwiki/Monad#Interesting_monads

Nothing to do with proofs.

Monads are a generic interface -- an API -- for changing up the computational rules of your programming language.

Just think about that for a second -- its a big deal.

Maybe you want to work with non-deterministic threads, or with continuations, or quantum computations, or backtracking search, or exceptions or partial results, or some other notion of computation. But you want to still write in your usual language.

So you embed that computational style as a monad, and now you have a really nice API for programming in that different environment -- inside your everyday language.

Its simple, but profound. With (good support for) monads you aren't constrained to the default computational rules of your programming language anymore.

You are free.

The problem with this description is that I don't know what kind of benefits I can get from using different computational rules... Can you show me?

dons' explanation will be better/more rigorous than mine, but in a more familiar syntax (Python), let's say you've got some functions:

    def get_user(id):
        # returns None if no such user exists
        return Database.Users.get(id)

    def send_message(user):
        user.send(message)

    def main():
        user = get_user(1)
        # uhoh -- this could be None and we didn't handle it!
        send_message(user)

So, we add a None check:

    def main():
        user = get_user(1)
        if user != None:
            send_message(user)

But... what if we want to log the status of that send_message call?

    def send_message(user):
        try:
            user.send(message)
            return None
        except Exception, e:
            return "Failed to send message; {0}".format(e)

(Note that this is a contrived example, please don't critique the general dumbness ;)).

Now...

    def main()
        user = get_user(1)
        if user != None:
            response = send_message(user)
            if response != None:
                log(response)

As you can see, it's getting a bit hairy. But, what if we had a class that dealt with the Nones for us? This is what a monad is: an interface, that many different instances implement, which provides some behavior. The following only deals with single-argument functions, but:

    def NoneMonad(Monad):
        def __init__(self, arg):
            self.arg = arg

        def bind(self, func):
            if arg != None:
                next_arg = func(arg)
                return NoneMonad(next_arg)
            else:
                return NoneMonad(None)

Now, we...

    def main(self):
        NoneMonad(1).bind(get_user)
                    .bind(send_message)
                    .bind(log)

And, boom, the Nones are handled. Real, non-contrived Monads do more (and implement other behaviours -- like in dons' example, the Either response, or the Maybe monad, etc.), but hopefully this demonstrates the strength. Haskell's typically used as the example language, because there's syntax sugar in Haskell for making dealing with Monads prettier :).

Having finally grokked them, it surprised me how simple the concept is. I think for people (like me!) coming from Java, Python, etc. who've not had to deal with the concept, there's this sort of imbued myth that they're a much more difficult concept than they really are. It's as simple as: a Monad is an interface, that can be implemented, that provides a construct for executing code in.

Please forgive any blinding mistakes I've made in my code.

You made a few python mistakes but that explained the basic concept much better than what dons wrote.

He once again tries to explain monads using terminology that only people who already understand them can follow.

Hmm... That's bad. What terminology was difficult?

Well, the meaning of >>= is impossible to grok in this context because the meaning of "bind" isn't clear. In fact, most of the Monad interface (bind, lift, etc.) is pretty unclear to most people because, I think, it doesn't map onto other languages' concepts.

In fact, I might say that the worst possible way to explain Monads to someone unfamiliar with the subject is to use Haskell's monadic syntax.

Ugh, this made more sense than anything else I've ever read about monads. This, together with the Wikipedia sentence that monads are "programmable semicolons", helped me finally understand what they actually are.

Like the other commenters said, I don't understand why someone would use Haskell syntax to explain monads. If you know Haskell, you already know what monads are!

Thanks for this great example.

I think it's always worth studying Free monads to understand them a bit more completely. After you can see how to construct and map free monads then there's not much left to the concept to debate.

You can learn enough Haskell syntax without learning nomads. It isn't very complicated.

Thank you for taking time to provide a meaningful example in a commonly used language as it makes it pretty clear why monads could be considered useful in certain scenarios. You have managed to explain monads more clearly to me with a single post than any other article I've ever read.

Best explanation of monads I've read the last decade.

this made more sense to me than the article. thanks.

You forgot the return operation.

The standard example is adding checked exceptions. You can refactor nested checks for null into straight line code in the Either (or Maybe or Option) monad, that does the same thing.

Consider this pseudo/Haskell code. Functions might fail, so we have to check the return value using nested switches:

  modify s f = do
    ev <- get s
    case ev of
        Left e  -> return (Left e)
        Right v -> do
            let u = f v
            ev <- set s u
            case ev of
                Left e  -> return (Left e)
                Right __-> return (Right (v,u))

Lots of nested checks -- makes the code more unreadable, and harder to maintain. Equivalent to null checks in other languages.

The 'case' stuff however, is the monadic 'semicolon' between each statement. So we can refactor to:

  modify s f = do
    get s
        >>= \v -> do
            let u = f v
            set s u
                >>= \v -> do
                    return (v,u)

Using the error monad definition of bind / >>= - http://hackage.haskell.org/packages/archive/category-extras/...

So then, if you language supports monadic syntax, you can actually use semicolon instead of 'bind':

  modify s f = do {
    v <- get s   ;
    let u = f v  ;
    v <- set s u ;
    return (v,u) ;
  }

and if you are in a whitespace-sensitive language, the error checking disappears into the newline:

  modify s f = do
    v <- get s
    let u = f v
    v <- set s u
    return (v,u)

So the above code, in the Either monad, is equivalent to the original code, however, we now have shorter, cleaner code, and a compile-time guarantee that all return values are checked.

This example is my "programmable semicolon" motivator, from http://donsbot.files.wordpress.com/2009/01/semicolon.pdf

I chose the computational environment I wanted my code to run in -- one with checked errors -- and did this by overriding my language's default 'semicolon' behavior using the monad interface to do so.

I reprogrammed my programming language, to make it possible to write better code. That's real power.

It seems like a trade-off: obvious control flow and some extra `if intermediate_result is None: return BogusValue` error checks are replaced by non-obvious control flow.

Is the only value that you save a few lines of error-checking? It just doesn't seem worth it to me.

I think your arguing against abstraction in general.

We replaced a manual, verbose and error-prone pattern with a standardized abstraction, and added in compile-time guarantees that the pattern is enforced for free. This made the code shorter and clearer, and exposed the actual logic of the code. Now imagine this over 100s of thousands of lines of code, often using different patterns. It is an enormous win at scale.

Arguing that monads obscure control flow is strange - since most abstractions we care about obscure control flow - whether functions, loops or monadic bind - that's the point, after all...

I don't write my own stack push/enter/pop to call functions, and nor should I have to write out all the other boilerplate control flow patterns I use, when it can be simply programmed into a monad, and left to the compiler.

> I think your (sic) arguing against abstractions in general

No.

> We replaced a manual, verbose and error-prone pattern with a standardized abstraction

Alternatively, we replaced some easy to follow procedural code with a manual, verbose, and error-prone abstraction. I have no idea what is going on with the author's decorated classes, generators, etc.

How do you create a new monad pattern and debug it? All code is imperfect; it feels like we're just shifting some of the logic around to a different place.

> since most abstractions we care about obscure control flow - whether functions, loops or monadic bind

This is apples and oranges. Functions and loops are straight-forward, monadic bind (in this framework) involves indirecting through a bunch of complicated Python magic.

> I don't write my own stack push/enter/pop to call functions, and nor should I have to write out all the other boilerplate control flow patterns I use, when it can be simply programmed into a monad, and left to the compiler.

It sounds like an arguments from the exceptions camp — "everything would be so much better if we didn't have to check error returns from every subroutine!" But like exceptions over error codes, I think introducing monads is inventing a bigger problem to solve a comparatively small problem.

Just my 2¢.

It's complicated and fairly ugly to do this in any language which has no first-class support for the monad abstraction. I wouldn't use this code in a "real world" setting, and I doubt even the author would argue that you should. Many of Haskell's unique language features make monads "go down smoothly" in a way that most other languages will only be able to roughly imitate without extensions like user-definable operators, type classes, `do` notation, return type and higher-ranked polymorphism, etc.

How do you create a new monad pattern and debug it? All code is imperfect; it feels like we're just shifting some of the logic around to a different place.

Nearly all forms of abstraction in any programming language can be characterized as "shifting some of the logic around to a different place". The entire point of abstraction is to hide away complexity behind abstract interfaces so that we can build more and more complex systems without having to mentally wrangle with the entire stack of complexity all at once. For instance, most people writing code in a high-level language don't spend much time mentally compiling the code they're writing down to machine instructions; we trust that the language interpreter or compiler will take care of that complexity well enough for us so that we can focus on the bigger picture. Monads just ratchet up this level of abstraction one notch higher than most languages take it.

Monads are the very same sort of thing that lets us jump to other locations via function calls, or encapsulate shared mutable state in a class (in OOP languages). The only thing that makes them different is that the "call stack" and "class" abstractions are given first-class support in the majority of popular languages, while monads are not.

Furthermore, in a strongly typed language with support for monads, the implicit flow control in a series of monadic statements is made obvious by its type. When encountering a `do` block of type `Maybe x`, there is no ambiguity surrounding the fact that each statement in the block may fail, and if it does, will short-circuit the remainder of the computation. This is not so much "hidden" control flow as it is "syntactically unencumbered". It would take a significant lapse of attention to forget about the monadic context of the computation and its implications (and if you did forget, the compiler would tell you about it). No one complains that when you encounter a statement like `foo.bar()` in an OO language, you can't know exactly which definition of `bar` is being called without walking up the inheritance chain to find it. There is implicit "magic" taking place here as well, in the form of dynamic method dispatch, but because most programmers encounter this particular sort of implicit behavior every day, it doesn't seem so strange or dangerous.

This is apples and oranges. Functions and loops are straight-forward, monadic bind (in this framework) involves indirecting through a bunch of complicated Python magic.

Functions and loops seem more straightforward to you because you are used to using them in the languages you use regularly and are most comfortable with. To a reasonably experienced Haskell user, there is nothing about monads that is not equally straightforward or obvious. More than anything else, it's a question of familiarity.

I won't argue that the Python implementation isn't complicated or somewhat "magical". I just don't think that's a result of monads' inherent complexity; rather, it is the result of the fact that Python isn't designed for working with this particular kind of abstraction. Any implementation of it in a language like Python is bound to be a bit kludgey and difficult to follow.

In addition to tmhedberg's good reply, I'd observe that you are either A: excessively stuck on this particular Python implementation when people are trying to argue that monadic patterns are useful in general (and in fact this Python implementation isn't even correct), or B: tautologically arguing from a base of monadic patterns being difficult to conclude that monadic patterns are difficult.

They aren't. Really. They just historically had one of the single most disastrous PR departments in the history of programming concepts. (Which has gotten better, but the old PR is still floating around the nets, screwing up everyone it meets.) It's just an interface slightly more complicated than the standard Iterable interface that happens to have a lot of useful things that can conform to it, and then a lot of useful things that can be built on it (two statements equally true of Iterable itself). It's a great deal simpler to use them when appropriate than the horrifying complexity of trying to manually implement them over and over that you've just grown so used to you can't see any more.

I do my part by trying to ensure I use the term as an adjective instead of a noun, because "monad" is like "iterable" as a term. It is unfortunate that it inherited its status as a noun from the world of math, where that happens to make sense. It does not in programming.

complexFn = do x <- getSomeData y <- computeWith x z <- computeSomeMore y return z

Let's say you have here straightforward imperative code. Of course, a real example would be more complex. But suppose x is now a list and you want to vectorise computeWith. Put your x in a box/monad, let's call it Parallel. Define return and bind to be parallel (bind = par . fmap, or something), and that's it. Transparent parallelism.

Maybe it does numerical algorithms, and you want x to be an interval, or a tuple (value, error). Again, define the corresponding monad. Same thing with non-deterministic computation, amb-like operators, passing state between calls... The code that calls them stays the same.

It also provides type safety for operations. For instance, some Haskell libraries allow programmers to specify a network protocol with monads, then write servers/clients that are statically checked to be correct. All sorts of things like that.

Conceptually, a monad is a box with a tag on it (the name of the monad), and your rules for (1) putting things into it, and (2) applying functions to what's inside. Plus compile-time guarantees that you can't do weird things with them, like mix tags and stuff.

It's explicitly not explaining what a monad is, first paragraph of the article:

I've been informed that I didn't clearly explain what monads are and what the code examples are supposed to do. Sorry. I guess I assumed too much preexposure to monads. If you're no familiar with them, there are already so many tutorials on monads that I'll simply direct you to two of my favorites: spacesuits and wikipedia. I've also added more explanations of what the code snippets are supposed to do. I hope that helps.

(The spacesuits link is dead (live[1]) and neither directly address "your motivating example" point, although the non-monadic vs monadic code comparisons demonstrate that monadic code can be much much shorter and less repetitive.)

[1]: http://web.archive.org/web/20081206204420/http://www.loria.f...

The spacesuit one has been explicitly disowned by its author. "Programmable semicolons" is the rough modern consensus on the best one-line metaphor.

I give an example in "How would I even use a Monad (in C#)?" ( http://twistedoakstudios.com/blog/Post867_how-would-i-even-u... ), assuming a hypothetical extension to the language:

    ///<summary>Pulls the monad type outside of the list type by binding across the list's elements.</summary>
    ///<remarks>Not actually possible to compile in C# today.</remarks>
    public static M<IEnumerable<T>> BindAll<M, T>(this IEnumerable<M<T>> sequence)
        where M : Monad { //<-- Type parameter M takes a type parameter T. Not currently possible.
        return sequence.Aggregate(
            M.Return(Enumerable.Empty<T>()), //<-- Static interface method. Not currently possible.
            (wrappedAccumulator, wrappedNextItem) =>
                from accumulator in wrappedAccumulator
                from item in wrappedNextItem
                select accumulator.Concat(new[] { item }).ToArray().AsEnumerable());
    }

This single method combines several apparently distinct methods: waiting for all tasks, choosing all of the combinations from a list of lists, etc.

> a real example of what problems monads solve

Have you ever used an async promise library in Javascript? Its a monad! (you have a function to create a new "async promise" given a sync value and you have a method to chain a promise with a callback that returns a new promise)

The complicated thing about monads is that they are an abstract interface. Having the abstract interface is good if you want to write generic code that works on all monads (and if you want to prove things about your code) but makes it hard to understand stuff. Another problem with monads is that its API can't be implemented directly in most languages so they get restricted to the more functional languages: one of the methods (>>=) receives an anonymous function as an argument (and many languages don't support those)and another method (the awkwardly named "return") is polymorfhic on its return value (OO languages can only handle polymorphism on the first input argument, the "this").

With templates/generics, polymorphic in return type is no problem. Consider Java Guava's

    Lists.<String>newArrayList()

Sure, but its kind of hackish and many people don't know about it. It also doesn't really apply to dynamic languages like Python :(

well, it's not claiming to explain monads.

but it does contain a pile of examples. try looking at the mailbox example and then running the code. you'll have a pretty powerful impression of the way that monads can modify apparent control flow semantics.

I think one of the best and clearest examples of a useful monad is the Error monad in OCaml (and Haskell, I think). Error is a type that can return two different things depending on the result of a computation. One could use exceptions for this sort of thing, but this is much, much cheaper.

i've worked through this article a couple times and his implementation never really sat well with me, the "with nice syntax for monad comprehensions" bit really obfuscates the implementation.

here's python source to a monadic lisp interpreter, which i wrote to follow along the paper "monad transformers and modular interpreters" [1]. i think this is a much simpler implementation of python monads than provided in the ValuedLessons article. https://github.com/dustingetz/monadic-interpreter

Study of this implementation will teach you why nobody actually uses monads in python for non-toy projects. A literal port of this code to clojure would feel so much more idiomatic and not hacky at all.

here are some smaller code dumps demonstrating the fundamental concepts to that monadic lisp interpreter:

http://www.dustingetz.com/2012/10/02/reader-writer-state-mon... http://www.dustingetz.com/2012/10/07/monads-in-python-identi...

[1] http://haskell.cs.yale.edu/wp-content/uploads/2011/02/POPL96...

I think the point of this article is to make a "nice" syntax for monadic operations in python (i.e. avoiding all the lambdas and extra parens in the "bind(mx, lambda x: my)"/"mx >> (lambda x: my)" pattern), no matter how unclear and non-pedagogical the implementation ends up.

BTW: This was already submitted to HN.

http://www.hnsearch.com/search#request/all&q=Monads+in+P...

But that doesn't make it less interesting ;)

I went through this article some time ago and, while it's certainly neat implementation and worth understanding (that was the first recursive generator that made sense to me - thanks to this I had much easier time understanding Scheme's call/cc and it's uses), it needs to be noted that it is not a generic monad implementation. You can not, for example, implement list monad (I tried very hard and couldn't, I saw the same said in comments below the article, but if it's possible please let me know!) using this implementation and syntax, because you can not "rewind" Python's generators.

So, while it's nice implementation for some kinds of monads it's not nearly general enough to be (IMHO) called "monads in Python" - it is possible to implement fully general monads in Python, but you need nested lambdas and there is no getting away from it.

Still, very nice hack and worth spending an evening (or two) to understand how it works.

The first line of his first example of using his monad implementation is:

@do(Maybe)

Ctrl+F Maybe. It's not defined anywhere!

I was excited to see that someone could maybe finally explain to me, in Python, why people are so excited about Monads.

I looked at Haskell once. It looks impossible to understand without understanding Monads. (And near-impossible to understand even if you do understand Monads -- the syntax is a nightmare.) I thought maybe this article would help me, by using the syntax of language I do understand -- Python -- with a concept I don't understand -- Monads.

But this excitement was misplaced, since this isn't a usable demo. Please, if you're the author of this article or someone who understands this code, post a Github repo, or a tarball on your HTTP server, or something with a runnable, simple example of code that uses the article's approach to monads.

This is very interesting, very intelligent. Indeed this is too much intelligent. There is a huge amount of highly valuable programmers that won't be able to understand all that mess, and the gain is questionable at least given that there are alternate constructs that are way better compromise between expressiveness and maintainability.

Use the right tool in its intended way: don't try to retrofit constructs in languages were they don't fit, just for an accessory characteristic. (Every line of an imperative language is conceptually kind of a monad, so the article here is just trying to convince us that yet another form of hidden goto is good, by an ad-hoc extension in a language were more than half of monad necessity is missing)

It might require an intelligent programmer to create, but as a library, can be used by regular, unintelligent programmers. If he documents his monads well and shows how to use it, and it's effective, then it's not such a big deal.

Or, you know, this is more of an attempt to show programmers stuck in simpler languages what other PL features have to offer.

"Every line of an imperative language is conceptually kind of a monad[.]"

Every line of an imperative language is conceptually in the IO monad. That doesn't mean that there's never reason to run things in another monad - many do things IO can't.

The problem with Monads is that the people who understand them are the least qualified to explain them to other people.

I disagree. I think the only big problems with teaching monads is that they are a mathematically inspired abstract interface (while most people only need to bother about the concrete implementations of this inteface) and that Haskell forced them too soon on people, since you need monads to do IO.

This is specious. Many people understand monads, and their ability to teach and explain varies wildly.

The corollary would mean that the people who can explain well can't understand monads, which means that some people just can't understand them. We're doomed!

not that i agree with the top comment, but your reasoning only works for a static view of people (i.e. they cannot learn something and at the same time forget something).

Reply on news.ycombinator.com