3

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?

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Imker Warze
  • 43
  • 5
  • 1
    The code that you've tried doesn't work because the typing is completely wrong (you take in a list of lists yet your typing states that it should be able to take in a list of any value) and it doesn't even have valid syntax. – Aplet123 Dec 19 '20 at 17:15
  • The pattern `[(x:xs),ys]` matxhes a list of lists, not a list of items. – Willem Van Onsem Dec 19 '20 at 17:17

3 Answers3

5

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.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
4

Others already provided a few basic solutions. I'll add one exploiting the Omega monad.

The Omega monad automatically handles all the interleaving among infinitely many choices. That is, it makes it so that infiniteListComb "ab" does not return ["", "a", "aa", "aaa", ...] without ever using b. Roughly, each choice is scheduled in a fair way.

import Control.Applicative
import Control.Monad.Omega
       
infiniteListComb :: [a] -> [[a]]
infiniteListComb xs = runOmega go
   where
   go =         -- a combination is
      pure []   -- either empty
      <|>       -- or
      (:) <$>   -- a non empty list whose head is
         each xs  -- an element of xs
         <*>      -- and whose tail is
         go       -- a combination

Test:

> take 10 $ infiniteListComb [1,2]
[[],[1],[1,1],[2],[1,1,1],[2,1],[1,2],[2,1,1],[1,1,1,1],[2,2]]

The main downside of Omega is that we have no real control about the order in which we get the answers. We only know that all the possible combinations are there.

chi
  • 111,837
  • 3
  • 133
  • 218
3

Since list Applicative/Monad works via a cartesian-product like system, there's a short solution with replicateM:

import Control.Monad

infiniteListComb :: [x] -> [[x]]
infiniteListComb l = [0..] >>= \n -> replicateM n l
Aplet123
  • 33,825
  • 1
  • 29
  • 55
  • ``infiniteListComb l = [0..] >>= (`replicateM` l)`` – Willem Van Onsem Dec 19 '20 at 17:20
  • How is replicateM defined? – Imker Warze Dec 19 '20 at 17:56
  • @ImkerWarze You can pursue codes [here](https://hackage.haskell.org/package/base-4.14.1.0/docs/src/Control.Monad.html#replicateM). – Akihito KIRISAKI Dec 19 '20 at 17:58
  • @ImkerWarze `replicateM :: Int -> m a -> m [a]` essentially repeats a monadic action a certain amount of times, collecting intermediate results. You can [find it on hackage](https://hackage.haskell.org/package/base-4.14.1.0/docs/Control-Monad.html#v:replicateM), along with its [source code](https://hackage.haskell.org/package/base-4.14.1.0/docs/src/Control.Monad.html#replicateM). – Aplet123 Dec 19 '20 at 17:59