Haskell - List of combinations of elements from list of lists

Question

Say I have some list of lists [[a, b], [c], [d, e, f], ...] where the lists in the list can be any length. I've sorted the list such that the shortest lists come first, and I want to generate a list of all combinations of elements in the lists such that I get a list [[a, c, d, ...], [a, c, e, ...], [a, c, f, ...], [b, c, d, ...], ...], i.e. the combinations are generated by changing the element picked from the last lists first, moving up lists to change elements similar to counting.

Using this list, I'll take the head of the list to use lazy evaluation as I only need 1 list that satisfies the predicate. How do I generate the list?

Answer 1

Yes, this is a special case of sequenceA :: (Applicative f, Traversable t) => t (f a) -> f (t a):

Prelude> sequenceA ["ab", "c", "def"]
["acd","ace","acf","bcd","bce","bcf"]

Here we thus set f ~ [], t ~ [] and a ~ Char for example. SequenceA is here thus equivalent to:

-- sequenceA for f ~ [] and t ~ []
sequenceAList [] = [[]]
sequenceAList (c:cs) = (:) <$> c <*> sequenceAList cs

For a single item sequenceA ["def"] is thus equivalent to:

sequenceA ["def"] = (:) <$> "def" <*> [[]]

which thus takes all elements of "def", the Characters 'd', 'e' and 'f', and then combines it with all elements of the list [[]] (only []), which thus yields "d", "e", and "f".

then for sequenceA ["c", "def"] it is thus equivalent to:

sequenceA ["c", "def"] = (:) <$> "c" <*> ["d", "e", "f"]

which thus yields: ["cd", "ce", "cf"], and finally:

sequenceA ["ab", "c", "def"] = (:) <$> "ab" <*> ["cd", "ce", "cf"]

will produce:

sequenceA ["ab", "c", "def"] = ["acd", "ace", "acf", "bcd", "bce", "bcf"]

Answer 2

You tagged this with list comprehensions:

pCombs pred xs = take 1 [ ys | ys <- sequenceAL xs, pred ys]

sequenceAL (xs:t)     = [ x : ys  | x <- xs, ys <- sequenceAL t]
sequenceAL []         = [ [] ]
sequenceAL [xs]       = [ [x]     | x <- xs]
sequenceAL [xs,ys]    = [ [x,y]   | x <- xs, y <- ys]
sequenceAL [xs,ys,zs] = [ [x,y,z] | x <- xs, y <- ys, z <- zs]
--- ....

List comprehensions are just like nested loops.

As can be seen, sequenceAL (which is sequenceA specialized to lists, []) enumerates a Cartesian product of all the sequences in its argument list (the last "spinning" the fastest). Since the length of that list is arbitrary, the elements are collected into lists, not tuples.

We could also define

sequenceAL (xs:t)     = [ x : ys  | ys <- sequenceAL t, x <- xs]

with the first element in the result lists spinning the fastest. The order of enumeration might not matter that much, and it could help with the memory issues. See haskell running out of memory with finite lists for more.

Also, if your predicate can be applied to parts of the resulting lists to weed out some of the lists in advance, it should be done, weaving the filtering with the generation steps, to reduce the enumeration space. In other words, test as early as possible, to prevent futile enumerations.