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的头部,那么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”中描述的实现一个素数生成器的过程中,我遇到了这个问题,很难给出一个简单的例子,说明迭代器对象在哪里是不够的,而不会从中提取很多细节那纸.这是一个使用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 = %snInput = %s".format(q,odds))
  }
}

我需要建立一个由他们最小的元素键入的无限数字序列的PriorityQueue. (因此,我使用一个BufferedIterator而不是一个简单的迭代器.)另请注意,这里无限系列的基础是奇数整数,但最通用的解决方案涉及更复杂的系列.在主函数结束时,我希望队列包含两个无限序列：

> 3x(从3开始的赔率)(即9,12,15 …)
> 5x(从5开始的赔率)(即25,30,35 …)

上面没有编译,因为odds.map(…)返回一个Iterator,而不是一个NumericSeries,因此不能被添加到优先级队列中.

在这一点上,看起来我正在进入集合类扩展,这很棘手,所以我想确保我不需要这样做,除非绝对必要.

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
  }
}

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