CODEWITHSUNDEEP
haskellfunctional-programminglist-comprehensionnested-listscombinatorics
Ammar Tarajia
Ammar Tarajia

Reputation: 189

Haskell - List of combinations of elements from list of lists

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?

Upvotes: 5

Views: 455

Answers (2)

Will Ness
Will Ness

Reputation: 71065

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.

Upvotes: 1

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476574

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"]

Upvotes: 6

Related Questions