4

我使用 Haskell 已经有一段时间了，我已经阅读了大部分 Real World Haskell 和 Learn You a Haskell。我想知道的是，是否存在使用惰性求值的语言的意义，特别是拥有无限列表的“优势”，是否存在无限列表非常容易完成的任务，或者甚至是只有无限可能的任务清单？

4

8 回答 8

17

这是一个非常微不足道但实际上日常有用的示例，说明无限列表特别派上用场：当您有一个要用于初始化某些键值样式数据结构的项目列表时，从连续键开始。所以，假设你有一个字符串列表，你想把它们IntMap从 0 开始计数。如果没有惰性无限列表，你会做一些事情，比如遍历输入列表，保持一个正在运行的“下一个索引”计数器并建立IntMap当你去时。

对于无限的惰性列表，列表本身扮演着运行计数器的角色；只需zip [0..]与您的项目列表一起使用来分配索引，然后IntMap.fromList构建最终结果。

当然，这两种情况本质上是一样的。但是拥有惰性无限列表可以让您更直接地表达概念，而不必担心输入列表的长度或跟踪额外计数器等细节。

于 2010-12-20T15:24:43.043 回答
13

一个明显的例子是将你的数据处理从输入链接到你想用它做的任何事情。例如，将字符流读入惰性列表，由词法分析器处理，同时生成一个惰性标记列表，将其解析为惰性 AST 结构，然后编译并执行。这就像使用 Unix 管道。

于 2010-12-20T15:08:46.817 回答
8

我发现在一个地方定义所有序列通常更容易和更清晰，即使它是无限的，并且使用它的代码只是抓住它想要的东西。

take 10 mySequence
takeWhile (<100) mySequence

而不是有许多相似但不完全相同的函数来生成一个子集

first10ofMySequence
elementsUnder100ofMySequence

当相同序列的不同小节用于不同区域时，好处更大。

于 2010-12-20T15:18:44.360 回答
7

正如 John Hughes 的经典论文Why Functional Programming Matters中所解释和说明的那样，无限数据结构（包括列表）极大地促进了模块化并因此提高了可重用性。例如，您可以将复杂的代码块分解为生产者/过滤器/消费者部分，每个部分都可能在其他地方有用。

因此，无论您在哪里看到代码重用的实际价值，您都会得到问题的答案。

于 2010-12-20T21:07:49.960 回答
6

基本上，惰性列表允许你延迟计算直到你需要它。当您事先不知道何时停止以及要预先计算什么时，这可能会很有用。

一个标准的例子是 u_n 一系列收敛到某个极限的数值计算。你可以要求第一个词，这样 |u_n - u_{n-1}| < epsilon，为您计算正确的术语数。

现在，您有两个这样的序列 u_n 和 v_n，并且您想知道 epsilon 精度限制的总和。算法是：

  • 计算 u_n 直到 epsilon/2 精度
  • 计算 v_n 直到 epsilon/2 精度
  • 返回 u_n + v_n

一切都是惰性完成的，只计算必要的 u_n 和 v_n。您可能想要不那么简单的示例，例如。在您知道（即知道如何计算）f 的连续性模数的地方计算 f(u_n)。

于 2010-12-20T15:11:33.073 回答
4

声音合成 - 请参阅 Jerzy Karczmarczuk 的这篇论文：

http://users.info.unicaen.fr/~karczma/arpap/cleasyn.pdf

Jerzy Karczmarcuk 有许多其他论文使用无限列表来模拟幂级数和导数等数学对象。

我已经将基本的声音合成代码翻译成 Haskell - 足以用于正弦波单元生成器和 WAV 文件 IO。性能几乎足以在 1.5GHz Athalon 上使用 GHCi 运行 - 因为我只是想测试这个概念，但我从未考虑过对其进行优化。

于 2010-12-20T18:28:58.367 回答
3

无限/懒惰的结构允许“打结”的成语：http ://www.haskell.org/haskellwiki/Tying_the_Knot

典型的简单示例是斐波那契数列，直接定义为递归关系。（是的，是的，举行效率投诉/算法讨论——重点是成语。）：fibs = 1:1:zipwith (+) fibs (tail fibs)

这是另一个故事。我有一些只适用于有限流的代码——它做了一些事情来将它们创建到一个点，然后做了一大堆废话，涉及对依赖于该点之前的整个流的流的各个位进行操作，将它与来自另一个流的信息合并，等等。这非常好，但我意识到它有一大堆处理边界条件所必需的东西，基本上当一个流用完东西时该怎么办。然后我意识到，从概念上讲，它没有理由不能在无限流上工作。所以我切换到一个没有 nil 的数据类型——即一个真正的流而不是一个列表，所有的麻烦都消失了。即使我知道我永远不需要超过某个点的数据，

于 2010-12-20T17:51:13.130 回答
3

我最喜欢的实用主义之一是cycle. cycle [False, True]生成无限列表[False, True, False, True, False ...]。特别是 , xs ! 0 = False，xs ! 1 = True所以这只是说明元素的索引是否为奇数。这在哪里出现？很多地方，但这里有一个任何 Web 开发人员都应该熟悉的地方：制作逐行交替着色的表格。

The general pattern seen here is that if we want to do some operation on a finite list, rather than having to construct a specific finite list that will “do the thing we want,” we can use an infinite list that will work for all sizes of lists. camcann’s answer is in this vein.

于 2010-12-21T00:44:16.107 回答