Haskell list comprehension creating all possible combinations of values

1
votes

I want to create a list of lists, which contains all possible combinations of values inside the smaller lists with size n

For example, let's say I have the list [1,2,3] and I have n equal to 2. The output would be: [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]

It sounds pretty easy for a fixed N, but how would it work for an undetermined value of N?

So far I've tried:

[[x,y] | x <- [1,2,3], y <- [1,2,3]]

and this works for a fixed n of 2. But I do not know how to make it depend on N.

1
listhaskelllist-comprehensioncombinations

1 Answers

4
votes

There's a library function to do this: it's replicateM in the Control.Monad package:

> import Control.Monad
> replicateM 2 [1,2,3]
[[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]
> replicateM 5 [1,2,3]
[[1,1,1,1,1],[1,1,1,1,2],[1,1,1,1,3],[1,1,1,2,1],....]

However, if you're interested in defining this yourself, you're right that this can't really be done for undetermined N using a single list comprehension. Instead, you need to write a recursive version. The idea is that if we already had the answer for some n, like n=2:

[[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]

then we could generate the answer for the next n (n=3) by prefixing all these lists with the first element:

[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3]

and similarly with the second and third elements:

[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3]
[3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]

to generate the full result list.

As a list comprehension, it would look like:

combos n lst = [x:xs | x <- lst, xs <- combos (n-1) lst]

We also need a base case for the recursion. We can use:

combos 0 lst = [[]]

The full definition is:

combos :: Int -> [a] -> [[a]]
combos 0 lst = [[]]
combos n lst = [x:xs | x <- lst, xs <- combos (n-1) lst]

and this works as intended:

> combos 3 [1,2,3]
[[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3]
,[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3]
,[3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]]