Haskell - 为什么我要使用无限数据结构？

Question

在 Haskell 中，可以像这样定义无限列表：

[1.. ]

如果找到许多描述如何实现无限列表的文章，并且我了解这是如何工作的。但是，我想不出有什么理由使用无限数据结构的概念。

有人可以给我一个问题的例子，在 Haskell 中使用无限列表可以更容易地（或者可能只是）解决这个问题？

Answer 1

Haskell 中列表的基本优点是它们是一种看起来像数据结构的控制结构。您可以编写对数据流进行增量操作的代码，但它看起来像对列表的简单操作。这与需要使用显式增量结构的其他语言形成对比，例如迭代器（Python 的）、协程（C# ）或范围（D）。itertoolsIEnumerable

例如，一个sort函数可以这样编写，在它开始产生结果之前，它对尽可能少的元素进行排序。而对整个列表进行排序需要 O(n log n) / 列表长度的线性时间，minimum xs = head (sort xs)只需要 O(n) /线性时间，因为head只会检查列表的第一个构造函数，例如x : _，而将尾部保留为一个未计算的 thunk，表示排序操作的剩余部分。

这意味着性能是组合性的：例如，如果您对数据流有很长的操作链，例如sum . map (* 2) . filter (< 5)，看起来它会首先过滤所有元素，然后将函数映射到它们上，然后求和，产生每一步都有一个完整的中间列表。但是发生的情况是每个元素一次只处理一个：给定[1, 2, 6]，这基本上如下进行，所有步骤都是递增的：

• 总计 = 0
• 1 < 5 是真的
• 1 * 2 == 2
• 总计 = 0 + 2=2
• 2 < 5 是真的
• 2 * 2 == 4
• 总计 = 2 + 4=6
• 6 < 5 是假的
• 结果 = 6

这正是您在命令式语言（伪代码）中编写快速循环的方式：

total = 0;
for x in xs {
  if (x < 5) {
    total = total + x * 2;
  }
}

这意味着性能是组合性的：由于懒惰，此代码在处理列表期间具有恒定的内存使用量。并没有什么特殊的内部map或filter使这种情况发生：它们可以是完全独立的。

再举一个例子，and在标准库中计算一个列表的逻辑与，例如and [a, b, c] == a && b && c，它被简单地实现为一个 fold: and = foldr (&&) True。当它到达False输入中的一个元素时，它会停止计算，因为&&它的正确参数是惰性的。懒惰给你作文！

关于这一切的一篇很棒的论文，请阅读John Hughes著名的为什么函数式编程很重要，它比我能更好地介绍了惰性函数式编程（在米兰达，Haskell 的前身）的优点。