What is the type of the variable in do-notation here in Haskell?

637 views Asked by At

The codes below looks quite clear:

do 
  x <- Just 3
  y <- Just "!"
  Just (show x ++ y)

Here the type of x is Num and y is String. (<- here is used to take actual value out of the Monad)

However, this snippet looks not so clear to me:

import Control.Monad.Instances
addStuff :: Int -> Int
addStuff = do
  a <- (* 2)
  b <- (+ 10)
  return (a + b)

What is the type of a and type of b here? It seems they act like a Num, but a <- (* 2) and b <- (+ 10) looks cryptic here...

Does anyone have ideas about this?

2

There are 2 answers

2
Sebastian Paaske Tørholm On BEST ANSWER

Well, you've stumbled upon a kind of weird monad.

The monad in question is the Monad ((->) r). Now, what does that mean? Well, it's the monad of functions of the form r -> *. I.e., of functions that take the same type of input.

You asked what the type of a and b are in this instance. Well, they are both Num a => a, but that doesn't really explain much.

Intuitively, we can understand the monad like this: A monadic value is a function that takes a value of type r as input. Whenever we bind in the monad, we take that value and pass it to the bound function.

I.e., in our addStuff example, if we call addStuff 5, then a is bound to (*2) 5 (which is 10), and b is bound to (+10) 5 (which is 15).

Let's see a simpler example from this monad to try to understand how it works precisely:

mutate = do a <- (*2)
            return (a + 5)

If we desugar this to a bind, we get:

mutate = (*2) >>= (\a -> return (a + 5))

Now, this doesn't help much, so let's use the definition of bind for this monad:

mutate = \ r -> (\a -> return (a + 5)) ((*2) r) r

This reduces to

mutate = \ r -> return ((r*2) + 5) r

Which we using the definition that return is const, can reduce to

mutate = \ r -> (r*2) + 5

Which is a function, that multiplies a number by 2, and then adds 5.

That's one weird monad.

0
mucaho On

Given addStuff

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

the definition desugars into

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

Hovering over the >>= in fpcomplete online editor shows

:: Monad m => forall a b. 
              (m a       ) -> (a   -> m b       ) -> (m b       )
::            (Int -> a  ) -> (a   -> Int -> b  ) -> (Int -> b  )
::            (Int -> Int) -> (Int -> Int -> Int) -> (Int -> Int)

That leads us to believe we use a Monad instance for functions. Indeed if we look at the source code, we see

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

Using this newly obtained information we can evaluate the addStuff function ourselves.

Given the initial expression

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

we substitute using the >>= definition, giving us (in the following {}, [], () just illustrate different depth of ())

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

simplify the second-to-last term inside the outermost lambda

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

apply {r1 * 2} to {\a -> ...}

\r1 -> {(+10) >>= \b -> return ((r1 * 2) + b)} r1 

substitute remaining >>= with its definition again

\r1 -> {\r2 -> [\b -> return (r1 * 2 + b)] [(+10) r2] r2} r1

simplify second-to-last term inside inner lambda

\r1 -> {\r2 -> [\b -> return (r1 * 2 + b)] [r2 + 10] r2} r1

apply [r2 + 10] to {\b -> ...}

\r1 -> {\r2 -> [return (r1 * 2 + (r2 + 10))] r2} r1

apply r1 to {\r2 -> ...}

\r1 -> {return (r1 * 2 + r1 + 10) r1}

substitute return with its definition

\r1 -> {const (r1 * 2 + r1 + 10) r1}

evaluate const x _ = x

\r1 -> {r1 * 2 + r1 + 10}

prettify

\x -> 3 * x + 10

finally we get

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