How does the List monad work in this example?

Question

The List monad has return x = [x]. So why in the following example is the result not [(["a", "b"], [2, 3])]?

> pairs a b = do { x <- a; y <- b; return (x, y)}
> pairs ["a", "b"] [2,3]
[("a",2),("a",3),("b",2),("b",3)]

because - the list monad also has a `(>>=) = concatMap` bind operation which you use implicitly with `(<-)`. It is best you try to de-sugar the do notation yourself and see how far you get. The gist is that you in each `x <- a` you bind each *element* of the monad and not the whole list. — epsilonhalbe, Feb 24 '18 at 08:59
Because the `return` has as argument `(x, y)`, so it produces `[(x,y)]`. — Willem Van Onsem, Feb 24 '18 at 09:33
`pairs = return` would provide your expected value. `<-` is *not* just assignment; it's more of an *extraction* operator. — chepner, Feb 24 '18 at 16:48
Because `do` notation doesn't do what you think it does. It doesn't just run things in order. — user253751, Feb 26 '18 at 05:03

score 5 · Accepted Answer · answered Feb 24 '18 at 10:18

Let us first analyze and rewrite the function pairs:

pairs a b = do { x <- a; y <- b; return (x, y)}

Here we thus have a monad. We use do as syntactical sugar. But the compiler rewrites this to:

pairs a b = a >>= (\x -> b >>= (\y -> return (x, y)))

Or in a more canonical form:

pairs a b = (>>=) a (\x -> (>>=) b (\y -> return (x, y)))

Now the list monad is defined as:

instance Monad [] where
    return x = [x]
    (>>=) xs f = concatMap f xs

So we have written:

pairs a b = concatMap (\x -> concatMap (\y -> [(x, y)]) b) a

So we thus take as input two lists a and b, and we perform a concatMap on a with as function (\x -> concatMap (\y -> [(x, y)]) b). In that function we perform another concatMap on b with as function \y -> [(x, y)].

So if we evaluate this with pairs ["a", "b"] [2,3] we get:

   pairs ["a", "b"] [2,3]
-> concatMap (\x -> concatMap (\y -> [(x, y)]) [2,3]) ["a", "b"]
-> concatMap (\y -> [("a", y)]) [2,3] ++ concatMap (\y -> [("b", y)]) [2,3]
-> [("a", 2)] ++ [("a", 3)] ++ [("b", 2)] ++ [("b", 3)]
-> [("a", 2), ("a", 3), ("b", 2), ("b", 3)]

Thanks for spelling it out. My confusion was that <- is not just an assignment, and in fact for the List monad involves mapping over following operations. I think your answer would be improved greatly by skipping over concatMap and using concat and map directly, as that's an extra level of abstraction someone struggling with this will have to deal with. — Matt Joiner, Feb 25 '18 at 06:41

Will Ness · Answer 2 · 2018-03-05T07:54:54.427

In general,

pairs a b = do { x <- a; y <- b; return (x, y) }  
          = do { x <- a;
                    do { y <- b; 
                            do { return (x, y) }}}

means, in pseudocode,

pairs( a, b) {  for x in a do: 
                     for y in b do: 
                                 yield( (x, y) ); 
             }

whatever the "for ... in ... do" and "yield" mean for the particular monad. More formally, it's

          = a  >>= (\x ->
                    do { y <- b;                          -- a >>= k  ===
                            do { return (x, y) }})        -- join (k <$> a)
          = join ( (<$> a)                                --  ( a       :: m a
                   (\x ->                                 --    k       ::   a ->   m b
                    do { y <- b;                          --    k <$> a :: m       (m b) )
                            do { return (x, y) }}) )      --            :: m          b

( (<$>) is an alias for fmap).

For the Identity monad, where return a = Identity a and join (Identity (Identity a)) = Identity a, it is indeed

