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

Question

我想要一个无限的非严格系列 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 习语的例子。)

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

我想要的是具有 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因此不能添加到优先级队列中。

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

Answer 1

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

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

好的，我的第二次尝试。为了保持 map 的懒惰行为, filter等，最好的可能是子类 SeqView 或 StreamView :

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)