Scala中的非严格、不可变、非记忆化的无限序列。

Question

我想要一个无限的非严格序列 x₁, x₂, x₃...，我可以一次处理一个元素，不将结果存储在内存中以保持内存使用量恒定。为了具体说明，让我们假设它是整数序列（例如自然数、奇数、质数），尽管这个问题可能适用于更一般的数据类型。

处理无限列表的最简单方法是使用 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的头部，则避免了记忆化，但实际上这可能很棘手。我可能会实现无限列表代码，在其中我认为我没有保留任何流头部，但如果它仍然具有无界内存需求，我必须弄清楚问题是我以某种方式处理我的流导致了记忆化，还是其他原因。这可能是一项困难的调试任务，并且具有代码气味，因为我试图欺骗一个明确记忆化的数据结构返回一个非记忆化的结果。

我想要的是具有流语义但不带有记忆化的对象。在Scala中似乎不存在这样的对象。我一直在尝试使用迭代器实现无限数字序列，但是当您开始想要对它们进行理解操作时，迭代器的可变性使得这很棘手。我还尝试从头编写自己的代码，但不清楚应该从哪里开始（我应该子类化Traversable吗？）或如何避免重新实现map，fold等功能。

是否有人有良好的Scala示例代码，用于实现非严格、不可变、非记忆化的无限列表？

更普遍地说，我理解可遍历、可迭代、序列、流和视图的语义，但是我发现这个问题如此令人烦恼，让我感到自己可能误解了什么。在我看来，非严格性和非记忆化完全是正交的属性，但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。还要注意，这里无限序列的基础是奇数，但最普遍的解决方案涉及更复杂的序列。在主函数结束时，我希望队列包含两个无限序列：

1. 3x(从3开始的奇数) (即9,12,15...)
2. 5x(从5开始的奇数) (即25,30,35...)

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

此时，看起来我正在深入集合类扩展，这很棘手，所以我想确保只有在绝对必要的情况下才需要这样做。

- W.P. McNeill

---

你能否举个例子说明 Iterator 的局限性？我通常使用 Iterator，但你可能需要一些技巧才能让它在所有你想要的情况下正常工作。因此，如果我们能看到一个天真方法失败的例子，也许我们可以提供帮助。 - Rex Kerr

在我的实际应用程序中（Melissa O'Neill筛选法算法的实现），我传递这些序列并调用map和tail操作，最终迫使我编写样板代码，如复制构造函数。我有一个非常干净的源代码版本Stream，但它会耗尽内存。 - W.P. McNeill

你能展示一下你想要避免的样板代码的最小化例子吗？此外，某种程度的记忆化是它成为高效算法的全部原因。 - Rex Kerr

我现在正在努力想出一个简化的例子，这很棘手。为了实现O'Niell算法，您需要使用后继函数生成无限整数列表，并且您需要能够使用map(_ * x)将该系列转换为具有不同缩放因子的多个其他系列，这些系列都可以独立地推进。 - W.P. McNeill

Answer 1

编辑：下面的方法在使用filter或map时不能保留Generator类型；实际上，尝试为生成器实现完整的“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的建议，将其称为“生成器”（Generator）。

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

- 0__

---

你想让 Generator 扩展 SeqView 还是 StreamView？（在上面的代码片段中，你有后者吗？） - W.P. McNeill

我认为你已经有了一个良好的开端 (+1)，但是你可能需要添加相当多的特性，以避免在你想要生成器时，随机方法会向你抛出 SeqView (或 StreamView)。 - Rex Kerr

StreamView是SeqView的子类。尽管名称如此，但它不会进行记忆化处理。这似乎是最直接的方法。上述代码唯一还没有实现的是，在调用map时返回一个Generator而不是StreamView。 - 0__

我尝试了你在这里概述的方法，使用map和filter返回一个Generator对象，但是由于我的序列是无限的构造，所以不清楚建造者语义应该是什么，因为建造者似乎想要成为有限的可变对象（如ArrayBuffer或其他类似对象）。 - W.P. McNeill

