Nested cartesian product of Haskell lists

This can be solved recursively. First, the Cartesian product of nothing is {∅}:

cart [] = [[]]

(Or define just the 1-element form if the empty product is invalid:

cart [x] = [[i] | i <- [0 .. x-1]]

)

Then, the Cartesian product of x:xs can be written as

cart (x:xs) = [i:rest | i <- [0 .. x-1], rest <- cart xs]

---

In general, if you what to write a function f that requires the list's length N, try to think of a way to make f(N) depends on smaller lists e.g. f(N - 1) only, then solve the base case f(0) or f(1) etc. This transforms the problem into a recursion that can be easily solved.

Umm..

cart = sequence . map (enumFromTo 0 . subtract 1)

It's reasonable to expect that a [[a]] -> [[a]] function doing what we expect already exists in the library. So if one is not familiar with sequence, finding it is a simple matter of hoogling it.

Edit: as newacct pointed out:

cart = mapM (enumFromTo 0 . subtract 1)

This can also be found by feeding the previous solution to HLint.