List comprehension in Haskell

Question

I've been using the following code to get all combinations of a pre-determined amount of numbers:

getList x = [ [a,b,c] | a <- [1..x], b <- [1..x], c <- [1..x]]

This was fine to begin with, but I'm looking to expand the program to handle very large lists, and I keep thinking there must be a better way to do this. How would I create a function that takes the same parameter x as here, and also another parameter for how many items the sublists have. For four items I would go and modify the code:

getList x = [ [a,b,c,d] | a <- [1..x], b <- [1..x], c <- [1..x], d <- [1..x]]

It doesn't need to be a list comprehension. Thank you for any help.

Answer 1

I believe what you want would be the replicateM function in Control.Monad.

The list monad is based on "trying all possible combinations", and plain replicate creates a list by repeating an item some number of times. So the result of replicateM is, given some list of possible values, a list of all possible ways to select an item from that list some number of times.

For example:

> replicateM 2 [0, 1]
[[0,0],[0,1],[1,0],[1,1]]
> replicateM 3 [0, 1]
[[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]

So to extend your function to arbitrary repetitions, you'd use something like:

getListN n x = replicateM n [1..x]

...where your original getList would be equivalent to getListN 3.

Answer 2

In case, anyone likes a non-Monadic-solution to understand to inner workings (although, the soliution via replicateM is great!):

getListN n = foldl (\ass bs -> [ b:as | b <- bs, as <- ass]) [[]] . replicate n

Essentially, this implementation via foldl works exactly in the same way as the replacatM-solution does.