无限数据结构有哪些令人信服的使用案例？

Question

无限数据结构有哪些令人信服的使用案例？

data-structureshaskellclojureschemelazy-sequences

26

一些语言（如Haskell、Clojure、Scheme等）具有惰性求值。惰性求值的一个“卖点”是无限数据结构。这有什么好处？有哪些情况下能够处理无限数据结构明显具有优势的例子？

- Anas Elghafari

Scheme默认情况下不是惰性的。 - knivil

@knivil：但它确实具有（可选）惰性求值，不是吗？ - fuz

Clojure应该是相同的，strict by default，但可以选择lazy。任何你可以实现thunks的语言都可以被视为类似的，尽管需要更多的语法来解决问题。@knivil @FUZxxl - Dan Burton

6个回答

15

以下是我能想到的几个优点：

更简洁的代码 - 有趣的是，生成无限序列的代码通常比操作有界数据的代码更简单、更干净。这是因为这样的代码通常更接近底层的数学定义。
更灵活 - 如果你使用懒惰无限结构来编写你的代码，而不是预先决定数据需要多大，那么你就不需要担心这个问题。它会“自己运行”。
更高的性能 - 如果正确使用惰性求值，可以通过仅在需要时计算数据值（甚至根本不计算）来提高性能。因此，你可以避免大量不必要的计算。
抽象无限进程 - 无限惰性序列可以很有趣地作为事件流的抽象使用，例如随着时间的推移从网络连接读取输入。这可以创造出一些非常优雅和有趣的方式来创建处理事件流的代码。例如查看Clojure中的stream-utils库。
更好的算法 - 有些算法更容易用无限数据结构表达 - 这个想法是你惰性地“拉入”你需要的解决方案的部分，同时保留其余无限算法未求值。如果使用这种方法可以减少算法的时间复杂度（从O(n^2)到O(n log n)），那么这可以是一个巨大的胜利。

- mikera

7

有一种经典的纯记忆化策略：

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

我们将fib'函数映射到无限列表上，以构建fib的所有值的表格。好了！廉价、易于记忆。

当然，这样做的查找时间是与参数成线性关系的。您可以使用无限trie替换它，以获得对数级别的查找时间。参见data-inttrie。

- luqui

这是优雅的代码。但是（也许我不完全理解底层发生了什么），这种方法比在表中缓存结果的动态编程方式更好在哪里？ - Anas Elghafari

6

@Anas，这确实是使用动态规划方法将结果缓存于表格中的方式。在这种情况下，表格是一个无限列表。尽管通常需要显式地迭代表格，但使用惰性记忆表可以让您像使用动态规划一样编写代码，但只计算实际在所需结果中使用的子问题。 - Dan Burton

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)), ...]。我可以用iterate来编写iota:

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

懒惰编程是一种优雅的方式。它并不是唯一的方式，熟悉C或Java的人们肯定会喊出“但我不需要懒惰，我可以只是_”，这是正确的。如果您的语言是图灵完备的，那么也可以完成。但是，懒惰编程可以非常优雅。

- Dan Burton

你展示了Haskell的许多特性，结合了惰性计算。但是优雅和简洁大多是语法上的主观感受。对我来说，你在Haskell中的例子确实很好，但我认为这不是无限数据结构的重点。游戏树的例子更好，所以我投了赞成票。 - knivil

3

上个月我有一个很好的应用场景。在复制对象时，我需要一个生成唯一名称的生成器。这意味着，生成器会接收原始名称X，并为副本生成一个新名称。它通过附加文本来实现此目的。

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

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

- Doc Brown

2

无限数据结构提供了（可计算的）实数的优雅表示。例如，像下面这样的无限列表：

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

可以用pi来表示。通过内置的惰性，对这个表示进行操作变得很容易。

- Peteris

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Paul Johnson · Accepted Answer

这里有两个例子，一个大的，一个小的：

Why Functional Programming Matters 一书中的John Hughes给出了一个很好的例子，关于一个国际象棋游戏。国际象棋游戏的移动树实际上并不是无限的，但足够大以至于可以视为无限（称之为“近似无限”）。在严格语言中，您无法将其视为一棵树，因为没有足够的空间来存储整个树。但在惰性语言中，您只需定义该树，然后定义一个"nextMove"函数来遍历它直到必要的程度。惰性求值机制会处理细节。

小的例子就是为列表中的每个项分配一个索引号，使["foo", "bar", "baz"]变成[(1,"foo"), (2,"bar"), (3,"baz")]。在严格语言中，您需要一个循环来跟踪最后一个索引并检查是否已到达结尾。在Haskell中，只需说：

zip [1..] items

zip的第一个参数是一个无限列表。你不需要预先计算它需要多长。