How does `[ (x !! 0, x !! 1) | x <- mapM (const ['A', 'B', 'C'] ) [1..2], head x < head (tail x) ]` work?

Question

I am new to Haskell and wondering how the statement

[ (x !! 0, x !! 1) | x <- mapM (const ['A', 'B', 'C'] ) [1..2], head x < head (tail x) ]

works. (I found it on StackOverflow.) I know what it outputs, but I am not really understanding it.

Answer 1

Well the above expression is likely not what is considered idiomatic Haskell. Probably a better version would be:

[ (x0, x1) | (x0:x1:_) <- mapM (const "ABC") [1..2], x0 < x1 ]

This is cleaner and if the lists in the mapM (const "ABC") would return a list that contains less than two elements (that is here impossible), it will not error.

Probably the core problem here is to understand how mapM works. The expression mapM (const "ABC") [1..2] boils down to:

mapM (\_ -> "ABC") [1..2]

since we do not take the values of the list into account, it is equivalent to:

replicateM 2 "ABC"

This replicateM for 2 can be rewritten as (pseudo-Haskell syntax):

replicateM 2 :: [a] -< [[a]]
replicateM 2 l = do
    x0 <- l
    x1 <- l
    return [x0, x1]

or if we desugar this:

replicateM 2 l = l >>= \x0 -> l >>= \x1 -> return [x0, x1]

For a list, the instance of Monad is implemented as:

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

so that means that for a list this replicateM 2, is implemented as:

replicateM 2 l :: [a] -> [[a]]
replicateM 2 l = concatMap (\x0 -> concatMap (\x1 -> [[x0, x1]]) l) l

or simpler:

replicateM 2 l :: [a] -> [[a]]
replicateM 2 l = concatMap (\x0 -> map (\x1 -> [x0, x1]) l) l

we thus make all possible combinations of two items of the list. This thus means that:

Prelude Control.Monad> replicateM 2 "ABC"
["AA","AB","AC","BA","BB","BC","CA","CB","CC"]

We then use this in list comprehension, and for each of these sublists with two elements, we check if the first element x0 is smaller than the second element with the filter part in the list comprehension (x0 < x1). If that is the case, we yield these elements as a 2-tuple.

It thus creates 2-tuples for each two items in "ABC", if the first element is (strictly) smaller than the second one.

Here we however do a bit "too much work": more than half of the elements will be rejected. We can optimize this by making use of tails :: [a] -> [[a]]:

import Data.List(tails)

[(x0, x1) | (x0:xs) <- tails "ABC", x1 <- xs ]

which yields the same value:

Prelude Control.Monad Data.List> [(x0, x1) | (x0:xs) <- tails "ABC", x1 <- xs ]
[('A','B'),('A','C'),('B','C')]

Answer 2

Ignoring the question of how the original code works, and skipping straight to how to write this more idiomatically, start with myList = ['A', 'B', 'C'].

You can get a list of all the possible pairs; pick an x, pick a y, and put them in a tuple:

> [ (x, y) | x <- myList, y <- myList ]
[('A','A'),('A','B'),('A','C'),('B','A'),('B','B'),('B','C'),('C','A'),('C','B'),('C','C')]

But you only want the ones where x < y:

> [ (x, y) | x <- myList, y <- myList, x < y ]
[('A','B'),('A','C'),('B','C')]

Answer 3

Re-writing it according to the definition mapM f xs = sequence (map f xs), we get

[ (x !! 0, x !! 1) | x <- mapM (const ['A', 'B', 'C'] ) [1..2], head x < head (tail x) ]
=
[ (a, b) | [a,b] <- mapM (const "ABC" ) [1,2], a < b ]
=
[ (a, b) | [a,b] <- sequence ["ABC" | _ <- [1,2]], a < b ]
=
[ (a, b) | [a,b] <- sequence ["ABC", "ABC"], a < b ]
=
[ (a, b) | [a,b] <- [[a,b] | a <- "ABC", b <- "ABC"], a < b ]   -- by def of sequence
=
[ (a, b) | a <- "ABC", b <- "ABC", a < b ]                 -- by associativity of (++)
=
[ (a, b) | a <- "ABC", b <- [b | b <- "ABC", b > a] ]      -- by associativity of (++)
=
[ (a, b) | a <- "A", b <- [b | b <- "ABC", b > a] ]
   ++
   [ (a, b) | a <- "B", b <- [b | b <- "ABC", b > a] ]
     ++
     [ (a, b) | a <- "C", b <- [b | b <- "ABC", b > a] ]
=
[ (a, b) | a <- "A", b <- [b | b <- "BC"] ]                -- by pre-evaluation
   ++
   [ (a, b) | a <- "B", b <- [b | b <- "C"] ]
     ++
     [ ]
=
[ (a, b) | a <- "A", b <- "BC" ]
   ++
   [ (a, b) | a <- "B", b <- "C" ]
=
[ (a, b) | (a:bs) <- ["ABC", "BC"], b <- bs ]

See? List comprehensions are fun. You could play this game too, and find out the answer that way.

Monadic do notation is fun too, and can be written as Monad Comprehensions, which for lists looks and is exactly the same as List Comprehensions.