Why list monad combines in that order?

Question

I was reading about list monads and encountered:

[1,2] >>= \n -> ['a','b'] >>= \ch -> return (n,ch)

it produces

[(1,'a'),(1,'b'),(2,'a'),(2,'b')]

Here's how I understand it:

Implicit parentheses are:

([1,2] >>= \n -> ['a','b']) >>= (\ch -> return (n,ch))

([1,2] >>= \n -> ['a','b']) should give [('a',1),('b',1),('a',2),('b',2)]

because

instance Monad [] where  
  return x = [x]  
  xs >>= f = concat (map f xs)   -- this line
  fail _ = []

so concat (map f xs) is concat (map (\n -> ['a','b']) [1,2]) which should produce [('a',1),('b',1),('a',2),('b',2)] - quite the opposite of the actual output.

Then I don't understand >>= (\ch -> return (n,ch)) part - I think that n here has no sense. That specific reasoning is flawed, could you please explain how that expression([1,2] >>= \n -> ['a','b'] >>= \ch -> return (n,ch)) is computed step-by-step?

note that `[1, 2] >>= \n -> ['a', 'b'] == "abab"`, not `[('a',1),('b',1),('a',2),('b',2)]`. — Adam Smith, Nov 20 '17 at 17:21
No, it's `[1,2] >>= (\n -> ['a','b'] >>= (\ch -> return (n,ch)))` — chi, Nov 20 '17 at 17:23
You may be interested in ["How to automatically parenthesize arbitrary haskell expressions?"](https://stackoverflow.com/q/40331179/3072788) — Alec, Nov 20 '17 at 17:23
an interesting tidbit: for lists `join == concat` and `map == fmap`, so `f =<< xs = concat (map f xs) == join (fmap f xs)`, as it indeed [should be](https://stackoverflow.com/a/11249714/849891) (check out other answers there as well). :) — Will Ness, Nov 20 '17 at 18:06

score 10 · Accepted Answer · answered Nov 20 '17 at 17:23

10

Your implicit parentheses are wrong. The way you have it, the n parameter to the first lambda would not be in scope in the return. It is more like:

([1,2] >>= (\n -> ['a','b'] >>= (\ch -> return (n,ch))))

Which becomes:

concatMap (\n -> concatMap (\ch -> [(n,ch)]) ['a','b']) [1,2]

answered Nov 20 '17 at 17:23

pat

12,587
1
23
52

That last line I was seeking. – Bulat M. Nov 20 '17 at 18:19

Will Ness · Answer 2 · 2020-03-02T07:36:47.553

No, you're using wrong parenthesization. It's nested to the right, so that

[1,2] >>= \n -> ['a','b'] >>= \ch -> return (n,ch)  
=
[1,2] >>= (\n -> ['a','b'] >>= (\ch -> return (n,ch) ))
=
do { n <- [1,2]
   ; do { ch <- ['a','b']
        ; return (n,ch) }}
=
for n in [1,2]:              -- pseudocode
    for ch in ['a','b']:
        return (n,ch)
=
[ r | n <- [1,2], ch <- ['a','b'], r <- [(n,ch)] ]    -- return == (:[])
=
[ (n,ch) | n <- [1,2], ch <- ['a','b'] ]
=
pure (,) <*> [1,2] <*> ['a','b']      -- using list applicative
=
[(1,'a'), (1,'b'), (2,'a'), (2,'b')]

and the innermost list is "spinning" the fastest, like in a car's odometer.

You are absolutely right, with the wrong parenthesization the n binding would make no sense. It is precisely for that reason that it must associate to the right, to make the nested binding possible; for the nested computations are the essence of the monad:

[ foo x   | x <- xs ]           -- functor : amendable computations
[ bar x y | x <- xs AND y <- ys ]     -- applicative : combinable computations
[ baz x y | x <- xs, y <- foo x ]         -- monad : reinterpretative computations

(and yes, omitting parentheses in learning material is the root of all evil... not really, but still...)

score 3 · Answer 3 · answered Nov 20 '17 at 17:25

Implicit parentheses are:
([1,2] >>= \n -> ['a','b']) >>= (\ch -> return (n,ch))

This is wrong. \ has the lowest precedence and thus extends to the end of the expression. So the parentheses are:

[1,2] >>= (\n -> ['a','b'] >>= (\ch -> return (n,ch)))

([1,2] >>= \n -> ['a','b']) should give [('a',1),('b',1),('a',2),('b',2)]

As you can see from the above parenthesization ([1,2] >>= \n -> ['a','b']), isn't actually a subexpression of the given expression. But if it were, its result would be ['a', 'b', 'a', 'b']. n is not actually used anywhere in the expressions ['a', 'b'], so there's no way the numbers could appear in the result.

Then I don't understand >>= (\ch -> return (n,ch)) part - I think that n here has no sense.

Given your parenthesization n would indeed be undefined there. However given the proper parenthesization it should be clear where n comes from: We're still inside the \n -> ... function, so n still refers to the argument of that function, namely the current element of the [1, 2] list.

score 1 · Answer 4 · answered Nov 20 '17 at 17:25

1

You're wrong about the semantics of concat (map (\n -> ['a','b']) [1,2]). I've done a step by step evaluation of it below.

concat (map (\n -> ['a','b']) [1,2])

concat [(\n -> ['a','b']) 1, (\n -> ['a','b']) 2]

concat [['a','b'], ['a','b']]

['a','b','a','b']

The last bind is what is used to actually make it a list of tuples.

answered Nov 20 '17 at 17:25

Izaak Weiss

1,281
9
18

answers above told me that this order of parentheses is wrong, so your evaluation is not relevant. Thanks. anyway. – Bulat M. Nov 20 '17 at 18:14

Why list monad combines in that order?

4 Answers4

Linked