CODEWITHSUNDEEP
haskelllist-comprehension
DavLin
DavLin

Reputation: 58

Haskell - Why does this list comprehension return an infinite list?

[3 * x | x <- [1 ..], 3 * x < 20]

I don't really understand why this gives

[3,6,9,12,15,18

And doesn't find an end

Upvotes: 2

Views: 99

Answers (1)

chi
chi

Reputation: 116139

The semantics of

[3 * x | x <- [1 ..], 3 * x < 20]

is to try all the elements of [1..] and keep those satisfying the filter condition 3*x<20.

A human can see that after the first x which falsifies the condition there's no point in trying all the larger values, but Haskell will try those anyway, and get stuck on a kind of infinite loop.

This is because, in the general case, the condition could become true once again, e.g.

[3 * x | x <- [1 ..], 3 * x < 20 || x == 1000000 ]

In general it is undecidable to detect whether there are no more solutions, so Haskell, like any other programming language, can not opt to stop after the last solution.

If you want the list to stop after the first value which does not satisfy the filtering condition, use takeWhile:

takeWhile (< 20) [3 * x | x <- [1 ..]]

Upvotes: 14

Related Questions