问题标签 [lazy-sequences]

我今天有一个高阶函数的想法，但我不知道该怎么写。我有几个稀疏的惰性无限序列，我想创建一个抽象，让我检查给定的数字是否在这些惰性序列中。为了提高性能，我想将稀疏序列的值推送到 hashmap（或集合）中，并在必要时动态增加 hashmap 中值的数量。由于惰性序列的稀疏性，自动记忆不是这里的答案。

可能代码最容易理解，所以这就是我到目前为止所拥有的。如何更改以下代码以使谓词使用封闭的哈希图，但如果需要增加哈希图的大小并重新定义自身以使用新的哈希图？

如何在不恢复到命令式风格的情况下解决这个问题？

当生成器未完成值并且已读取所有需要的结果时，有没有办法停止产生？我的意思是生成器在没有进行 StopIteration 的情况下给出值。

例如，这永远不会停止：（修订）

我找到了这段代码，但还不明白，如何在这种情况下应用它：http: //code.activestate.com/recipes/576585-lazy-recursive-generator-function/

编辑：我在写这篇文章的过程中发现了我自己问题的部分答案，但我认为它可以很容易地改进，所以无论如何我都会发布它。也许那里有更好的解决方案？

我正在寻找一种简单的方法来以一种let形式定义递归函数，而无需借助letfn. 这可能是一个不合理的要求，但我正在寻找这种技术的原因是因为我混合了数据和递归函数，这些函数在某种程度上需要大量的嵌套let和letfn语句。

我想编写生成这样的惰性序列的递归函数（以斐波那契序列为例）：

但是在clojure中似乎fibs不能在绑定期间使用它自己的符号。解决它的明显方法是使用letfn

但是正如我之前所说，这会导致很多麻烦的嵌套和交替letand letfn.

为了在不letfn使用和使用 just的情况下做到这一点let，我首先编写了一些使用我认为是 U-combinator 的东西（今天刚刚听说过这个概念）：

但是如何摆脱冗余(fi fi)呢？

正是在这一点上，经过一个小时的挣扎并逐渐向组合子 Q 添加位，我找到了自己问题的答案。

Q我用来定义递归序列的这个组合器叫什么？它看起来像没有参数的 Y 组合器x。是一样的吗？

clojure.core 或 clojure.contrib 中是否有另一个函数提供 Y 或 Q 的功能？我无法想象我刚才所做的是惯用的......

我有一个长而懒惰的序列，我想减少和懒惰地测试。一旦两个顺序元素=（或其他谓词）彼此不存在，我就想停止使用该列表，因为该列表的生成成本很高。是的，这听起来像take-while，但请进一步阅读。

我想写一些像这样简单而优雅的东西（假装一分钟every?像这样reduce）：

但这并不懒惰，因此它挂在无限序列上。我发现这几乎可以按我的意愿工作：

但是，我注意到序列分块会导致创建和测试额外的、不必要的元素。至少，我认为这就是以下代码中发生的情况：

我找到了一种解决方法，使用take-while, 并count检查所用元素的数量，但这相当麻烦。

我应该礼貌地向 Rich Hickey 建议他正确地进行一些组合reduce和every?短路，还是我错过了一些已经存在的明显方式？

编辑：两个好心人发布了避免在惰性序列上分块的解决方案，但是在执行 时如何避免分块apply，这似乎在四个一组的分块中消耗？

编辑#2：正如 Stuart Sierra 所指出的，我独立发现，这实际上并不是分块。只是申请正常行事，所以我会称之为关闭并给他答案。对于那些感兴趣的人，我在单独的答案中包含了一个小函数来解决问题的减少部分。

我正在使用 BufferedReader 对对象执行流式读取。

我需要对这个对象做两件事：

1. 将其传递给 SuperCSV csv 阅读器
2. 获取原始行并将它们保存在（Clojure）惰性序列中

目前，我不得不使用两种不同的 BufferedReader：一种作为 SuperCSV CSV 阅读器类的参数，另一种用于初始化原始行的惰性序列。我有效地下载了 S3 对象两次，这很昂贵（$）而且速度很慢。

我的一位同事指出，我正在寻找类似于 Unix“tee”命令的东西。一个 BufferedReader 可以以某种方式“拆分”，下载一大块数据，并将副本传递给惰性序列和 csv 阅读器功能将很有用。

