当前位置：文江博客话题详情

无限数据结构有哪些引人注目的用例？

发布于 2024-10-21 14:49:41 字数 96 浏览 3 评论 0原文

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

风启觞 2024-10-28 14:49:41

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

为什么功能性John Hughes 的《Programming Matters》有一个很好的例子，即国际象棋游戏。国际象棋游戏的走棋树实际上并不是无限的，但它足够大，以至于它也可能是无限的（称之为“接近无限”）。用严格的语言来说，你实际上不能将其视为一棵树，因为没有足够的空间来存储整棵树。但在惰性语言中，您只需定义树，然后定义一个“nextMove”函数来根据需要遍历它。惰性求值机制负责处理细节。

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

zip [1..] items

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

Here are two examples, one big and one small:

Why Functional Programming Matters by John Hughes has a good example, of a chess game. The move tree for a chess game is not actually infinite, but its big enough that it might as well be infinite (call it "near-infinite"). In a strict language you can't actually treat it as a tree, because there isn't enough room to store the whole tree. But in a lazy language you just define the tree and then define a "nextMove" function to traverse it as far as necessary. The lazy evaluation mechanism takes care of the details.

The small example is simply associating an index number with every item in a list, so that ["foo", "bar", "baz"] becomes [(1,"foo"), (2,"bar"), (3,"baz")]. In a strict language you need a loop that keeps track of the last index and checks to see if you are at the end. In Haskell you just say:

zip [1..] items

The first argument to zip is an infinite list. You don't need to work out how long it needs to be ahead of time.

回复收藏 0 原文

留一抹残留的笑 2024-10-28 14:49:41

我能想到的一些优点：

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

回复收藏 0 原文

墨离汐 2024-10-28 14:49:41

有一个规范的纯记忆策略：

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

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

当然，这在参数中具有线性的查找时间。您可以将其替换为无限特里树以获得对数查找时间。参见data-inttrie。

There is the canonical pure memoization strategy:

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

We map the fib' function over an infinite list to construct a table of all the values of fib. Voila! Cheap, easy memoization.

Of course, this has lookup time linear in the argument. You can replace it with an infinite trie to get logarithmic lookup time. cf. data-inttrie.

回复收藏 0 原文

背叛残局 2024-10-28 14:49:41

我要评论@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, fx, f (fx), f (f (fx)), ...]。我本可以用迭代的方式来编写 iota：

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

惰性方法是一种优雅的编程方式。这不是唯一的方法，习惯了 C 或 Java 的人肯定会大喊“但我不需要懒惰，我可以_”，他们是对的。如果你的语言是图灵完备的，那就可以做到。但懒惰也可以如此优雅。

I was going to comment regarding @knivil's Scheme. Instead I'll just throw this up as another answer.

Lazy data structures aren't the only way to accomplish most tasks. This might irritate Pythonistas. But I believe it's best when programmers get to choose which techniques they use. Lazy techinques are powerful and elegant.

Knivil mentioned using Scheme's iota. Look how easy it is to write the full method (with all 3 args), relying on laziness:

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..]

I could also write length for non-empty lists by abusing laziness:

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

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

Consider the powerful and elegant iterate function defined in Prelude.

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

It creates the infinite list [x, f x, f (f x), f (f (f x)), ...]. I could have written iota in terms of iterate:

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

The lazy approach is an elegant way to program. It's not the only way, and people used to C or Java will certainly cry out "but I don't need laziness, I can just _", and they are correct. If your language is Turing-complete, it can be done. But laziness can be oh so elegant.

回复收藏 0 原文

左岸枫 2024-10-28 14:49:41

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

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

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

Well, I had a nice use case for that last month. I needed a generator for unique names when copying objects. That means, the generator takes the original name X, and generates a new name for the copy. It does that by appending a text like

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

as long as the name is not used within the set of objects within the same group. Using an "infinite data structure" (an infinite array of strings) for that instead of a simple loop has one advantage: you can separate the name generating part completely from the test if the name is already in use. So I could reuse the generator function for different types of objects where the in-use test is slightly different for each object type.

回复收藏 0 原文