List comprehension in Haskell of any order or dimension

Question

Consider the following program.

chars = [" "] ++ ["A"] ++ ["B"] ++ (repeat "ABCD")

f :: Int -> [(Char,Int)]
f n = (,) <$> (chars !! n) <*> [1..3]

g :: Int -> [[(Char,Int)]]
g 1 = (\a     -> [a    ]) <$> (f 1)
g 2 = (\a b   -> [a,b  ]) <$> (f 1) <*> (f 2)
g 3 = (\a b c -> [a,b,c]) <$> (f 1) <*> (f 2) <*> (f 3)
-- g n = (\x1 x2 ... xn -> [x1,x2,...,xn]) <$> (f 1) <*> (f 2) <*> ... (f n)

How can we write g n generally for all n > 0, without typing out the expansion explicitly as above, ideally only using Prelude (and Control.Applicative if necessary)? Note that f n = f (n-1) for all n>3, hence it may be possible to define g recursively.

The output is like this (ignore the pretty printing):

> g 1
[ [ ( 'A' , 1 ) ] , [ ( 'A' , 2 ) ] , [ ( 'A' , 3 ) ] ]

> g 2
[ [ ( 'A' , 1 ) , ( 'B' , 1 ) ]
, [ ( 'A' , 1 ) , ( 'B' , 2 ) ]
, [ ( 'A' , 1 ) , ( 'B' , 3 ) ]
, [ ( 'A' , 2 ) , ( 'B' , 1 ) ]
, [ ( 'A' , 2 ) , ( 'B' , 2 ) ]
, [ ( 'A' , 2 ) , ( 'B' , 3 ) ]
, [ ( 'A' , 3 ) , ( 'B' , 1 ) ]
, [ ( 'A' , 3 ) , ( 'B' , 2 ) ]
, [ ( 'A' , 3 ) , ( 'B' , 3 ) ]
]

> g 3
[ [ ( 'A' , 1 ) , ( 'B' , 1 ) , ( 'A' , 1 ) ]
, [ ( 'A' , 1 ) , ( 'B' , 1 ) , ( 'A' , 2 ) ]
...
, [ ( 'A' , 3 ) , ( 'B' , 3 ) , ( 'D' , 3 ) ]
]

Answer 1

g n = traverse f [1 .. n]

traverse is in the Prelude (at least for the last few years).

As that's a bit non-obvious, here's how I got there:

1. I noticed you were applying f to the numbers from 1 to n, so I started with map f [1 .. n].

2. This produced a [[(Char, Int)]], which is the desired result type, but it needs to be sort of... turned sideways and multiplied. You want all the lists that come from non-deterministic selection of values in the inner lists. Non-deterministic selection is the essence of the Applicative instance for [], and it turns out that sequence on something of type [[a]] is exactly the operation "produce all the lists you get from combinatorially combining elements from the inner lists". This got me to sequence $ map f [1 .. n].

3. But the pair of sequence and map is common enough that there's an operation that does both at once. sequence . map f === traverse f. So applying that rule simplified the result. traverse f [1 .. n].

Answer 2

g n = mapM f [1..n]

How to get there.

Your examples are equivalently written with List Comprehension syntax as

g :: Int -> [[(Char,Int)]]
g 1 = [[a    ] | a <- (f 1)]
g 2 = [[a,b  ] | a <- (f 1), b <- (f 2)]
g 3 = [[a,b,c] | a <- (f 1), b <- (f 2), c <- (f 3)]
-- g n = [[a,b,c, ... , z] | a <- (f 1), b <- (f 2), ... , z <- (f n)]

which is exactly how sequence is defined, in Monad Comprehension syntax:

sequence [as,bs,cs, ... , zs] = [[a,b,c, ... , z] | a <- as, b <- bs, ... , z <- zs]

and thus

g n = sequence [(f 1), (f 2), ... , (f n)]
    = sequence $ map f [1..n]

which is, in its turn, the definition (or an equivalent thereof) of mapM.

(mapM is also known as traverse now, for types which are also Applicatives, as well as Monads. Haskell lists [] are both, anyway, and I find the name mapM clearer and shorter to type).

---

This has been a public service announcement in favor of the underappreciated List Comprehension and Monad Comprehension syntax.

I'm actually fine with g n = sequence $ map f [1..n], and don't feel any particular urge to shorten it any further, as I find it clearer than both alternatives.

Answer 3

Like this:

g 0 = [[]]
g n = (\xs x -> xs ++ [x]) <$> g (n - 1) <*> f n

Or more complicated, but also more efficient:

g = map ($ []) . go
  where
    go :: Int -> [[(Char,Int)] -> [(Char,Int)]]
    go 0 = [id]
    go n = (\xs x -> xs . (x:)) <$> go (n - 1) <*> f n

This uses Hughes lists/difference lists to avoid the quadratic slowdown of \xs x -> xs ++ [x].