List comprehension with infinity list

Question

I tried this:

[x * y | x <- [1..], y <- [1..], even x, even y]

This fails to run, the ghci just hangs.

But

[x * y | x <- [1..], even x, y <- [1..], even y]

works.

Can someone explain why? Thanks!

GHCI isn't "hanging", it is simply working on something that is taking ages to do, or has no end. So your code probably works, but the time complexity of it is too large. — jonogilmour, Nov 12 '14 at 02:08
It doesn't mean that the second example ever gets to enumerate `4*2` — Sassa NF, Nov 12 '14 at 12:01
This is equivalent to enumerating all rational numbers. You have to convert two infinities into one by iterating over cross-diagonals in a two dimensional representation. — karakfa, Nov 12 '14 at 14:42
possible duplicate of [How to have multiple infinite ranges in list comprehensions?](http://stackoverflow.com/questions/15510916/how-to-have-multiple-infinite-ranges-in-list-comprehensions) — Luis Casillas, Nov 12 '14 at 22:06

score 4 · Accepted Answer · edited May 23 '17 at 10:33

In the first version, before the guards, (x, y) are generated as [(1, 1), (1, 2), (1, 3), (1, 4), ...)], so the even x guard fails for all of them, but it never gets to the point where x would become 2, so no (x, y) pair ever makes it through the guards.

In the second version, x is generated as [1, 2, 3, ...], the first guard filters out 1, so it only gets to generating y with x already set to 2. So this means (x, y) is now generated as [(2, 1), (2, 2), (2, 3), (2, 4), ...]. The second guard then filters this down into [(2, 2), (2, 4), ...]; these are the numbers which are then multiplied and yielded.

Note that while the second version is productive in this sense, it will never consider any x other than 2, because of the reason outlined above.

A better solution would be to enumerate the pairs of numbers in such a way that the y doesn't starve out the x: haskell infinite list of incrementing pairs

score 1 · Answer 2 · answered Nov 12 '14 at 02:10

The predicates are supposed to go after their respective bindings, like in your second example. Then you can think of it like a nested loop:

for each x:
  if x even:
    for each y:
       if y even:
         x * y

Since the ys are an infinite list though, only 2 will be considered for x.

List comprehension with infinity list

2 Answers2