0

This question is related to this post: Understanding do notation for simple Reader monad: a <- (*2), b <- (+10), return (a+b)

I don't care if a language is hard to understand if it promises to solve some problems that easy to understand languages give us. I've been promised that the impossibility of changing state in Haskell (and other functional languages) is a game changer and I do believe that. I've had too many bugs in my code related to state and I totally agree with this post that reasoning about the interaction of objects in OOP languages is near impossible because they can change states, and thus in order to reason about code we should consider all the possible permutations of these states.

However, I've been finding that reasoning about Haskell monads is also very hard. As you can see in the answers to the question I linked, we need a big diagram to understand 3 lines of the do notation. I always end up opening stackedit.io to desugar the do notation by hand and write step by step the >>= applications of the do notation in order to understand the code.

The problem is more or less like this: in the majority of the cases when we have S a >>= f we have to unwrap a from S and apply f to it. However, f is actually another thing more or less in the formS a >>= g, which we also have to unwrap and so on. Human brain doesn't work like that, we can't easily apply these things in the head and stop, keep them in the brain's stack, and continue applying the rest of the >>= until we reach the end. When the end is reached, we get all those things stored in the brain's stack and glue them together.

Therefore, I must be doing something wrong. There must be an easy way to understand '>>= composition' in the brain. I know that do notation is very simple, but I can only think of that as a way to easily write >>= compositions. When I see the do notation I simply translate it to a bunch of >>=. I don't see it as a separate way of understanding code. If there is a way, I'd like someone to tell me.

So the question is: how to read the do notation?

Will Ness
  • 70,110
  • 9
  • 98
  • 181
PPP
  • 1,279
  • 1
  • 28
  • 71
  • What diagram do you refer to? – Bergi Feb 07 '20 at 00:39
  • 5
    This seems more like a rant than a question, especially with the argumentative title. – Joseph Sible-Reinstate Monica Feb 07 '20 at 00:39
  • 2
    I think your mistake is trying to expand `do` syntax to `>>=` notation, and then to expand `g` until unwrapping stops, and then probably continue expanding by replacing `>>=` with its definition. This is what you do at most once when you try to understand how a particular monad is *implemented*. But you never do that when reasoning about code, for that you should stay on the level of that `S` monad and its purpose. – Bergi Feb 07 '20 at 00:43
  • @Bergi what do you mean with "you should stay on the level of that S monad and its purpose"? – PPP Feb 07 '20 at 01:57
  • 1
    @LucasZanella You just should argue what the respective monad (e.g. `IO`, `List`, `Reader`) does (i.e. "do side effects consecutively", "concatmap", "read from that one parameter of the implicit wrapping function" respectively), not expand to the implementation level. – Bergi Feb 07 '20 at 02:02

4 Answers4

6

Given a simple code like

foo :: Monad m => m Int -> m Int -> m Int
foo x y = do
    a <- y  -- I'm intentionally doing y first; see the Either example
    b <- x
    return (a + b)

you can't say much about <- except that it "gets" an Int value from x or y. What "get" means depends very much on what m is.


Some examples:

m ~ Maybe

foo (Just 3) (Just 5) evaluates to Just 8; replace either argument with Nothing, and you get Nothing. <- tries to get a value out the Maybe Int value, but aborts the rest of the block if it fails.

m ~ Either a

Pretty much the same as Maybe, but replacing Nothing with the first Left value that it encounters. foo (Right 3) (Right 5) returns Right 8. foo x (Left "foo") returns Left "foo", whether x is a Right or Left value.

m ~ []

Now, instead of getting an Int, <- gets every Int from among the given choices. It does so nondeterministically; you can imagine that the function "forks" into multiple parallel copies, each one having chosen a different value from its list. In the end, the final result is a list of all the results that were computed.

foo [1,2] [3,4] returns [4, 5, 5, 6] ([3 + 1, 3 + 2, 4 + 1, 4 + 2]).

m ~ IO

This one is tricky, because unlike the previous monads we've looked at, there isn't necessarily a value yet to get. foo readLn readLn will return whatever the sum of the two numbers read from standard input is, with the possibility of a run-time error should the strings so read not be parseable as Int values.

You might think of it as working like the Maybe monad, but with run-time exceptions replacing Nothing.

