列表理解与参数不终止

Question

假设我想找到(Integer, Integer)i和j> = 2的列表,并且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)]

但是,当我更改此函数以接受参数n(而不是100)时,它在约15秒后不会终止.

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

ghci> f 5
Interrupted.

Answer 1

如果你打电话f 100而不是f 5,你会得到与第一个例子相同的结果.问题不在于它是一个功能; 事实上,当过滤器永远不会返回那么多元素时,你试图提取过滤的无限列表的前10个元素.

有没有值i和j大于或等于2通过3*i*j < 5,所以返回的列表n=5应该是空的.但是Haskell无法确定它是空的,直到它检查了i和的所有可能值j.如上所述,这是无限多种可能性.由于它永远不会耗尽可能的输入,并且永远不会达到所需的十个输出,因此它永远不会终止.

另一件需要注意的是,n=100所有问题的前十个答案都有i=2.如果你在中间尝试一个数字,例如50,你可以观察该函数生成该情况的正确答案的第一部分 - 特别是n=50,在七个元素i等于2 的情况下.但在那之后,尽管那里它不仅仅是需要三个额外的解决方案来获得十个元素,它还有待实现.那是因为那些额外的解决方案都有i > 2.Haskell找不到它们,因为它永远不会过去看"第一个无限"的情况,其中i2 j是任何数字.