如何在Haskell中过滤无限列表

Question

可能重复:
对无限列表的有限理解

我无法理解为什么ghci无法正确计算此代码？

[x | x <- [1..], x < 1000]

Ghci只是停在最后一个号码,我需要在命令行中断这个过程以恢复正常状态.怎么了？我希望这段代码可以工作,因为haskell的懒惰评估.

Answer 1

[x | x <- [1..], x < 1000]相当于filter (< 1000) [1..]; 你想要的takeWhile (< 1000) [1..].

那么filter和之间的区别是takeWhile什么？

好吧,如果你试图评估整个结果 - 这就是ghci所做的,为了打印它 - 然后filter将测试输入列表中的每个元素以确定它是否应该在输出列表中.在第一千元素之后？它继续进行测试.filter不知道它不会突然遇到..., 12345, 12346, -7, 12348, ....

另一种看待它的方法是,filter一旦到达输入列表的末尾,只能说"输出列表在这里结束".如果您为它提供无限列表,则永远无法确定它是否已生成输出列表的所有元素.所以它似乎会挂起.

takeWhile另一方面,一旦到达不符合条件的元素,就会停止并终止其输出列表.

Answer 2

您只是要求列表中的每个小于1000的数字.您知道列表已排序,但您的算法没有利用此功能.编译器不会自动意识到您正在处理已排序的数据,并且无法推断一旦您看到一个至少为1000的数字,您再也看不到一个小于该值的数字.

正如其他人所指出的那样,takeWhile (< 1000) [1..]一旦谓词对一个元素失败(在这种情况下,一旦遇到一个至少为1000的数字),就可以通过特定地停止对列表的检查来利用你对列表特殊性的了解.请注意这是一个可用的优化,因为[1..]它不是"只是一个列表"; 它是一个包含特殊属性的列表(特别是它已经排序).