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

Question

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

[1.. ]

如果发现许多描述如何实现无限列表的文章，我就明白这是如何工作的。
但是，我想不出任何理由使用无限数据结构的概念。

有人可以给我一个问题的例子，可以通过 Haskell 中的无限列表更容易(或者可能只)解决这个问题吗？

Answer 1

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

例如，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 , 它被简单地实现为折叠:and = foldr (&&) True .到达 False 的那一刻输入中的元素，它停止评估，仅仅是因为 &&在正确的论点上是懒惰的。懒惰给你作文!

有关这一切的精彩论文，请阅读著名的 Why Functional Programming Matters由 John Hughes 撰写，它对惰性函数式编程(在 Miranda 中，Haskell 的前身)的优势进行了比我做得更好的论述。