scala - Scala 中的非严格、不可变、非记忆化的无限系列

我想要一个无限的非严格系列 x1、x2、x3...，我可以一次处理一个元素，而不是记住结果以保持我的内存使用不变。为了具体起见，我们假设它是一系列整数(例如自然数、奇数、素数)，尽管这个问题可能适用于更一般的数据类型。

使用无限列表的最简单方法是使用 Scala 的 Stream 对象。一个常见的习惯用法是编写一个返回 Stream 的函数，使用 #:: 运算符向系列添加一个术语，然后递归调用自身。例如，下面给出一个起始值和一个后继函数，生成一个无限的整数流。

  def infiniteList(n: Int, f: Int => Int): Stream[Int] = {
      n #:: infiniteList(f(n), f)
  }
  infiniteList(2, _*2+3).take(10) print
  // returns 2, 7, 17, 37, 77, 157, 317, 637, 1277, 2557, empty

(我意识到上面的等价于库调用 Stream.iterate(2)(_*2+3) 。我在这里写它作为这个无限 Stream 习语的例子。)

然而，流会记住它们的结果，这使得它们的内存需求非常大，并且可能非常大。如果您不捕获 Stream 的头部，则可以避免内存的 documentation states ，但实际上这可能很棘手。我可能会实现无限列表代码，其中我认为我没有捕获任何流头，但是如果它仍然有无限的内存需求，我必须弄清楚问题是否是我以某种方式处理我的流这确实会导致内存，或者是其他原因。这可能是一项困难的调试任务并且有代码异味，因为我试图欺骗一个显式记忆化的数据结构返回一个非记忆化的结果。

我想要的是具有 Stream 没有内存的语义的东西。 Scala 中似乎不存在这样的对象。我一直在尝试使用迭代器来实现无限数字序列，但是当您开始想要对它们进行理解操作时，迭代器的可变性使这变得棘手。我也尝试从头开始编写自己的代码，但不清楚我应该从哪里开始(我应该继承 Traversable 吗？)或者如何避免重新实现 map、fold 中的功能

有人有一个很好的示例 Scala 代码来实现一个非严格的、不可变的、非记忆化的无限列表吗？

更一般地说，我理解 semantics of traversable, iterable, sequence, stream, and view ，但我发现这个问题如此令人烦恼的事实让我觉得我误解了一些东西。在我看来，非严格性和非内存性是完全正交的属性，但 Scala 似乎做出了一个设计决定，将它们统一在 Stream 中，并且没有简单的方法将它们分开。这是对 Scala 的疏忽，还是我忽略的非严格性和非内存性之间存在某种深层联系？

我意识到这个问题相当抽象。这是将其与特定问题联系起来的一些附加上下文。

我在实现 Meissa O'Niell 的论文“The Genuine Sieve of Eratosthenes”中描述的素数生成器的过程中遇到了这个问题，并且很难给出一个简单的例子来说明 Iterator 对象在不从那张纸。这是一个使用 streams 的完整实现，它非常优雅，但内存消耗大得令人怀疑。

这是一个带有迭代器的简化实现，它不会编译，但可以让您了解我想要什么。

import scala.collection.mutable

object ONeillSieve {

  class NumericSeries extends BufferedIterator[Int] with Ordered[NumericSeries] {
    def hasNext = true

    def compare(that: NumericSeries) = that.head.compare(head)

    override def toString() = head + "..."

    var head = 3

    def next() = {
      val r = head
      head += 2
      r
   }
 }

def main(args: Array[String]) {
    val q = mutable.PriorityQueue[NumericSeries]()

    val odds = new NumericSeries

    q += odds.map(odds.head * _)
    odds.next()
    q += odds.map(odds.head * _)

    println("Sieve = %s\nInput = %s".format(q, odds))
  }
}

我需要构建一个无限数字系列的 PriorityQueue，以最小元素为键。 (因此我使用 BufferedIterator 而不是简单的 Iterator 。)还要注意，这里无限级数的基础是奇数，但最通用的解决方案涉及更复杂的级数。在主函数的末尾，我希望队列包含两个无限系列:

3x(赔率从 3 开始)(即 9,12,15...)

5x(赔率从 5 开始)(即 25,30,35...)

上述内容无法编译，因为 odds.map(...) 返回 Iterator ，而不是 NumericSeries ，因此无法添加到优先级队列中。

在这一点上，我似乎正在涉足集合类扩展，这很棘手，所以我想确保除非绝对必要，否则我不必这样做。

最佳答案

编辑: 当使用 Generator 或 0x251843124 时，以下不保留 filter 类型；实际上，尝试为生成器实现完整的“MyType”几乎是不可能的(查看 map 源代码以了解困惑情况)。

但是有一个更简单的方法(见我的第三个答案)

好的，我的第二次尝试。为了保持 IndexedSeqView 、 map 等的惰性行为，最好的方法是将 filter 或 SeqView 子类化:

import collection.immutable.StreamView

final case class Generator[A](override val head: A, fun: A => A)
extends StreamView[A, Generator[A]] {
  protected def underlying = this
  def length: Int = Int.MaxValue  // ?
  def iterator = Iterator.iterate(head)(fun)
  def apply(idx: Int): A = {
    if(idx < 0) throw new IndexOutOfBoundsException(idx.toString)
    var res = head
    var i = idx; while(i > 0) {
      res = fun(res)
      i -= 1
    }
    res
  }
}

(我接受了 Rex 的建议，称其为“生成器”)。

val i = Generator[Int](2, _ * 2 + 3)
i.take(4).foreach(println)
val j = i.map(_ * 0.5)
j.take(4).foreach(println)

关于scala - Scala 中的非严格、不可变、非记忆化的无限系列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14298139/