Converting `do` Notation `addStuff` to `>>=`

Question

Learn You a Haskell presents the addStuff function:

import Control.Monad.Instances

addStuff :: Int -> Int
addStuff = do
    a <- (*2)    -- binds (*2) to a
    b <- (+10)   -- binds (+10) to b
    return (a+b) -- return has type sig: 'Monad m => a -> m a'

Are the types of a, b, and return (a+b) all Int -> Int? I think so, but I'm not sure how bind-ing plays a role.

I tried to implement it using >>=, but I'm not sure how to complete it (hence ...).

addStuff' :: Int -> Int
addStuff' = (*2) >>= (+10) >>= ...

Please give me a hint to complete it, as well as edit my understanding of the do notation version.

As I understand, the ... needs to include a type of Int -> Int. In the do version, I could use a and b, but I'm not sure how to add them with the >>= version.

Answer 1

When working with the reader monad (a.k.a. the function monad), you have the type a -> b, which can be rewritten as (->) a b. The actual monad instance here is

instance Monad ((->) r) where
    return x = const x
    f >>= g = \r -> g (f r) r

Notice that during >>=, the type is

(>>=) :: ((->) r a) -> (a -> ((->) r b)) -> ((->) r b)

Which can be rewritten as

(>>=) :: (r -> a) -> (a -> (r -> b)) -> (r -> b)

Or even

(>>=) :: (r -> a) -> (a -> r -> b) -> (r -> b)

So as you can see, what >>= does is take a single input, apply that to f, and then apply that result to g to produce a new function r -> b. So for your example, you could use:

addStuff' :: Int -> Int
addStuff' = (*2) >>= (+)

And so addStuff' 10 == 30, since it performs the computation (10 * 2) + (10). Note how 10 is fed both to (*2) and (+), and the result of (10*2) is fed to (+) as well. It might make things a little more clear to see it as

test :: Int -> (Int, Int, Int)
test = do
    x <- (*2)
    y <- (*3)
    z <- (*5)
    return (x, y, z)

And it's result would be

> test 1
(2, 3, 5)
> test 10
(20, 30, 50)

What this essentially is doing is taking the argument to test "before" it's been applied, feeding it to each of the functions on the right hand side of the <-s, and then combining that result in the return.

---

So how can you write these without do notation? You could do something like

test :: Int -> (Int, Int, Int)
test =
    (\r -> r * 2) >>= (\x ->
        (\r -> r * 3) >>= (\y ->
            (\r -> r * 5) >>= (\z ->
                return (x, y, z))))

Which, admittedly, is not very readable, even with formatting, but the gist is basically that r gets fed to each intermediate function, which produces a result, and a couple nested lambda expressions later you return all three of those results in a tuple.

With a bit of simplification, you could also make each of those nested lambdas into two arguments lambdas:

test =
    (\r -> r * 2) >>=
        (\x r -> r * 3) >>=
            (\y r -> r * 5) >>=
                (\z r -> const (x, y, z) r)

I've also replaced the last \z -> return (x, y, z) with its equivalent \z -> const (x, y, z) => \z r -> const (x, y, z) r, just so they all have the same form.

Answer 2

As a rough rule if you want to manually desugar do-notation, first erase the do at the top and flip the bind arrow (<-) on the left-hand-side to a (>>=) on the right-hand-side with the variable on the left as a lambda variable on the right. So:

addStuff :: Int -> Int
addStuff = do
    a <- (*2)
    ... rest ...

Becomes:

addStuff :: Int -> Int
addStuff =
  (*2) >>= (\a ->
  ... rest ... 
  )

This is recursive, so the next term in the do-notation then becomes nested in the lambda of the desugared term above it, all the way down to the last expression which is just the body of the nested lambda expression.

The desugaring is quite mechanical, it's defined by the following rewrites, where ; denotes a newline.

do { a <- f ; m } ≡ f >>= \a -> do { m }
do { f ; m } ≡ f >> do { m }
do { m } ≡ m

Both a and b are of type Int while return (a+b) has type Int -> Int which is the last term in the do-notation so it has to be identical to the toplevel signature. Using -XScopedTypeVariables we can manually annotate the subterms:

{-# LANGUAGE ScopedTypeVariables #-}

import Control.Monad.Instances

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

Answer 3

Thanks to bheklilr. I wrote my own code.

addStuff :: Int -> Int
addStuff = (\r -> r * 2) >>= (\x ->
           (\r -> r + 10) >>= (\y ->
           return (x + y)))