CODEWITHSUNDEEP
haskell
Kevin Meredith
Kevin Meredith

Reputation: 41919

Understanding `sequence` with `[[a]]` Monad

Given:

Prelude>[ [Just 10, Just 20], [Just 5] ]
[ [Just 10, Just 20], [Just 5] ]

it has type:

Prelude> :t [ [Just 10, Just 20], [Just 5] ]
[ [Just 10, Just 20], [Just 5] ] :: Num a => [[Maybe a]]

I'd like to apply this to sequence:

Prelude> :t sequence
sequence :: Monad m => [m a] -> m [a]

The Monad m in the above List is: [a], as I understand, so I'd expect the types to line up as:

sequence :: Monad m => [m a] -> m [a]
                       [[a]] -> [[a]]

Assuming that's right, then please help me understand the output:

Prelude> sequence [ [Just 10, Just 20], [Just 5] ]
[[Just 10,Just 5],[Just 20,Just 5]]

Upvotes: 0

Views: 75

Answers (2)

bheklilr
bheklilr

Reputation: 54068

It might be easier to do this with just Ints instead of Maybe Ints:

> sequence [[10, 20], [5]]
[[10,5],[20,5]]
it :: [[Int]]

The type signature you deduced is correct, it does have type [[a]] -> [[a]] in this situation, where a ~ Int in my example or a ~ Maybe Int in your example. Whenever using sequence in the list monad, I like to think of it as an N-dimensional Cartesian product. It desugars to something like

sequence [a, b, c] = do
    x <- a
    y <- b
    z <- c
    return [x, y, z]

But with an arbitrary number of elements, not just 3. Some other examples might help explain:

sequence [["a1", "a2", "a3"], ["b1", "b2"], ["c1", "c2", "c3"]]
[
  ["a1","b1","c1"],["a1","b1","c2"],["a1","b1","c3"],["a1","b2","c1"],["a1","b2","c2"],["a1","b2","c3"],
  ["a2","b1","c1"],["a2","b1","c2"],["a2","b1","c3"],["a2","b2","c1"],["a2","b2","c2"],["a2","b2","c3"],
  ["a3","b1","c1"],["a3","b1","c2"],["a3","b1","c3"],["a3","b2","c1"],["a3","b2","c2"],["a3","b2","c3"]
]

If you study this output closely, you'll see that we have each element of the as matched with each element of the bs and each element from the cs. Since there are 3 as, 2 bs, and 3 cs, there are 3*2*3 == 18 elements in the output.

Upvotes: 3

MathematicalOrchid
MathematicalOrchid

Reputation: 62848

What sequence does is to turn something like

[foo, bar, baz]

into something like

do
  x <- foo
  y <- bar
  z <- baz
  return [x, y, z]

In your case, we have

do
  x <- [Just 10, Just 5]
  y <- [Just 5]
  return [x, y]

which is the same as

foreach x in [Just 10, Just 5]
  foreach y in [Just 5]
    return [x, y]

in psuedo-OO syntax.

It should now be fairly obvious why you get the result you do.

Upvotes: 3

Related Questions