Question

I'm currently preparing for my final exam regarding Haskell, and I am going over the Monads and we were giving an example such as:

Given the following definition for the List Monad:

``````instance Monad [] where
m >>= f = concatMap f m
return x = [x]
``````

where the types of `(>>=)` and `concatMap` are

`````` (>>=) :: [a] -> (a -> [b]) -> [b]
concatMap :: (a -> [b]) -> [a] -> [b]
``````

What is the result of the expression?

``````> [1,2,3] >>= \x -> [x..3] >>= \y -> return x
[1, 1, 1, 2, 2, 3] //Answer
``````

Here the answer is different from what I thought it to be, now we briefly went over Monads, but from what I understand `(>>=)` is called bind and could be read in the expression above as "applyMaybe". In this case for the first part of bind we get `[1,2,3,2,3,3]` and we continue to the second part of the bind, but `return x` is defined to return the list of x. Which should have been `[1,2,3,2,3,3]`. However, I might have misunderstood the expression. Can anyone explain the wrong doing of my approach and how should I have tackled this. Thanks.

Show source

1. First, let's be clear how this expression is parsed: lambdas are syntactic heralds, i.e. they grab as much as they can to their right, using it as the function result. So what you have there is parsed as

``````[1,2,3] >>= (\x -> ([x..3] >>= \y -> return x))
``````

The inner expression is actually written more complicated than it should be. `y` isn't used at all, and `a >>= \_ -> p` can just be written as `a >> p`. There's an even better replacement though: generally, the monadic bind `a >>= \q -> return (f q)` is equivalent to `fmap f a`, so your expression should really be written

``````[1,2,3] >>= (\x -> (fmap (const x) [x..3]))
``````

or

``````[1,2,3] >>= \x -> map (const x) [x..3]
``````

or

``````[1,2,3] >>= \x -> replicate (3-x+1) x
``````

At this point it should be pretty clear what the result will be, since `>>=` in the list monad simply maps over each element and concatenates the results.

2. this case for the first part of bind we get [1,2,3,2,3,3]

Correct.

and we continue to the second part of the bind, but "return x" is defined to return the list of x. Which should have been [1,2,3,2,3,3].

Note that, in...

``````[1,2,3] >>= \x -> [x..3] >>= \y -> return x
``````

... `x` is bound by (the lambda of) the first `(>>=)`, and not by the second one. Some extra parentheses might make that clearer:

``````[1,2,3] >>= (\x -> [x..3] >>= (\y -> return x))
``````

In `\y -> return x`, the values bound to `y` (that is, the elements of `[1,2,3,2,3,3]`) are ignored, and replaced by the corresponding values bound to `x` (that is, the elements of the original list from which each `y` was generated). Schematically, we have:

``````[1,     2,   3] -- [1,2,3]
[1,2,3, 2,3, 3] -- [1,2,3] >>= \x -> [x..3]
[1,1,1, 2,2, 3] -- [1,2,3] >>= \x -> [x..3] >>= \y -> return x
``````