14

我正在尝试学习 Haskell（非常好），我正在做的许多不同的事情之一是尝试解决一些 Project Euler 问题，因为我将继续测试我的勇气。

在做一些基于斐波那契的问题时，我偶然发现并开始使用斐波那契序列的递归无限列表版本：

fibs = 1 : 2 : zipWith (+) fibs (tail fibs)

对于其中一个 PE 问题，我需要提取小于 4,000,000 的偶数斐波那契数的子序列。我决定用列表理解来做这件事，在我玩代码的过程中，我偶然发现了一些我不太理解的东西；我假设这是我对 Haskell 的惰性评估方案的薄弱掌握使事情变得复杂。

以下理解工作得很好：

[x | x <- takeWhile (<= 4000000) fibs, even x]

下一个理解永远旋转；所以我通过并将输出返回到标准输出，虽然它停在正确的位置，但它似乎只是继续评估递归定义的列表，而在达到上限值后没有完成；表示列表中的最后一项以逗号打印，但不存在其他列表项或右方括号：

[x | x <- fibs, x <= 4000000, even x]

那么，与无限列表配合得很好的各种函数究竟使用了什么秘诀呢？

4

1 回答 1

24

该函数takeWhile不断获取输入列表的元素，直到它到达不满足谓词的第一个元素，然后停止。只要至少有一个元素不满足谓词，takeWhile就会将无限列表转换为有限列表。

你的第一个表情说

继续获取这个无限列表中的元素，直到找到大于 4,000,000 的元素，然后停止。如果它是偶数，则在输出中包含每个元素。

第二个表达式说

继续获取这个无限列表中的元素。如果每个元素小于或等于 4,000,000 并且它是偶数，则在输出中包含每个元素。

当您观察到永远挂起的输出时，该函数正忙于生成更多斐波那契数并检查它们是否小于或等于 4,000,000。它们都不是，这就是为什么什么都不会打印到屏幕上的原因，但是该函数无法知道它不会在列表的下方遇到一个小数字，因此它必须继续检查。

于 2012-11-12T16:33:02.830 回答