Haskell - Por que essa compreensão de lista retorna uma lista infinita?

Question

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

Eu realmente não entendo porque isso dá

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

E não encontra fim

Answer 1

A semântica de

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

é testar [1..]e manter todos os elementos que satisfaçam a condição do filtro 3*x<20.

Um humano pode ver que, após o primeiro, xque falsifica a condição, não há sentido em tentar todos os valores maiores, mas Haskell tentará aqueles de qualquer maneira e ficará preso em uma espécie de loop infinito.

Isso ocorre porque, no caso geral, a condição pode se tornar verdadeira mais uma vez, por exemplo

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

Em geral, é indecidível detectar se não há mais soluções, então Haskell, como qualquer outra linguagem de programação, não pode optar por parar após a última solução.

Se você quiser que a lista pare após o primeiro valor que não satisfaça a condição de filtragem, use takeWhile:

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