Haskell List comprehensions infinite list problem

Question

I'm trying to learn Haskell and comprehension lists but cannot find solution on this:

mylist = [x*y | x <- [1..], y <- [1..]]

After my trials the result is something like this

mylist = [1,2,3,4,5,...]

because in list comprehensions, x takes the value 1,and then y changes value repeatedly.

But my goal is to achieve a different assignment so as to have the following result:

mylist = [1,2,2,4,3,3,6.....]

I mean i want the combinations being mixed and not each one apart,because I have a serious problem to have the suitable result.

I will give a more specific example.

I want a list that will have all numbers of this form:

num = 2^x * 3^y

x and y must take all values >= 0.

My approach is the following:

powers = [2^x * 3^y | x <- [0..], y <- [0..]]

But in this way I only take powers of 3, because x is constantly 0.

I tried this one

multiples = nub (merge (<=) powers2 powers3)
powers3 = [2^x * 3^y | x <- [0..], y <- [0..]]
powers2 = [2^x * 3^y | y <- [0..], x <- [0..]]

so as to merge the different ones but again,the values 6,12,etc. are missing - the result is this:

mylist = [1,2,3,4,8,9,16,27,32,64,81...]

So it's just a matter of ordering? I wonder if `[x*y | (x,y) <- zip [1..] [1..]]` would work? Hm, yeah no, that actually goes on both at the same time. Interesting question actually. — Bartek Banachewicz, Jan 08 '19 at 15:38
@BartekBanachewicz Just prepending `sort` does the trick for finite lists. — S.L. Barth is on codidact.com, Jan 08 '19 at 15:43
If you arrange all values `x, y` on a two-dimensional grid, can you show the path in which you intend to iterate through them? — mkrieger1, Jan 08 '19 at 15:50
How about powers3=[2^x*3^y | x <-[0..],y <-[0..x]] Then you can sort the resulting list. — Matteo Ugolotti, Jan 08 '19 at 15:52
Getting things in a different order is easy. But "mixed" is not an order. If you can specify precisely what order you want, we'll be able to help a lot better. — Silvio Mayolo, Jan 08 '19 at 15:52
Maybe this question should be tagged [sorting], but there are already too many tags. — mkrieger1, Jan 08 '19 at 15:56
@mkrieger1 it's not exactly sorting. I have tried for example to make 2 different lists as I writed on the post and mergesort between them but I'm missing results. The problem is on the multiplying.For example for values x=2,y=1, the result will be 2^2*3^1 = 12. In the above case I 'm missing this result. I just want to take the numbers sorted finally,but I guess it's not possible to sort an infinite list. — JAM AICA, Jan 08 '19 at 16:05
I don't understand. It's not sorting, but you tried to mergesort? Can you explain the logic by which the result should be ordered? (See my [earlier comment](https://stackoverflow.com/questions/54095052/haskell-list-comprehensions-infinite-list-problem?noredirect=1#comment95022948_54095052)) — mkrieger1, Jan 08 '19 at 16:08
@mkrieger1 simple increasing order. you probably meant merge, not mergesort. @ Jam-aica yes it can be done. there's a package data-ordlist; and the two tags that I added have many highly relevant entries. :) — Will Ness, Jan 08 '19 at 16:11
OK,I tried the solution of @MatteoUgolotti and that helped but I've not totally solved it. powers2=[2^x*3^y | y <-[0..],x <-[0..y]] powers3=[2^x*3^y | x <-[0..],y <-[0..x]] multiples = nub (merge (<=) powers2 powers3) But merge does not do the job totally. — JAM AICA, Jan 08 '19 at 16:21
@mkrieger1 re "readily known path" this is a not yet solved problem AFAIK. I can explain it by I can't code it. the explanation is: in the 2D grid, draw a line from (1/log 2,0) to (0,1/log 3). Now move it away from (0,0) keeping it parallel to itself. As you come to cross each (i,j) point for whole i and j, output `2^i*3^j`. — Will Ness, Jan 08 '19 at 16:24
@JAMAICA our last two streams, [2^x*3^y | y <-[0..],x <-[0..y]] and the other one, won't be ordered. but merge needs its arguments ordered. that's why it doesn't work. — Will Ness, Jan 08 '19 at 17:02

Will Ness · Accepted Answer · 2019-01-08T17:36:56.110

The code that you show,

multiples = nub (merge (<=) powers2 powers3)
powers3 = [2^x * 3^y | x <- [0..], y <- [0..]]
powers2 = [2^x * 3^y | y <- [0..], x <- [0..]]

is equivalent to

powers3 = [2^x * 3^y | x <- [0], y <- [0..]]
        = [2^0 * 3^y | y <- [0..]]
        = [3^y | y <- [0..]]
powers2 = [2^x * 3^y | y <- [0], x <- [0..]] 
        = [2^x * 3^0 | x <- [0..]]
        = [2^x | x <- [0..]]

so you only produce the powers of 2 and 3, without any mixed multiples. As such, there are guaranteed to be no duplicates in the stream, and the nub was not necessary. And of course it's incomplete.

But let's look at it at another angle. It was proposed in the comments to create a 2D grid out of these numbers:

mults23_2D = [[2^x * 3^y | y <- [0..]] | x <- [0..]]
{-
   1   3   9   27  81  ...
   2   6  18   54  ...
   4  12  36  108  ...
   8  24  72  ...
  16  ...
  .......     
-}

Now we're getting somewhere. At least now none are skipped. We just need to understand how to join them into one sorted, increasing stream of numbers. Simple concat of course won't do. We need to merge them in order. A well-known function merge does that, provided the arguments are already ordered, increasing lists.

Each row produced is already in increasing order, but there are infinitely many of them. Never fear, foldr can do it. We define

mults23 = foldr g [] [[2^x * 3^y | y <- [0..]] | x <- [0..]]
  -- foldr g [] [a,b,c,...] == a `g` (b `g` (c `g` (....)))
 where
 g (x:xs) ys =

Here it is a little bit tricky. If we define g = merge, we'll have a run-away recursion, because each merge will want to know the head element of its "right" (second) argument stream.

To prevent that, we produce the leftmost element right away.

                x : merge xs ys

And that's that.

Bingo! That worked. Make no mistake,the lists I wrote were not the ones you pointed out at start, it was the same with mults23_2D but I had not managed to make that kind of sorting! How could I handle it If I wanted to add in the equation 5^z?( 2^x*3^y*5^z) — JAM AICA, Jan 08 '19 at 18:52
To add 5^z like in the above comment,we just need a double nested foldr... result = foldr g [] [foldr g....] — JAM AICA, Jan 09 '19 at 01:46

fp_mora · Answer 2 · 2021-03-23T17:06:12.370

Tool use

I needed an infinite Cartesian product function. An infinite function must take the diagonals of a table. The pair pattern of a diagonal traversal is

0 0 – 0 1, 1 0 – 0 2, 1 1, 2 0 – 0 3, 1 2, 2 1, 3 0

I love the symmetries but the pattern is counting forward with first digit and backward with second which when expressed in an infinite function is

diag2 xs ys = [ (m,n) | i<- [1..], (m,n) <- zip (take i xs) (reverse.take i $ ys) ]

The infinite generation is just to take any amount however large to work with. What may be important, also is taking a diagonal or triangular number for a complete set. revt n makes a triangular number from you input. If you want 25 elements revt 25 will return 7. tri 7 will return 28 the parameter for take. revt and tri are

tri n = foldl (+) 1 [2..n]
revt n = floor (sqrt (n*2))

Making and using taket is good until you learn the first 10 or so triangular numbers.

taket n xs = take (tri $ revt n) xs

Now, with some tools in place we apply them (mostly 1) to a problem.

[ 2^a * 3^b | (a,b) <- sort.taket 25 $ diag2 [0..] [0..]]

[1,3,9,27,81,243,729, 2,6,18,54,162,486, 4,12,36,108,324, 8,24,72,216, 16,48,144, 32,96, 64]

And it’s a diagonal. The first group is 7 long, the second is 6 long, the second-to-the-last is 2 long and the last is 1 long. revt 25 is 7. tri 7 is 28 the length of the output list.

Haskell List comprehensions infinite list problem

2 Answers2