pairs( {Identity, a}, {Identity, b}) {  x = a; 
                                        y = b; 
                                        yield( {Identity, {Pair, x, y}} ); 
                                     }

For the list monad though, "for" means foreach, because return x = [x] and join xs = concat xs:

-- join :: m (m a) -> m a
-- join :: [] ([] a) -> [] a
-- join :: [[a]] -> [a]
join = concat

and so,

join    [ [a1, a2, a3, ...],
          [b1, b2, b3, ...],
           .....
          [z1, z2, z3, ...] ]
=
        [  a1, a2, a3, ... ,
           b1, b2, b3, ... ,
            .....
           z1, z2, z3, ...  ]

Monadic bind satisfies ma >>= k = join (fmap k ma) where ma :: m a, k :: a -> m b for a Monad m. Thus for lists, where fmap = map, we have ma >>= k = join (fmap k ma) = concat (map k ma) = concatMap k ma:

m >>= k  =  [ a,        = join [ k a,   = join [ [ a1, a2, ... ],  =  [  a1, a2, ... ,
              b,                 k b,            [ b1, b2, ... ],        b1, b2, ... ,
              c,                 k c,            [ c1, c2, ... ],        c1, c2, ... ,
              d,                 k d,            [ d1, d2, ... ],        d1, d2, ... ,
              e,                 k e,            [ e1, e2, ... ],        e1, e2, ... ,
             ... ] >>= k         ...  ]          ...............  ]      ...........   ]

which is exactly what nested loops do. Thus

pairs ["a",                                   -- for x in ["a", "b"] do:
       "b"] [2, 3]                            --          for y in [2, 3] do:
=                                             --                     yield (x,y)
      ["a", 
       "b"] >>= (\x-> join (fmap (\y -> return (x,y)) [2, 3]) )
=
      ["a", 
       "b"] >>= (\x-> concat (map (\y -> [ (x,y) ]) [2, 3]) )
=
join [ "a"  &   (\x-> concat ((\y -> [ (x,y) ]) `map` [2, 3]) ),      -- x & f = f x
       "b"  &   (\x-> concat ((\y -> [ (x,y) ]) `map` [2, 3]) ) ]     
=
join [              concat ((\y -> [ ("a",y) ]) `map` [2, 3])  ,    
                    concat ((\y -> [ ("b",y) ]) `map` [2, 3])   ]     
=
join [ concat [ [("a", 2)], [("a", 3)] ] ,    -- for y in [2, 3] do: yield ("a",y)
       concat [ [("b", 2)], [("b", 3)] ] ]    -- for y in [2, 3] do: yield ("b",y)
=
join [        [  ("a", 2) ,  ("a", 3)  ] ,
              [  ("b", 2) ,  ("b", 3)  ] ]
=
     [           ("a", 2) ,  ("a", 3)    ,
                 ("b", 2) ,  ("b", 3)    ]

Loop unrolling is what nested loops do ⁄ are, and nested computations are the essence of Monad.

It is also interesting to notice that

 join                =                      =   [a1] ++            =  [a1] ++ join
  [ [ a1, a2, ... ],    [ a1, a2, ... ] ++          [a2, ... ] ++         [ [a2, ...],
    [ b1, b2, ... ],    [ b1, b2, ... ] ++     [ b1, b2, ... ] ++      [ b1, b2, ...],
    [ c1, c2, ... ],    [ c1, c2, ... ] ++     [ c1, c2, ... ] ++      [ c1, c2, ...],
    [ d1, d2, ... ],    [ d1, d2, ... ] ++     [ d1, d2, ... ] ++      [ d1, d2, ...],
    [ e1, e2, ... ],    [ e1, e2, ... ] ++     [ e1, e2, ... ] ++      [ e1, e2, ...],
    ............... ]   ...............        ...............         ..............  ]

which goes to the heart of the "nested loops ⁄ yield" analogy. Monads are higher order monoids, "what's the problem?"

How does the List monad work in this example?

2 Answers2

Linked