26

某些语言（Haskell、Clojure、Scheme 等）具有惰性求值。惰性求值的“卖点”之一是无限数据结构。这有什么了不起的？能够处理无限数据结构显然具有优势的案例有哪些？

4

6 回答 6

22

举两个例子，一大一小：

约翰休斯的《为什么函数式编程很重要》有一个很好的例子，一个国际象棋游戏。国际象棋游戏的移动树实际上并不是无限的，但它足够大以至于它也可能是无限的（称之为“接近无限”）。在严格的语言中，您实际上不能将其视为一棵树，因为没有足够的空间来存储整棵树。但是在惰性语言中，您只需定义树，然后定义“nextMove”函数以尽可能地遍历它。惰性评估机制负责处理细节。

这个小例子只是简单地将索引号与列表中的每个项目相关联，因此 ["foo", "bar", "baz"] 变为 [(1,"foo"), (2,"bar"), ( 3，“巴兹”）]。在严格的语言中，您需要一个循环来跟踪最后一个索引并检查您是否在最后。在 Haskell 中，您只需说：

zip [1..] items

zip 的第一个参数是一个无限列表。您无需提前计算出需要多长时间。

于 2011-03-12T18:36:21.430 回答
15

我能想到的几个优点：

  • 更简洁的代码——有趣的是，生成无限序列的代码通常比对有界数据进行操作的代码更简单、更简洁。这是因为这样的代码通常更接近底层的数学定义。
  • 灵活性——与其提前决定你的数据需要多大，如果你使用惰性无限结构来编写它，你根本不需要担心。它会“正常工作”
  • 性能——如果你正确地使用惰性，你可以通过只在需要时计算数据值来使用它来提高性能——而且可能根本不需要。因此，您可以潜在地避免大量不必要的计算。
  • 无限进程的抽象——无限惰性序列作为事件流的抽象有一个有趣的用途，例如随着时间的推移从网络连接中读取输入。这可以创建一些非常优雅和有趣的方式来创建代码来处理事件流。例如，请参阅 Clojure 中的stream-utils库。
  • 更好的算法- 有些算法更容易用无限数据结构表达 - 想法是你懒惰地“拉入”你需要的解决方案部分，同时不评估无限算法的其余部分。如果使用这种方法启用您可以降低算法的时间复杂度（例如 from O(n^2)to O(n log n)），那么这可能是一个巨大的胜利。
于 2011-03-12T18:42:19.683 回答
7

有规范的纯记忆策略：

fib = (map fib' [0..] !!)
    where
    fib' 0 = 0
    fib' 1 = 1
    fib' n = fib (n-1) + fib (n-2)

我们将fib'函数映射到一个无限列表上，以构建一个包含 的所有值的表fib。瞧！便宜，容易记忆。

当然，这在参数中具有线性查找时间。您可以将其替换为无限特里以获取对数查找时间。参看。数据完整性。

于 2011-03-12T18:20:21.670 回答
6

我打算评论@knivil 的计划。相反，我将把它作为另一个答案提出来。

惰性数据结构并不是完成大多数任务的唯一方法。这可能会激怒 Python 爱好者。但我相信最好让程序员选择他们使用的技术。懒惰的技术是强大而优雅的。

Knivil 提到使用 Scheme 的iota. 看看编写完整的方法（使用所有 3 个参数）是多么容易，依赖于惰性：

iota count begin step = let xs = begin:map (+step) xs
                        in take count xs

-- or, alternately
iota count begin step = take count $ map ((+begin).(*step)) [0..]

我还可以length通过滥用懒惰来写非空列表：

len = fst . last . zip [1..]

-- or even handling empty lists
len = fst . last . zip [0..] . (undefined:)

考虑一下 Prelude 中定义的强大而优雅的iterate函数。

iterate f x = x : iterate f (f x)

它创建了无限列表[x, f x, f (f x), f (f (f x)), ...]。我本可以这样写iota：iterate

iota count begin step = take count $ iterate (+step) begin

惰性方法是一种优雅的编程方式。这不是唯一的方法，习惯了 C 或 Java 的人肯定会喊“但我不需要懒惰，我可以只是 _”，他们是正确的。如果您的语言是图灵完备的，则可以完成。但是懒惰可以如此优雅。

于 2011-03-12T21:37:53.823 回答
3

好吧，上个月我有一个很好的用例。复制对象时，我需要一个生成器来生成唯一名称。这意味着，生成器采用原始名称X，并为副本生成一个新名称。它通过附加一个文本来做到这一点

X - copy
X - copy (2)
X - copy (3)
...

只要该名称未在同一组内的一组对象中使用。为此使用“无限数据结构”（无限的字符串数组）而不是简单的循环有一个优点：如果名称已经在使用中，您可以将名称生成部分与测试完全分开。所以我可以为不同类型的对象重用生成器函数，其中每个对象类型的使用测试略有不同。

于 2011-03-12T18:35:18.430 回答
2

无限数据结构提供了（可计算的）实数的优雅表示。例如，一个无限列表，如

[(0, 4), (1, 3.5), (3.1, 3.2), ...]

可以代表pi。借助内置的惰性，对这种表示进行操作变得容易。

于 2012-09-26T04:13:21.843 回答