什么是无限数据结构的引人注目的用例？

有些语言（Haskell，Clojure，Scheme等）有懒惰的评价。懒惰评估的“卖点”之一是无限数据结构。这有什么好处的？能够处理无限数据结构的情况的一些例子显然是有利的吗？

已邀请:

6 个回复

这里有两个例子，一个是大一个，一个是小的：为什么功能编程很重要约翰休斯有一个很好的例子，一个象棋游戏。国际象棋游戏的移动树实际上并不是无限的，但它足够大以至于它可能是无限的（称之为“近无限”）。在严格的语言中，您实际上不能将其视为树，因为没有足够的空间来存储整棵树。但是在惰性语言中，您只需定义树，然后定义“nextMove”函数，以便在必要时遍历它。懒惰的评估机制负责细节。小例子只是将索引号与列表中的每个项相关联，这样[[foo“，”bar“，”baz“]变为[（1，”foo“），（2，”bar“），（ 3， “巴兹”）]。在严格的语言中，您需要一个循环来跟踪最后一个索引，并检查您是否在最后。在Haskell中你只需说：

zip [1..] items

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

佩疵瓦

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

臂哦

有规范的纯记忆策略：

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

我们将fib'函数映射到无限列表上，以构建一个包含fib所有值的表。瞧！便宜，简单的记忆。当然，这在参数中具有线性查找时间。您可以用无限trie替换它以获得对数查找时间。比照数据inttrie。

辽躺

我打算对@ knivil的计划发表评论。相反，我会把它作为另一个答案。惰性数据结构不是完成大多数任务的唯一方法。这可能会激怒Pythonistas。但我相信程序员可以选择使用哪种技术。懒惰的技术强大而优雅。 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的人肯定会喊出“但我不需要懒惰，我只能_”，而且他们是正确的。如果您的语言是Turing-complete，则可以完成。但懒惰可以是如此优雅。

屉杆绊

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

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

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

浩挎

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

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

可以代表pi。由于内置的懒惰，操作这种表示变得容易。

要回复问题请先登录或注册

什么是无限数据结构的引人注目的用例？

6 个回复

发起人

lazy_sequences

问题状态

什么是无限数据结构的引人注目的用例？

与内容相关的链接

6 个回复

发起人

lazy_sequences

问题状态