Understanding do notation for simple Reader monad: a <- (*2), b <- (+10), return (a+b)

Question

instance Monad ((->) r) where  
    return x = \_ -> x  
    h >>= f = \w -> f (h w) w  

import Control.Monad.Instances  

addStuff :: Int -> Int  
addStuff = do  
    a <- (*2)  
    b <- (+10)  
    return (a+b)

I'm trying to understand this monad by unwiding the do notation, because I think the do notation hides what happens.

If I understood correctly, this is what happens:

(*2) >>= (\a -> (+10) >>= (\b -> return (a+b)))

Now, if we take the rule for >>=, we must understand (*2) as h and (\a -> (+10) >>= (\b -> return (a+b))) as f. Applying h to w is easy, let's just say it is 2w (I don't know if 2w is valid in haskell but just for reasoning lets keep it this way. Now we have to apply f to h w or 2w. Well, f simply returns (+10) >>= (\b -> return (a+b)) for an specific a, which is 2w in our case, so f (hw) is (+10) >>= (\b -> return (2w+b)). We must first get what happens to (+10) >>= (\b -> return (2w + b)) before finally applying it to w.

Now we reidentify (+10) >>= (\b -> return (2w + b)) with our rule, so h is +10 and f is (\b -> return (2w + b)). Let's first do h w. We get w + 10. Now we need to apply f to h w. We get (return (2w + w + 10)).

So (return (2w + w + 10)) is what we need to apply to w in the first >>= that we were tyring to uwind. But I'm totally lost and I don't know what happened.

Am I thinking in the rigth way? This is so confusing. Is there a better way to think of it?

score 6 · Accepted Answer · answered Feb 05 '20 at 06:11

You're forgetting that operator >>= doesn't return just f (h w) w, but rather \w -> f (h w) w. That is, it returns a function, not a number.

By substituting it incorrectly you lost the outermost parameter w, so it's no wonder it remains free in your final expression.

To do this correctly, you have to substitute function bodies for their calls completely, without dropping stuff.

If you substitute the outermost >>=, you will get:

(*2) >>= (\a -> ...) 
==
\w -> (\a -> ...) (w*2) w

Then, if you substitute the innermost >>=, you get:

\a -> (+10) >>= (\b -> return (a+b))
==
\a -> \w1 -> (\b -> return (a+b)) (w1 + 10) w1

Note that I use w1 instead of w. This is to avoid name collisions later on when I combine the substitutions, because these two ws come from two different lambda abstractions, so they're different variables.

Finally, substitute the return:

return (a+b)
==
\_ -> a+b

Now insert this last substitution into the previous one:

\a -> (+10) >>= (\b -> return (a+b))
==
\a -> \w1 -> (\b -> return (a+b)) (w1 + 10) w1
==
\a -> \w1 -> (\b -> \_ -> a+b) (w1 + 10) w1

And finally insert this into the very first substitution:

(*2) >>= (\a -> ...) 
==
\w -> (\a -> ...) (w*2) w
==
\w -> (\a -> \w1 -> (\b -> \_ -> a+b) (w1 + 10) w1) (w*2) w

And now that all substitutions are compete, we can reduce. Start with applying the innermost lambda \b -> ...:

\w -> (\a -> \w1 -> (\_ -> a+w1+10) w1) (w*2) w

Now apply the new innermost lambda \_ -> ...:

\w -> (\a -> \w1 -> a+w1+10) (w*2) w

Now apply \a -> ...:

\w -> (\w1 -> w*2+w1+10) w

And finally apply the only remaining lambda \w1 -> ...:

\w -> w*2+w+10

And voila! The whole function reduces to \w -> (w*2) + (w+10), completely as expected.

