Haskell List comprehensions infinite list problem

767 views Asked by At

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...]
2

There are 2 answers

2
Will Ness On BEST ANSWER

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.

0
fp_mora On

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.