chepner
  • 497,756
  • 71
  • 530
  • 681
  • 1
    "and so all those different types of computations are described by *the same `do` block*, their specific meaning determined by the concrete type used in place of the abstract `m`" could be a nice finishing line, or perhaps you wanted a reader to realize this on their own, without saying this explicitly. :) --- great set of concrete illustrative examples, although it all describes what is *an Applicative Functor* (except the IO). which of course must be understood first! – Will Ness Feb 07 '20 at 15:43
5

Part 1: no need to go into the weeds

There is actually a very simple, easy to grasp, intuition behind monads: they encode the order of stuff happening. Like, first do this thing, then do the other thing, then do the third thing. For example:

executeMadDoctrine = do
    wait oneYear
    s <- evaluatePoliticalSituation
    case s of
        Stable -> do
            printInNewspapers "We're going to live another day"
            executeMadDoctrine -- recursive call
        Unstable -> do
            printInNewspapers "Run for your lives"
            launchMissiles
            return ()

Or a slightly more realistic (and also compilable and executable) example:

main = do
    putStrLn "What's your name?"
    name <- getLine
    if name == "EXIT" then
        return ()
    else do
        putStrLn $ "Hi, " <> name
        main

Simple. Just like Python. Human brain does, indeed, work exactly like this.

You see, you don't need to know how it all works inside, unless you start doing more advanced things. After all, you're probably not thinking about the order of cylinders firing every time you start your car, do you? You just hit the gas and it goes. It's the same with do.

Part 2: you picked a bad example

The example you picked in your previous question is not the best candidate for this stuff. The Monad instance for functions is indeed a bit brain-wrecking. Even I have to make a little effort to understand what's going on - and I've been doing Haskell professionally for quite some time.

The trouble here is mathematics. The bloody thing turns out unreasonably effective time after time, especially when nobody is asking it to.

Think about this: first we had perfectly good natural numbers that we could very well understand. I have two eyes, and you have one sword, I better run. But then it turned out that we need zero. Why the bloody hell do we need it? It's sacrilege! You can't write down something that isn't! But it turns out you have to have it. It unambiguously follows from the other stuff we know is true. And then we got irrational numbers. WTF is that? How do I even understand it? I can't have π oranges after all, can I? But they too must exist. It just follows. No way around it. And then complex numbers, transcendental, hypercomplex, unconstructible... My brain is boiling at this point.

It's sort of the same with monads: there is this peculiar mathematical object, and at some point somebody noticed that it's very good for expressing the order of computation, so we appropriated monads for that. But then it turns out that all kinds of things can be made to look like monads, mathematically speaking. No way around it, it just is.

And so we have all these funny instances. And the do notation still works for them, because they're monads (mathematically speaking), but it's no longer about order. Like, did you know that lists were monads too? But just like with functions, the interpretation for lists is not "order", it's nested loops. And if you combine lists with something else, you get non-determinism. Fun stuff.

But just like with different kinds of numbers, you can learn. You can build up intuition over time. Do you absolutely have to? See part 1.

