如何在Haskell中过滤无限列表

Question

可能是重复问题:
有限的理解无限列表

我不明白为什么ghci不能正确计算这段代码？

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

Ghci停在最后一个数字，我需要在命令行中打断这个进程才能回到正常状态。出了什么问题？我原本以为这段代码可以工作，因为Haskell有惰性评估。

- surganov

---

由于Haskell语言的惰性求值特性，这段代码确实有效。如果Haskell是严格求值的话，您将根本不会得到任何输出。 - sepp2k

Answer 1

[x | x <- [1..], x < 1000] 等价于 filter (< 1000) [1..]；你要使用 takeWhile (< 1000) [1..]。

那么 filter 和 takeWhile 有什么区别呢？

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

另一种看待它的方式是，filter 只能在达到输入列表的末尾时说 "输出列表到此为止"。如果你提供一个无限的列表，它永远无法确定它已生成所有的输出列表元素。因此它看起来会挂起。

另一方面，takeWhile 会在达到不符合条件的元素时立即停止并终止其输出列表。

- dave4420

Answer 2

你只是简单地请求一个小于1000的数字列表。你知道这个列表是有序的，但你的算法却没有利用这一点。编译器不能自动意识到你正在处理排序数据，并且无法推断出一旦你看到了一个至少为1000的数字，你就再也不会看到比它小的数字了。

正如其他人指出的那样，takeWhile (< 1000) [1..] 利用了你对列表的特殊知识，通过在谓词未能满足元素时（在这种情况下，一旦遇到至少为1000的数字），特别停止对列表的检查。注意，这是一种可用的优化，因为[1..]不仅仅是一个列表，它还具有特殊的属性（特别是它是排序的）。

- gspr

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的定义中一样，如果处理完整个列表或达到第一个不符合条件的元素，函数就会终止。

- ichistmeinname

Answer 4

检查x<1000用于决定在过滤列表中包含什么，而不是停止评估。换句话说，您正在为ghci提供一个无限的列表，并且它将对列表的每个元素执行x<1000操作。如果要获取元素直到谓词为True，请使用takeWhile。即使Haskell是惰性的，过滤列表也会被评估，因为ghci会打印它。如果要避免这种情况，请使用let。

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

- mariop