我目前也在研究是否可以将惰性序列包装在 BufferedReader 中并将其传递给超级 csv。在将非常大的惰性序列传递给多个消费者时，我遇到了一些 Java 堆空间问题，所以我有点担心采用这种解决方案。

另一种解决方案是在本地下载文件，然后在该文件上打开两个流。这消除了流式传输背后的原始动机：允许在数据开始到达时立即开始处理文件。

最终的解决方案，也是我只有在没有其他方法的情况下才会考虑的解决方案，是实现我自己的 CSV 阅读器，它返回已解析的 CSV 和原始的未解析行。如果您使用了一个非常可靠的 CSV 阅读器，它可以返回已解析 CSV 数据的 Java Hash 和原始未解析行，请告诉我！

谢谢！

我正在实现一个类似跳棋的游戏，我需要一个序列来枚举给定配置的所有合法移动。

我有以下函数，直接从 C# 翻译而来：

它有效，但很尴尬，而且不完全是“F# 方式”，更不用说我偷偷怀疑我在这里所做的不是性能最佳的。

我想要的是将其“展平”为使用“迭代所有单元格”、“迭代来自该单元格的所有有效移动”的组合的东西。

以下是我希望结合的功能：

和

我将不向您详细说明我为使其发挥作用所做的各种尝试，因为它们都没有成功。但长话短说，我能想到的最好的方法是一个迭代器，它为每个产量返回一个序列，而不是我正在寻找的扁平版本，它会返回一个简单的 MoveStruct。

任何人都知道如何结合 AllCells 和 LegalMovesAround(x,y)？

问候， 阿列克斯

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

问题

1 流和惰性评估（40 分）

我们知道比较排序至少需要 O(n log n) 次比较，其中对 n 个元素进行排序。假设对于某个函数 f，我们只需要排序列表中的前 f(n) 个元素。如果我们知道 f(n) 渐近小于 log n，那么对整个列表进行排序将是一种浪费。我们可以实现一个惰性排序，它返回一个表示排序列表的流。每次访问流以获取排序列表的头部时，都会在列表中找到最小的元素。这需要线性时间。从列表中删除 f(n) 个元素将花费 O(nf(n))。对于这个问题，我们使用以下数据类型定义。还定义了一些辅助函数。

请注意，这些流不一定是无限的，但它们可以是无限的。

Q1.1 (20 分) 实现函数lazysort: int list -> int stream'。

它接受一个整数列表并返回一个表示排序列表的 int 流。这应该在恒定时间内完成。每次强制流'时，它都会给出 Empty 或 Cons(v, s')。在 cons 的情况下，v 是排序列表中的最小元素，s' 是表示剩余排序列表的流'。该力应该花费线性时间。例如：

相关定义

以下是作为代码给出的内容：

我的解决方案尝试

我尝试执行以下操作来获取 int 列表并将其转换为 int 流'：

但是当调用 force 时，它​​不会返回最小元素。我必须搜索最小值，但我不知道如何......我想像下面这样进行插入排序：

但是我必须搜索最小值并且不对列表进行排序，然后将其作为流...

任何帮助，将不胜感激。

考虑以下用例：
我想并行遍历 2 个 db 表，并在任一表中查找差异和差距/缺失记录。假设1）table的pk是一个Int ID字段；2）表格按ID顺序读取；3) 任一表中可能缺少记录（具有相应的序列间隙）。

我想在每个数据库上一次通过 - 使用惰性读取。（我的这个程序的初始版本使用序列对象和数据阅读器 - 不幸的是，对每个数据库进行了多次传递）。

我考虑过使用成对序列处理并在迭代中使用 Seq.skip 来尝试保持表处理同步。但是显然这非常慢，因为我 Seq.skip 的开销很高（在引擎盖下创建新序列），所以这可能是一个大表（比如 200k 记录）的问题。

我想这是一种常见的设计模式（比较来自不同来源的并发数据流）并且对类似项目的反馈/评论/链接感兴趣。

有人愿意发表评论吗？

我正在学习 Haskell，并遇到了以下代码：

就其工作方式而言，我在解析时遇到了一些麻烦。它非常简洁，我知道不需要更多，但我想了解 Haskell 如何在我编写时设法“填充”小谎言：

有什么帮助吗？

谢谢！