Answer 2

如果你只需要能够多次递归遍历列表，请尝试使用 Unit => Iterator[A] 而不是原始列表，可以尝试进行以下重构：

// Old way
val i = Iterator.tabulate(5)(_ + 2)
val j = i.map(_*5)
val k = i.map(_*3)
println(j.mkString(" "))  // Prints 10, 15, 20, 25, 30 as it should
println(k.mkString(" "))  // Prints nothing!  (i was used up!)

// New way
val f = (u: Unit) => Iterator.tabulate(5)(_+2)
val g = f andThen (_.map(_*5))
val h = f andThen (_.map(_*3))
println(g(()).mkString(" "))  // 10, 15, 20, 25, 30
println(h(()).mkString(" "))  // 6, 9, 12, 15, 18

但这一切都需要从头开始重新工作。如果您需要从中间生成新的工作，也有一种方法可以做到，只要您愿意存储在您已经完成的进度之间的所有中间元素：

val a = Iterator.tabulate(5)(_+2)
val (a1,a2) = a.duplicate
val c = a1.map(_*5)
val d = a2.map(_*3)
println(c.mkString(" "))  // 10, 15, 20, 25, 30...but stores a=2, 3, 4, 5, 6
println(d.mkString(" "))  // 6, 9, 12, 15, 18

如果以上两种模式都不够好，那么您将需要在集合库中创建一个类——也许叫做Generator？——它将完全按照您的要求执行。我会让它继承Iterator或Iterable，覆盖或创建一个duplicate方法，该方法将使用内部生成函数和数据处于相同状态的方式创建两个新副本。

- Rex Kerr

---

看起来我需要采用继承Iterator的自定义方法。扩展集合类是Scala中唯一令我感到困惑的方面。我从不知道该从哪里开始。 - W.P. McNeill

@W.P.McNeill - 我认为你必须咬紧牙关并开始（在指导下！）。考虑到你的应用程序，我怀疑你会发现它不会按照你想要的方式工作（但我仍然会在这里留下答案，以供那些可能有较少要求的任务的人参考）。 - Rex Kerr

Answer 3

希望这是最直接的方法。只需创建一个惰性的Iterable:

object Generator {
  def apply[A](head: A)(next: A => A): Generator[A] = {
    val _head = head
    new collection.IterableView[A, Nothing] {
      override def head = _head
      def underlying = sys.error("No underlying structure")
      def iterator = Iterator.iterate(head)(next)
    }
  }
}
type Generator[A] = Iterable[A]

这是使用案例：

val q = collection.mutable.PriorityQueue[Generator[Int]]()
val odds = Generator(3)(_ + 2)
q += odds.map(odds.head * _)
val next = odds.tail
q += next.map(next.head * _)
q.last.take(3).mkString(",") // -> 9,12,21
q.head.take(3).mkString(",") // -> 25,35,45

- 0__

Answer 4

编辑: 我把这个答案留在这里供参考，但我发现，为了避免堆栈溢出，最好使用默认为lazy的集合：SeqView -> 请查看我的其他答案。

---

如果你想定义一个新的集合类型，这是我所想象的：

import collection.generic.{GenericTraversableTemplate, GenericCompanion}
import collection.immutable.LinearSeq

final case class InfSeq[A](override val head: A, fun: A => A)
extends LinearSeq[A] with GenericTraversableTemplate[A, List] {
  override def companion: GenericCompanion[List] = List

  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
  }

  def length            = Int.MaxValue  // ?
  override def isEmpty  = false  
  override def tail     = InfSeq(fun(head), fun)
  override def toString = take(4).mkString("InfSeq(", ",", ",...)")
}

例子。

val i = InfSeq[Int](2, _ * 2 + 3)
i.take(4).foreach(println)

显然，这还没有解决map、filter等功能。但是如果你小心地使用.view，那么应该没问题：

val j = i.view.map(_ * 0.5)
j.take(4).foreach(println)

- 0__