Haskell >> operator with two lists

Question

For a college assignment I am learning Haskell and when reading about the do-notation and sequencing with >>= and >> I came across this behaviour that I did not expect.

[1,2,3] >> [1] -- returns [1,1,1]

Can anyone explain why every element of the first array is replaced by the elements of the second array? It seems like the list is concatenated in some way, while I expected the result of the first expression to be completely ignored, thus I would expect [1] as the result.

Thanks a lot in advance.

leftaroundabout · Accepted Answer · 2022-02-18T16:03:51.680

7

The “result” is in this case the values contained in [1,2,3], which are indeed ignored. What >> does not ignore is the context, which for the list monad is the shape (i.e. length) of the list. This can't be ignored, because we must have x >>= pure ≡ x, i.e.

Prelude> [1,2,3] >>= pure
[1,2,3]
Prelude> [1,2,3] >>= \n -> [n]
[1,2,3]
Prelude> [1,2,3] >>= \n -> [1]
[1,1,1]
Prelude> [1,2,3] >>= \_ -> [1]
[1,1,1]
Prelude> [1,2,3] >> [1]
[1,1,1]

An example with length>1 on the RHS:

[1,2,3] >>= \n -> [n, n+10]
[1,11,2,12,3,13]
Prelude> [1,2,3] >>= \n -> [100, 10]
[100,10,100,10,100,10]
Prelude> [1,2,3] >> [100, 10]
[100,10,100,10,100,10]

edited Feb 18 '22 at 16:03

answered Feb 18 '22 at 15:54

leftaroundabout

117,950
5
174
319

1

I might also add another example of `[1,2,3] >> [5,6]` for contrast – Fyodor Soikin Feb 18 '22 at 16:01
After reading your comment three times over I finally understood what it does, thanks a lot for the examples! – Sebastiaan Steenbrink Feb 18 '22 at 17:38

score 3 · Answer 2 · edited Feb 19 '22 at 07:42

There are several equivalent ways of writing [1,2,3] >> [1]:

do [1,2,3]
   return 1

[ x | _ <- [1,2,3], x <- [1] ]

[ 1 | _ <- [1,2,3] ]

[1,2,3] >>= \_ -> [1]

concatMap (const [1]) [1,2,3]

concat (map (const [1]) [1,2,3])

concat ([1,2,3] $> [1])

It replaces every element of [1..3] with [1] and then collapses it:

  concatMap (\_ -> [1]) [1,2,3]
= concat (map (\_ -> [1]) [1,2,3])
= concat [[1],[1],[1]]
= [1,1,1]

It completely ignores the elements of [1,2,3], just using the shape (length). Look what happens if we replace them with undefined:

> do [undefined, undefined, undefined]; return 1
[1,1,1]

Will Ness · Answer 3 · 2022-02-19T15:26:17.497

The results of the first computation are indeed ignored.

Monads can be seen as generalized nested loops. What you have can be written in pseudocode as

  for y in [1,2,3]:
    for x in [1]:     -- for x in ((\_ -> [1]) y):
      yield x

Both y and x are in scope at the innermost level. y's value is indeed ignored.

Still for each y in [1,2,3] each x in [1] is produced, thus defining the overall computation. For lists this means the results produced one by one by the combined computation as a whole are the results produced one by one at the innermost level. Sounds trivial, isn't it.

How exactly this is implemented is an implementational detail. Seeing the lists as data this means splicing the results of the inner computations in place, flattening the list of lists into a one-level list, appending the inner lists together. concatMap is widely known as flatMap in other languages:

   [  1,   2,   3  ]
     [1]  [1]  [1]
  -------------------
  [   1,   1,   1  ]

^{Related answers: Why >> duplicates right-hand side operand , Map and flatMap , How does Monad on list work? , Why list monad combines in that order? , mapM with const functions in Haskell , under the hood reason we can use nested loops in list comprehensions , Generalizing prime pairs in SICP.}

Haskell >> operator with two lists

3 Answers3