CODEWITHSUNDEEP
haskelllist-comprehension
Kevin Meredith
Kevin Meredith

Reputation: 41909

List Comprehension with Argument Not Terminating

Let's say I want to find a list of (Integer, Integer) where i and j are >= 2, and i + j + 2*i*j < 100:

ghci> take 10 [ (i, j) | i <- [2..], j <- [2..], i * j + 2*i*j < 100]
[(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(2,10),(2,11)]

However, when I change this function to accept an argument n (rather than 100), it's not terminating for me after ~15 seconds.

ghci> let f n = take 10 [ (i, j) | i <- [2..], j <- [2..], i * j + 2*i*j < n]

ghci> f 5
Interrupted.

Upvotes: 1

Views: 89

Answers (1)

Mark Reed
Mark Reed

Reputation: 95252

If you call f 100 instead of f 5, you'll get the same results as the first example. The problem isn't the fact that it's a function; it's the fact that you're trying to extract the first 10 elements of a filtered infinite list when the filter will never return that many elements.

There are no values of i and j greater than or equal to 2 for which 3*i*j < 5, so the returned list for n=5 should be empty. But Haskell can't determine that it's empty until it's examined all possible values of i and j. As written, that's an infinite number of possibilities. Since it never runs out of possible inputs, and never gets to the desired ten outputs, it never terminates.

The other thing to notice is that the first ten answers to the problem for n=100 all have i=2. If you try a number in between, such 50, you can watch the function generate the first part of the correct answer for that case - specifically, in the case of n=50, the seven elements which have i equal to 2. But after that, despite there being more than the needed three additional solutions to get to ten elements, it hangs. That's becausee those additional solutions all have i > 2. Haskell doesn't find them because it never gets past looking at the "first infinity" cases where i is 2 and j is any number at all.

Upvotes: 8

Related Questions