Fyodor Soikin
  • 78,590
  • 9
  • 125
  • 172
  • 1
    "monads encode order"? I very much dislike this take on it. there's so much more to it than that. what about applicative do, for starters. a monad might express a true nondeterminism, too. the order is only truly defined by data dependencies. State Passing has an inherent order; Reader has none. so, nah. it's only more confusing, IMO. – Will Ness Feb 07 '20 at 08:39
  • or maybe, this goes to the ultimate difference between Monads and Applicatives ([e.g.](https://stackoverflow.com/a/54962626/849891)) (Reader really being only the latter), and we ought to answer these kinds of questions by "forget Monad for a moment, understand what's an Applicative Functor, first". then, Monads are indeed about order -- but only on top of what's that same type seen as AF is all about. so no, it's not "simply" about order after all. :) – Will Ness Feb 07 '20 at 09:18
  • @WillNess Applicatives depend on the previous effect whereas monads may additionally depend on the prev value. Isn't order a direct outcome of this property specific to monads? The only thing I don't quite get is why depending on the prev effect doesn't enforce order. Maybe performing effects is decoupled from the evaluation strategy.. –  Feb 07 '20 at 09:34
  • 1
    @bob Applicative's effects do not depend on anything. Each computation is given upfront, before the combined computation runs. With Monads, the next computation itself can be created / changed based on the previously computed value. (see e.g. "The difference between Applicative and Monad" in [this answer](https://stackoverflow.com/a/24467994/849891), which gives a great and memorable example) – Will Ness Feb 07 '20 at 09:48
  • @WillNess there is an inherent tension between completeness and accessibility of an explanation. One must strike a balance. This is why we don't start teaching arithmetic with complex numbers. – Fyodor Soikin Feb 07 '20 at 13:11
  • yes, that it why I prefer it when it's not taken apart into the M and the AF with the "it's about order" pitch (too advanced), but instead presented all smashed together as "notions of computations" pitch (simpler); and also to use (pseudo-)do-notation (or monad comprehensions) with M and the AF and even F, equally, for the [exposition purposes](https://stackoverflow.com/a/39647091/849891). – Will Ness Feb 07 '20 at 14:08
  • @WillNess The "notion of computation" is abstract. It corresponds to nothing in the everyday experience. This is not how people learn. We can't read a strict definition and immediately retain it and be able to apply it. Instead we first build a partial, and usually not-quite-correct, but still somewhat useful intuition, and then slowly build on it, expand and correct. – Fyodor Soikin Feb 07 '20 at 15:02
  • I thought pretty much everyone understand various modes of computations like exceptions and optional failure/early exit, and state passing is not that far ahead of the curve. "computational (self-adjusting) pipeline", "generalized function application", "monads are EDSL", all more helpful than "ordering" IMO, but YMWV. :) – Will Ness Feb 07 '20 at 15:21
  • "computational pipeline" is just a fancy way of saying "order of things". And "generalized function application" - well, that's exactly what the OP had trouble understanding in the first place. – Fyodor Soikin Feb 07 '20 at 15:24
  • no, I take it to mean more "there's much hidden stuff going on in the pipe walls" than just the order of the flow inside them. but all matters of opinion... :) – Will Ness Feb 07 '20 at 15:26
2

Any long do chains can be re-arranged into the equivalent binary do, by the associativity law of monads, grouping everything on the right, as

do { A ;           B ; C ; ...              } 
=== 
do { A ; r <- do { B ; C ; ... } ; return r }. 

So we only need to understand this binary do form to understand everything else. And that is expressed as single >>= combination.

Then, treat do code's interpretation (for a particular monad) axiomatically instead, as a bunch of re-write rules. Convince yourself about the validity of those rules for a particular monad just once (yes, using possibly extensive >>=-based re-writes, once).

So, for the Reader monad from the question's linked entry,

(do { S f }) x                       ===   f x 

(do { a <- S f ; return (h a) }) x   ===   let {a = f x} in h a 
                                     ===   h (f x) 

(do { a <- S f ;                     ===   let {a = f x ; 
      b <- S g ;                                b = g x} in h a b 
      return (h a b) }) x            ===   h (f x) (g x) 

and any longer chain of lets is expressible as nested binary lets, equivalently.

The last one is liftM2 actually, so an argument could be made that understanding a particular monad means understanding its particular liftM2 (*), really.

