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

是的,有很大的不同.如果我们阅读文档,我们会看到:

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

takeWhile,应用于谓词p和列表xs,返回满足的元素的最长前缀(可能为空).xsp

然而:

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

filter,应用于谓词和列表,返回满足谓词的那些元素的列表.

至于输入列表filter和takeWhile,你用一个列表:

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

这意味着您生成所有正方形的列表map (^2) [1...],然后filter odd从中生成.这又是一个无限的列表(但即使它是有限的,也永远不会终止,因为filter不知道列表,因此将继续尝试查找odd元素).

因此输入列表具有无限大小.我们可以看到列表中的项目正在增长,但filter不知道.因此,虽然在某个元素之后列表将继续失败,filter但在搜索下一个元素时将继续枚举列表.

takeWhile在另一方面从时刻终止它发现它的元素没有满足条件.例如:

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]