2

I more or less wrapped my head around monads, but i can't deduct how expression

(>>=) id (+) 3

evaluates to 6. It just seems the expression somehow got simplified to

(+) 3 3

but how? How is 3 applied twice? Could someone explain what is happening behind the scenes ?

pharmaz0ne
  • 23
  • 3
  • 3
    The key is to realize that `(+) :: a -> m a` where `m ~ (->) a` which is a monad. (The fact that we need `Num a` for `(+)` does not change this.) Also, `id :: m a` for the same monad. So, we can have `id >>= (+) :: m a`, which is a function `a -> a` and can be applied to `3`. – chi Jun 11 '21 at 10:20

2 Answers2

3

This follows from how >>= is defined for the ((->) r) types:

(f =<< g) x  =  f (g x) x

Thus

(>>=) id (+) 3
=
(id >>= (+)) 3
=
((+) =<< id) 3
=
(+) (id 3) 3
=
3 + 3

see the types:

> :t let (f =<< g) x = f (g x) x in (=<<)
let (f =<< g) x = f (g x) x in (=<<)
        :: (t1 -> (t2 -> t)) -> (t2 -> t1) -> (t2 -> t)

> :t (=<<)
(=<<) :: Monad m => (a -> m b) -> m a -> m b

The types match with

t1 ~ a
(t2 ->) ~ m    -- this is actually ((->) t2)`
t ~ b

Thus the constraint Monad m here means Monad ((->) t2), and that defines the definition of =<< and >>= which get used.

If you want to deduce the definition from the type,

(>>=) :: Monad m => m a -> (a -> m b) -> m b
m ~ ((->) r)

(>>=) :: (r -> a) -> (a -> r -> b) -> (r -> b)
(>>=)    f            g                r =  b
  where
  a  = f r
  rb = g a
  b  = rb r

which after the simplification becomes the one we used above.

And if you want to understand it "with words",

(=<<) :: (Monad m, m ~ ((->) r)) => (a -> m b) -> m a -> m b
(f =<< g) x  =  f (g x) x
  • g is a "monadic value" that "can compute" an "a", represented as r -> a
  • f a calculates a "monadic value" that "can compute" a "b", represented as r -> b,
  • thus \x -> f (g x) x is a monadic value that "can compute" a "b", given an "r".

So these "non-monadic functions" are, in fact, monadic values, which happen to be functions.

Thus in your example, g = id, f = (+), and

  • id is a "monadic value" that "can compute" an "a", an a -> a
  • (+) a calculates a "monadic value" that "can compute" a "b", an a -> b, which b is actually also an a,
  • thus \x -> (+) (id x) x is a monadic value that "can compute" an "a", given an "a":
(>>=) id (+)
=
((+) =<< id) 
=
\x -> (+) (id x) x
=
\x -> (+)     x  x
Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • Not sure you need the intermediate translation to `=<<`, but perhaps I am missing something? – shree.pat18 Jun 11 '21 at 10:12
  • 1
    @shree.pat18 that's the definition that I remember. :) its type `(=<<) :: Monad m => (a -> m b) -> m a -> m b` also aligns nicely with the other types, of `(<$>)` and `(<*>)`, all [ending with the `m a -> m b`](https://stackoverflow.com/a/34561605/849891). – Will Ness Jun 11 '21 at 10:12
  • Thanks, great exhaustive answer, everything makes sense now. Also thanks to @shree.pat18 and chi. I would like to use the chance to ask about type abbreviations, e.g. what r in (->) r stands for and why isn't it t1 or a . What is the difference between t1, a, r etc... I cannot find anything on the web about it. – pharmaz0ne Jun 15 '21 at 07:44
  • 1
    You might find this useful, although I too cant find an authoritative document: https://kowainik.github.io/posts/naming-conventions – shree.pat18 Jun 15 '21 at 07:58
  • 2
    they are just mnemonics of course. `r` on the right of `->` is usually for "result", here on the left of `->` I use it as a reminder of "reader" although of course the whole type is a "reader" from an "environment" so it probably should have been `e` instead (but `e` is also often an "error" as in e.g. `Either e a`). `a`, `t`, etc are for the more generic types. – Will Ness Jun 15 '21 at 12:05
2

Adding some colour to Will's excellent answer.

If we look at the source, we have this:

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

If we rearrange the input expression slightly, we get (id >>= (+)) 3. This now resembles the form shown above. Now fitting the input into the above 'template', we can rewrite the input as \ r -> (+) (id r) r

This is the same expression we arrived at for the final evaluation i.e. (+) (id 3) 3

shree.pat18
  • 21,449
  • 3
  • 43
  • 63