And those Ss, we end up just ignoring them as noise, forced on us by Haskell syntax (well, that question didn't use them at all, but it could).


(*) more precisely, liftBind, (do { a <- S f ; b <- k a ; return (h a b) }) x === let {a = f x ; b = g x } in h a b where (S g) x === k a x. (specifically, this, after the words "the long version")


And so, your attitude of "When I see the do notation I simply translate it to a bunch of >>=. I don't see it as a separate way of understanding code" could actually be the problem.

do notation is your friend. Personally, I first hated it, then learned to love it, and now I see the >>=-based re-writes as its (low-level) implementation, more and more.

And, even more abstractly, do can equivalently be written as Monad Comprehensions, looking just like list comprehensions!

Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • what is `h`? It comes out of nowhere – PPP Feb 07 '20 at 03:08
  • 2
    It's whatever function you choose to use. `h a b` is just the most generic way to write "some expression involving `a` and `b`". It could be something simple like `a + b`, or something much more complicated - it doesn't matter. – Robin Zigmond Feb 07 '20 at 07:09
1

@chepner has already included in his answer quite a lot of what I would have said, but I wish to emphasise another aspect, which I feel is quite pertinent to this question: the fact that do notation is, for most developers, a much easier and more easily understandable way to work with any monadic expression which is at least moderately complex.

The reason for this is that, in an almost miraculous way, do blocks end up very much resembling code written in an imperative language. Imperative style code is much easier to understand for the majority of developers, and not only because it's by far the most common paradigm: it gives an explicit "recipe" for what a piece of code is doing, whereas more typical Haskell expressions, particularly monadic ones involving nested lambdas and >>= everywhere, very easily become difficult to comprehend.

In saying this I certainly do not mean that one should code in an imperative language as opposed to Haskell. The advantages of the pure functional style are well documented and seemingly well understood by the OP, so I will not go into them here. But Haskell's do notation allows one to write code in an imperative-looking "style", which therefore is explicit and easier to comprehend - at least on a small scale - while sacrificing none of the advantages of using a pure functional language.

This "imperative style" of do notation is, I feel, more visible with some monads than others, and I wish to illustrate my point with examples from a couple of monads which I find suit the "imperative style" well. First, IO, where I can give this simple example:

greet :: IO ()
greet = do
    putStrLn "Hello, what is your name?"
    name <- readLine
    putStrLn $ "Pleased to meet you, " ++ name ++ "!"

I hope it's immediately obvious what this code does, when executed by the Haskell runtime. What I wish to emphasise is how similar it is to imperative code, for example, this Python translation (which is not the most idiomatic, but has been chosen to exactly match the Haskell code line for line).

def greet():
       print("Hello, what is your name?")
       name = input()
       print("Pleased to meet you, " + name + "!")

Now ask yourself, how easy would the code be to understand in its desugared from, without do?

greet = putStrLn "Hello, what is your name?" >> readLine >>= \name -> putStrLn $ "Pleased to meet you, " ++ name ++ "!"

It's not particularly difficult, granted - but I hope you agree that it's much more "noisy" than the do block above. I can't speak for others, but I very much doubt I'm alone in saying that the latter version might take me 10-20 seconds or so to fully comprehend, whereas the do block is instantly comprehensible. And this of course is an extremely simple action - anything more complicated, as found in many real-world applications, makes the difference in comprehensibility much greater.

I have chosen IO for a reason, of course - I think it's in dealing with IO in particular that it's most natural to think in terms of "do this action, then if the result is that then do the next action, otherwise...". While the semantics of the IO monad fits this perfectly, it's much easier to translate the code into something like that when written in quasi-imperative notation than it is to use >>= directly. And the do notation is easier to write, too.

But although IO is the clearest example of this, it's certainly not the only one. Another great example is the State monad. Here's a simple example of using it to find the sum of a list of integers (and I know you wouldn't actually do that this way, but it's just a very simple example of some not-totally-trivial code that used this monad):

sumList :: State [Int] Int
sumList = go 0
    where go subtotal = do
                    remaining <- get
                    case remaining of
                         [] -> return subtotal
                         (x:xs) -> do
                              put xs
                              go $ subtotal + X

Here, in my opinion, the steps are very clear - the auxiliary function go successively adds the first element of the list to the running total, while updating the internal state with the tail of the list. When there is no more list, it returns the running total. (Given the above, the function evalState sumList will take an actual list and sum it.)

One can probably come up with better examples (particularly ones where the calculation involved isn't trivial to do in other ways), but my point is hopefully still clear: rewriting the above with >>= and lambdas would make it much less comprehensible.

do notation is, in my opinion, why the often-quoted quip about Haskell being "the world's finest imperative language", has more than a grain of truth. By using and defining different monads one can write easily understandable "imperative" code in a wide variety of situations - while still having guarantees that various functions can't, for example, change global state. It's in many ways the best of both worlds.

Robin Zigmond
  • 17,805
  • 2
  • 23
  • 34
  • a counterpoint: https://pastebin.com/YpBqXWpX. `do` enforces the indentation i.e. alignment and separate lines, but same formatting can be used with the `>>=`/lambdas as well, even if not enforced. :) – Will Ness Feb 08 '20 at 22:36
  • @WillNess - fair enough, indeed you don't need `do` notation to make the monadic expression more readable. But I still think `do` notation is slightly more natural looking, especially for those new to Haskell. In particular, `a <- m`, as an analogue of `a = m` in an imperative language, is to me a bit easier to instantly comprehend than `m >>= \a -> ...`. But you make a good point nonetheless. – Robin Zigmond Feb 08 '20 at 22:54
  • *"`a <- m` is like `a = m`"* but perhaps the `let`'s `=`, not the imperative `:=`. indeed that's why they called it "bind" (I think). :) – Will Ness Feb 09 '20 at 06:45