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

Question

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

[1.. ]

我找到了许多有关如何实现无限列表的文章，我也理解了它的工作原理。然而，我无法想出使用无限数据结构概念的任何理由。

有人能给我举一个在Haskell中可以更轻松地（或仅能）使用无限列表解决的问题的例子吗？

- Moritz Schmidt

---

我确定有很多好的答案，但是为了让您开始了解，无限数据结构通常允许更简单的定义。考虑enumerate，它将列表中的每个元素与其索引放入元组中。这可以通过一个带有索引参数的辅助函数进行递归定义，或更简单地使用zipWith [0..]来定义。由于 zip 的特性，编写[0..]比编写[0.. length list - 1]要容易得多且更一般化。 - cole

这句话的意思是，你不需要通过数据生成函数传递停止条件，而是可以在最后应用它。一个经典的例子是 take 50 fibonacci，其中 fibonacci 是通过自身来定义的。 - Bergi

首先，让我们消除“在数学上是无限的事物”（如整数）和“在我的程序看来实际上是无限的事物”（如用户生成的I/O事件流）之间的区别。很容易看出为两者操作提供通用接口的优点。你可能不会经常遇到前者，但后者却很常见。 - Jared Smith

根据我的经验，无限数据结构并不经常使用。尽管有时它们很方便。例如，如果我们正在编写一种语言解释器，“head [var | var <- infiniteListOfVarNames , not (var freeIn expression)]”是一个简短的代码，用于生成一个在“expression”中没有出现过的新名称。虽然它不太高效，但很容易编写和理解。还有类似的情况，需要在满足某些条件的无限多个值中找到“第一个”值，并且过滤无限列表非常自然。在我看来，无限树并不是很有用。 - chi

请参阅非平凡的惰性求值。 - Daniel Wagner

@cole 我本来也想举 zip [0..] 的例子，但说实话这个例子有点浅显，因为不仅 Python 的 enumerate 可以胜任这个工作，甚至在 Haskell 中也可以做到：当使用 Data.Vector 时，你会使用 indexed 而不是 zip。 - leftaroundabout

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]，这基本上是按照以下方式进行的，所有步骤都是逐步进行的：

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

这意味着性能是可组合的：由于惰性求值，在处理列表时，该代码具有恒定的内存使用量。而在map或者filter中并没有什么特别的东西使得这种情况发生：它们可以完全独立。

举个例子，标准库中的and函数计算一个列表的逻辑“与”（logical AND），例如and [a, b, c] == a && b && c，并且其实现仅仅是一个fold: and = foldr (&&) True。一旦它到达输入中的False元素，它就会停止求值，这仅仅是因为&&对其右参数是惰性的。惰性给你带来了组合的能力！

关于所有这些的一篇好文章，请阅读约翰·休斯（John Hughes）著名的《为什么函数式编程很重要》，其中详细介绍了惰性函数式编程（Miranda语言的前身）的优势。

- Jon Purdy

---

关于您对“最小值”的定义，这不是依赖于实现sort的算法保证最小元素可以在线性时间内被识别出来吗（例如插入排序）？ - chepner

@chepner 我认为标准的sort是一种归并排序，由于惰性的缘故更像堆排序。如果是这样，它应该保证生成第一个元素的时间复杂度为O(n)。 - chi

如果我理解正确，这里有一个O(n)时间的遍历来将列表分解成已排序的子序列，然后是O(k)个合并操作将所有子列表合并为单个列表，最后一步是返回结果中的单个项目。也就是说，[5, 6, 4, 7, 3, 8, 2, 9, 1] -> [[5, 6], [4, 7], [3, 8], [2, 9], [1]] -> [[4,5,6,7],[2,3,8,9],[1]] -> [[2,3,4,5,6,7,8,9],[1]] -> [[1,2,3,4,5,6,7,8,9]] -> [1,2,3,4,5,6,7,8,9]。在完成中间的合并步骤之前，无法提取头项。 - chepner

在执行所有合并步骤之前，您可以提取头部，因为您实际上只需要每个合并的头部。因此，您大致可以得到：将n个比较拆分成序列所需的比较次数；获取第一级合并头部所需的n/2次比较；获取第二级头部所需的n/4次比较；下一级需要n/8次比较；等等。这是n+n/2+n/4+n/8+... = 2*n ∈ O(n) 的总比较次数，以获取顶级列表的头部。 - Daniel Wagner

这是一个关于懒惰性的很好的回答，但似乎没有提到任何无限数据结构。 - luqui

Answer 2

• Annotating a list with its indices temporarily uses an infinite list of indices:

  zip [0..] ['a','b','c','d'] = [(0,'a'), (1,'b'), (2,'c'), (3,'d')]
  

• Memoizing functions while maintaining purity (in this case this transformation causes an exponential speed increase, because the memo table is used recursively):

  fib = (memo !!)
      where
      memo = map fib' [0..]  -- cache of *all* fibonacci numbers (evaluated on demand) 
      fib' 0 = 0
      fib' 1 = 1
      fib' n = fib (n-1) + fib (n-2)
  

• Purely mocking programs with side-effects (free monads)

  data IO a = Return a
            | GetChar (Char -> IO a)
            | PutChar Char (IO a)
  

  Potentially non-terminating programs are represented with infinite IO strucutres; e.g. forever (putChar 'y') = PutChar 'y' (PutChar 'y' (PutChar 'y' ...))

• Tries: if you define a type approximately like the following:

  data Trie a = Trie a (Trie a) (Trie a)
  

  it can represent an infinite collection of as indexed by the naturals. Note that there is no base case for the recursion, so every Trie is infinite. But the element at index n can be accessed in log(n) time. Which means you can do something like this (using some functions in the inttrie library):

  findIndices :: [Integer] -> Trie [Integer]
  findIndices = foldr (\(i,x) -> modify x (i:)) (pure []) . zip [0..]
  

  this builds an efficient "reverse lookup table" which given any value in the list can tell you at which indices it occurs, and it both caches results and streams information as soon as it's available:

  -- N.B. findIndices [0, 0,1, 0,1,2, 0,1,2,3, 0,1,2,3,4...]
  > table = findIndices (concat [ [0..n] | n <- [0..] ])
  > table `apply` 0
  [0,1,3,6,10,15,21,28,36,45,55,66,78,91,...
  

  all from a one-line infinite fold.

我相信还有更多的例子，有许多很酷的事情可以做。

- luqui