I understood. Bow how on earth could the do notation explain all this? I understand the do notation as simply a way of writing a chained `>>=` application in an easier to read way, BUT I don't know how to write a do notation without first writing the chained `>>=` version, so I see no point in it. — Guerlando OCs, Feb 05 '20 at 06:37
@GuerlandoOCs if that's your real question you should update the OP to ask if explicitly. But how to "read" `do` notation depends on the specific monad being used - precisely because it desugars to uses of `>>=`. But in general, `a <- m` means "run the computation `m`, and assign the result to the variable `a`", except it does this in a functionally pure way. In the case of this function monad, it means that, in the function we are building, we start by multiplying the input by 2, and use `a` to denote the result. — Robin Zigmond, Feb 05 '20 at 07:03
@GuerlandoOCs Perhaps this monad isn't the most useful one, but you might think of do-notation in this monad as something that lets you access an implicit (immutable) value. When you "run" the line `x <- f`, you apply `f` to the implicit value, and bind the result to `x`. So, instead of `foo v = let {x = f v ; y = g v ; z = h v } in x+y+z` we can make `v` implicit and write `foo = do {x <- f; y <- g; z <- h; return (x+y+z) }`. You can write the last code without thinking of what the underlying `>>=` does. — chi, Feb 06 '20 at 15:15

Will Ness · Answer 2 · 2020-02-06T15:02:05.187

First, we write out the implicit argument in your definition explicitly,

addStuff :: Int -> Int  
addStuff = do  
    a <- (*2)  
    b <- (+10)  
    return (a+b)
  =
addStuff :: Int -> Int  
addStuff x = ( do  
    a <- (*2)  
    b <- (+10)  
    return (a+b) ) x
  =
  ....

Then, with

    return x  =  const x  
    (f =<< h) w  =  f (h w) w      -- (f =<< h)  =  (h >>= f)

it should be easier to follow and substitute the definitions, line for line:

  ....
  =
    ( (*2) >>= (\a ->                     -- (h >>= f)  =
       (+10) >>= (\b -> 
         const (a+b) ) ) ) x
  =
    ( (\a ->                              --   =   (f =<< h)
       (+10) >>= (\b ->
         const (a+b) ) ) =<< (*2) ) x     -- (f =<< h) w  =
  =
      (\a ->
       (+10) >>= (\b ->
         const (a+b) ) )  ( (*2) x) x     --   =  f (h w) w 
  =
    ( let a = (*2) x in                   -- parameter binding
       (+10) >>= (\b ->                   
         const (a+b) ) )            x
  =
      let a = (*2) x in                   -- float the let 
      ((\b ->
         const (a+b) ) =<< (+10) )  x     -- swap the >>=
  =
      let a = (*2) x in
       (\b ->                             -- (f =<< h) w  =
         const (a+b) )  ( (+10) x)  x     --   =  f (h w) w
  =
      let a = (*2) x in
       (let b = (+10) x in                -- application
          const (a+b) )             x
  =
      let a = (*2)  x in                  -- do a <- (*2)
      let b = (+10) x in                  --    b <- (+10)
      const (a+b)   x                     --    return (a+b)

The essence of reader monad is application to same argument shared between all calls.

score 1 · Answer 3 · answered Feb 05 '20 at 15:36

1

Intuitively, each function call on the right-hand side of the <- is given an additional argument, which you can think of as the argument to addStuff itself.

Take

addStuff :: Int -> Int  
addStuff = do  
    a <- (*2)  
    b <- (+10)  
    return (a+b)

and turn it into

addStuff :: Int -> Int  
addStuff x = let a = (*2) x
                 b = (+10) x
             in (a+b)

It looks a little less "strange" if you use the MonadReader instance for (->) r, which provides ask as a way to get direct access to the implicit value.

import Control.Monad.Reader

addStuff :: Int -> Int
addStuff = do
  x <- ask   -- ask is literally just id in this case
  let a = x * 2
  let b = x + 10
  return (a + b)

answered Feb 05 '20 at 15:36

chepner

497,756
71
530
681

might I suggest turning the "and turn it into `addStuff x = let { a = (*2) x ; b = (+10) x } in ` **`(a+b)`** into `addStuff x = { let a = (*2) x ; b = (+10) x } in ` **`const (a+b) x`** ..? – Will Ness Feb 05 '20 at 18:06
I didn't mean to imply that my transformation was a strict desugaring and replacement of the `Monad` methods with their definitions. `const (a+b) x` just reduces to `a + b` anyway, so I'd prefer to leave it as it is. – chepner Feb 05 '20 at 18:20

Understanding do notation for simple Reader monad: a <- (*2), b <- (+10), return (a+b)

3 Answers3

Linked