Hi list!

How to transform a list of streams of elements into a stream of lists of elements such that all combinations of exactly one element of each input stream is present? I.e. something like this:


                type Stream a = [a]

                      tr :: [Stream e] -> Stream [e]

                    tr = sequence

But I want the order of the output lists so the ones with early elements come first. The above starts with the first elements from each stream but does not treat the streams fairly. All the elements of the last stream are used before the next element of the second last stream is used, i.e.


                > tr [[1..3], [1..2], [1..3]]

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

I don't want the third element of one stream before I have seen all the combinations of the first two elements of each stream and so on. In this case I want something like this:


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

Also [2,1,1] comes before [1,2,2] because the former contains two first element and one second element while the latter contains only one first element and two second elements.

The number of streams are fairly low but the sequences can be very long (almost infinte :) and I want the first results without having to go though a full stream. Also the streams may vary in length so one stream may ran out of elements before the others. If that happens, the non-empty streams should contrbute fairly with new elements, i.e:


                > sequence_ $ map print
                    $ tr [[1..2], [3..5]]  -- two times three equals to
                    six combinations

                    [1,3]  -- 1: first and first

                    [1,4]  -- 2: first and second

                    [2,3]  -- 3: second and first

                    [2,4]  -- 4: second and second

                    [1,5]  -- 5: first and third

                    [2,5]  -- 6: second and third

Note, I'm not just interested to handle infinite streams (nor infinite number of streams) using some diagonal algorithm. I have looked at the Omega library. But it doesn't return the combinations in wanted order.

If someone still wonder about the output ordering, the following program may help:


                import Data.List (sort,
                    sortBy)

                    

                    type Stream a =
                  [a]

                    

                    tr :: Ord e => [Stream e] -> Stream [e]

                    tr = sortBy myOrder .
                    sequence

                         where myOrder ::
                  Ord e => [e] -> [e] -> Ordering

                           myOrder xs ys =
                    compare (reverse $ sort xs)
                  (reverse $ sort ys)

                    

                    main = sequence_ $ map print $ tr [[1..3],
                  [1..2], [1..3], [1..4]]

But this of course is not a valid solution since it inspects every combinations before producing any output.

Attached the sample output.