无限列表对任何实际应用程序都有用吗？

Question

我已经使用haskell很长一段时间了,我已经阅读了大部分真实世界Haskell和了解你的Haskell.我想知道的是,对于使用惰性评估的语言是否有意义,特别是具有无限列表的"优势",是否有无限列表变得非常容易的任务,或者甚至是只有无限可能的任务名单？

Answer 1

这里有一个完全无关紧要但实际上日常有用的例子,其中无限列表特别派上用场:当你有一个项目列表,你想用它来初始化一些键值式数据结构,从连续键开始.所以,假设你有一个字符串列表,你想把它们IntMap从0 开始计数.没有懒惰的无限列表,你会做一些事情,比如走下输入列表,保持一个正在运行的"下一个索引"计数器并建立IntMap当你去时.

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

当然,在这两种情况下,它基本上都是一样的.但是,拥有懒惰的无限列表可以让您更直接地表达概念,而无需担心输入列表的长度或跟踪额外计数器等细节.

Answer 2

一个明显的例子是将数据处理从输入链接到您想要用它做的任何事情.例如,将字符流读入由词法分析器处理的惰性列表,还生成一个懒惰的令牌列表,这些令牌被解析为一个惰性AST结构,然后进行编译和执行.这就像使用Unix管道.

Answer 3

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

take 10 mySequence
takeWhile (<100) mySequence

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

first10ofMySequence
elementsUnder100ofMySequence

当在不同区域中使用相同序列的不同子部分时,益处更大.

Answer 4

基本上,惰性列表允许您在需要之前延迟计算.如果您事先不知道何时停止以及预先计算什么,这可能会很有用.

标准示例是u_n一系列数值计算收敛到某个极限.您可以要求第一个术语,例如| u_n - u_ {n-1} | <epsilon,为您计算正确的术语数.

现在,您有两个这样的序列u_n和v_n,并且您想知道epsilon精度的限制之和.算法是:

• 计算u_n直到epsilon/2准确度
• 计算v_n直到epsilon/2精度
• return u_n + v_n

所有这些都是懒惰地完成的,只计算了必要的u_n和v_n.您可能需要不太简单的示例,例如.计算f(u_n)你知道(即知道如何计算)f的连续模数.

Answer 5

无限的数据结构(包括列表)大大提高了模块性和可重用性,正如John Hughes的经典论文"功能编程为何重要"所解释和说明的那样.例如,您可以将复杂的代码块分解为生产者/过滤器/消费者块,每个块都可能在其他地方使用.

因此,只要您在代码重用中看到真实世界的价值,您就可以得到问题的答案.