haskell - 如何在 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..]它不是“只是一个列表”；它是一个具有特殊属性的列表（特别是已排序）。

Answer 3

由于您产生了一个无穷大[1..]，因此该列表的每个元素都会根据您的条件进行检查x < 1000。这也意味着此列表中大于 1000 的每个元素都会使用此条件进行检查。

但是你可以这样写你的函数：

myFilteredList :: [Int] -> [Int]
myFilteredList [] = []
myFilteredList (x:xs) = if x < 1000 then x: myFilteredList xs else []

对于更一般的行为，您也可以将条件作为参数。

myFilteredList :: (a -> Bool) -> [a] -> [a]
myFilteredList cond [] = []
myFilteredList cond (x:xs) = if cond x then x: myFilteredList cond xs else []

myFilteredList (< 1000) [1..]

这正是预定义函数takeWhile所做的。它接受一个条件(a -> Bool)和一个列表[a]作为参数，并返回符合条件的列表前缀。就像在 的定义中一样myFilteredList，如果函数处理了整个列表或者如果它到达列表中的第一个元素，则该函数终止，这不满足条件。

Answer 4

检查 x<1000 用于决定要包含在过滤列表中的内容，而不是停止评估。换句话说，你给 ghci 一个无限列表，它会对列表中的每个元素执行 x<1000。如果要在谓词为 True 之前获取元素，请使用 takeWhile。Haskell 是否懒惰并不重要，过滤后的列表会被评估，因为 ghci 会打印它。如果你想避免这种情况，请使用 let

let l = [x | x <- [1..], x < 1000]