Haskell method that creates infinite list with all combinations of a given list

Question

My Problem is that I want to create a infinite list of all combinations of a given list. So for example:

infiniteListComb [1,2] = [[],[1],[2], [1,1],[1,2],[2,1],[2,2], [1,1,1], ...].

other example:

infiniteListComb [1,2,3] = [[], [1], [2], [3], [1,1], [1,2], [1,3], [2,1],[2,2],[2,3],[3,1],[3,2],[3,3],[1,1,1], ...].

Reminds me of power sets, but with lists with same elements in it. What I tried: I am new in Haskell. I tried the following:

infiniteListComb: [x] -> [[x]]
infiniteListComb [] = []
infiniteListComb [(x:xs), ys] = x : infiniteListComb [xs,ys] 

But that did not work because it only sumed up my list again. Has anyone another idea?

Answer 1

We iteratively add the input list xs to a list, starting with the empty list, to get the ever growing lists of repeated xs lists, and we put each such list of 0, 1, 2, ... xs lists through sequence, concatting the resulting lists:

infiniteListComb :: [a] -> [[a]]
infiniteListComb xs  =  sequence =<< iterate (xs :) []
            -- = concatMap sequence (iterate (xs :) [])

e.g.

> take 4 (iterate ([1,2,3] :) [])
[[],[[1,2,3]],[[1,2,3],[1,2,3]],[[1,2,3],[1,2,3],[1,2,3]]]

> sequence [[1,2,3],[1,2,3]]
[[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]

> take 14 $ sequence =<< iterate ([1,2,3] :) []
[[],[1],[2],[3],[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3],[1,1,1]]

The essence of Monad is flatMap (splicing map).

sequence is the real magician here. It is equivalent to

sequence [xs, ys, ..., zs] =
  [ [x,y,...,z] | x <- xs, y <- ys, ..., z <- zs ]

or in our case

sequence [xs, xs, ..., xs] =
  [ [x,y,...,z] | x <- xs, y <- xs, ..., z <- xs ]

Coincidentally, sequence . replicate n is also known as replicateM n. But we spare the repeated counting from 0 to the growing n, growing them by 1 at a time instead.

We can inline and fuse together all the definitions used here, including

concat [a,b,c...] = a ++ concat [b,c...]

to arrive at a recursive solution.

---

Another approach, drawing on answer by chi,

combs xs = ys where 
    ys = [[]] ++ weave [ map (x:) ys | x <- xs ] 
    weave ((x:xs):r) = x : weave (r ++ [xs])

There are many ways to implement weave.