Haskell: All combinations between multiple Strings

Viewed 131

Suppose I have a list of Strings like this:

["aesfa","gwopq","awefg"]

I would want to get all possible combinations between those Strings, something like this:

["aga","agw","age","agf", ... ,"sga","sgw", ... , "aqf","aqg"]

The strings inside the list have all the same lenght, but could be any lenght, and the list could contain different numbers of strings

I tried the following list comprehensions:

-getCombinations (z:zs) = [x:y | x <- z, y <- zs]

This gives me, obviously, a list of the combinations between all the characters of the first string and the rest of the strings (not the characters).

-getCombinations (z:zs) = [x:y | x <- z, y <- getCombinations zs]

This doesnt work if I dont do a pattern matching for the empy list, I did it like this:

getCombinations [] = []

but doing that make the function return always the empty list no matter what

weirdly enough, if I do:

-getCombinations (z:zs) = [x:[y] | x <- z, y <- head zs]

it gives me the combinations between the first two strings

I tried to extend that to get another String and I ended up with this:

getCombinations (z:zs) = [x:[y]++[w] | x <- z, y <- (head zs), w <- (head(tail zs))]

That gave me the combinations of the first three strings

1 Answers

You are actually quite close. The only problem is the case for the empty list:

getCombinations :: [[a]] -> [[a]]
getCombinations [] = []  -- ← empty list
getCombinations (z:zs) = [x:y | x <- z, y <- getCombinations zs]

If you here return the empty list, then that means that eventually getCombinations zs will return the empty list, and thus the list comprehension with that empty list... will also return an empty list.

If you have no strings, then basically there is one combination: the empty string, so you should return:

getCombinations :: [[a]] -> [[a]]
getCombinations [] = [[]]  -- singleton list with an empty string/list
getCombinations (z:zs) = [x:y | x <- z, y <- getCombinations zs]

You actually do not need to implement getCombinations yourself. Due to the Monad instance of list, getCombinations is a special case of sequence :: (Monad m, Traversable t) => t (m a) -> m (t a) :

Prelude> sequence ["aesfa","gwopq","awefg"]
["aga","agw","age","agf","agg","awa","aww","awe","awf","awg","aoa","aow","aoe","aof","aog","apa","apw","ape","apf","apg","aqa","aqw","aqe","aqf","aqg","ega","egw","ege","egf","egg","ewa","eww","ewe","ewf","ewg","eoa","eow","eoe","eof","eog","epa","epw","epe","epf","epg","eqa","eqw","eqe","eqf","eqg","sga","sgw","sge","sgf","sgg","swa","sww","swe","swf","swg","soa","sow","soe","sof","sog","spa","spw","spe","spf","spg","sqa","sqw","sqe","sqf","sqg","fga","fgw","fge","fgf","fgg","fwa","fww","fwe","fwf","fwg","foa","fow","foe","fof","fog","fpa","fpw","fpe","fpf","fpg","fqa","fqw","fqe","fqf","fqg","aga","agw","age","agf","agg","awa","aww","awe","awf","awg","aoa","aow","aoe","aof","aog","apa","apw","ape","apf","apg","aqa","aqw","aqe","aqf","aqg"]
Related