filter vs takeWhile：差异和运行时间

Question

在 GHCI 中，我有以下运行。第一个表达式很快就给出了结果。第二个没有（我在 10 秒后打断了它）。我想明白为什么？有无限循环吗？

Prelude> sum (takeWhile (<10000) (filter odd (map (^2) [1..])))
166650
Prelude> sum (filter (<10000) (filter odd (map (^2) [1..])))
Interrupted.
Prelude>

Answer 1

filter 只是不断遍历您提供的列表以找到满足谓词的所有元素。给它一个无限列表，它只会不断搅动。

takeWhile 另一方面 returns 满足谓词的最长初始元素序列，不满足时停止。

Answer 2

是的，有很大的不同。如果我们阅读文档，我们会看到：

takeWhile :: (a -> Bool) -> [a] -> [a]

takeWhile, applied to a predicate p and a list xs, returns the longest prefix (possibly empty) of xs of elements that satisfy p.

鉴于：

filter :: (a -> Bool) -> [a] -> [a]

filter, applied to a predicate and a list, returns the list of those elements that satisfy the predicate.

作为 filter 和 takeWhile 的输入列表，您使用列表：

filter odd (map (^2) [1..])

所以这意味着您生成了一个包含所有个方块的列表，其中包含 map (^2) [1...]，然后从这些方块中生成 filter odd。这又是一个无限列表（但即使它是有限的，也永远不会终止，因为 filter 不知道该列表，因此将继续尝试找到 odd 个元素）。

所以输入列表的大小是无限的。我们可以看到列表中的项目在增长，但 filter 不知道。因此，尽管在某个元素之后列表将继续失败，但 filter 将在搜索下一个元素时继续枚举列表。

另一方面，

takeWhile 从它找到 not 满足条件的元素的那一刻起终止。例如：

Prelude> takeWhile odd [1,3,5,12,7,9,1,3]
[1,3,5]

鉴于：

Prelude> filter odd [1,3,5,12,7,9,1,3]
[1,3,5,7,9,1,3]

filter vs takeWhile：差异和运行时间

filter vs takeWhile: difference and runtime

haskell

functional-programming

runtime