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

Question

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

[1.. ]

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

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

Answer 1

Haskell中列表的基本优点是它们是control结构，看起来像data结构。您可以编写对数据的[[streams进行增量操作的代码，但它对列表的简单操作却像对列表的简单操作那样。这与其他需要使用显式增量结构的语言形成了对比，例如迭代器（Python itertools），协程（C＃IEnumerable）或范围（D）。例如，sort函数可以这样编写：在开始产生结果之前，它对尽可能少的元素进行排序。在对entire

列表进行排序时，在列表的长度上花费O（n log n）/线性时间，而minimum xs = head (sort xs)仅花费O（n）/

linear时间，因为head仅检查列表的第一个构造函数，例如x : _，将tail保留为未评估的重排，表示排序操作的其余部分。]这意味着性能是compositional：例如，如果您对数据流（例如sum . map (* 2) . filter (< 5)）进行一长串操作，则

looks

就像首先过滤所有元素一样，然后将函数映射到它们，然后求和，并在每一步生成完整的中间列表。但是发生的是，每个元素一次只能处理一个：给定[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，例如and [a, b, c] == a && b && c，并且可以简单地实现为折叠：and = foldr (&&) True。一旦到达输入中的False元素，它就会停止求值，这仅仅是因为&&的正确参数很懒。懒惰给你构图！[有关所有这些的出色论文，请阅读约翰·休斯着名的Why Functional Programming Matters，该书超越了我所能比的更好的惰性函数编程的优势（在Haskell的前身Miranda中）。