Result of expressions in Haskell with monads

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
| haskell   | monads   2016-12-12 00:12 2 Answers

Answers ( 2 )

  1. 2016-12-12 00:12

    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. 2016-12-12 00:12

    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
    
◀ Go back