12

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

使用无限列表最简单的方法是使用 Scala 的Stream对象。一个常见的习惯用法是编写一个返回 a 的函数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成语的例子。）

但是，流会记住它们的结果，从而使它们的内存需求非常不稳定，并且可能非常大。文档指出，如果您不抓住 a 的头部，就可以避免记忆Stream，但实际上这可能很棘手。我可能会实现无限列表代码，我认为我不会在其中保留任何流头，但如果它仍然有无限的内存需求，我必须弄清楚问题是否在于我正在以某种方式处理我的流这确实会导致记忆，或者如果它是其他东西。这可能是一项困难的调试任务并且有代码味道，因为我试图欺骗显式记忆的数据结构以返回非记忆的结果。

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

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

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

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

我在实施 Meissa O'Niell 的论文“ The Genuine Sieve of Eratosthenes ”中描述的素数生成器的过程中遇到了这个问题，并且很难给出一个简单的例子来说明一个Iterator对象是不合适的而不拉入很多那篇论文的细节。这是一个使用 流的完整实现，它非常优雅，但内存消耗非常大。

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

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由它们的最小元素键入的无限数字系列。（因此我使用 aBufferedIterator而不仅仅是一个普通的Iterator。）还要注意，这里无限级数的基础是奇数，但最通用的解决方案涉及更复杂的级数。在主函数结束时，我希望队列包含两个无限系列：

  1. 3x（赔率从 3 开始）（即 9,12,15...）
  2. 5x（赔率从 5 开始）（即 25,30,35...）

以上无法编译，因为odds.map(...)返回的是Iteratora ，而不是 a NumericSeries，因此无法添加到优先级队列中。

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

4

4 回答 4

3

编辑：Generator使用filteror时，以下内容不保留类型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)
于 2013-01-12T22:51:59.503 回答
1

如果您只需要能够多次递归列表，请尝试使用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可以称之为它吗？——这将完全符合您的要求。我让它继承自Iteratoror Iterable，覆盖或创建一个duplicate方法，该方法将创建两个新副本，内部生成函数和数据处于相同状态。

于 2013-01-12T22:22:24.960 回答
1

希望这是最直接的方法。只需创建一个惰性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
于 2013-01-13T00:33:55.857 回答
0

编辑：我在这里留下这个答案以供参考，但我发现不要遇到堆栈溢出，最好使用默认情况下惰性的集合：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)
于 2013-01-12T22:27:09.493 回答