Нестрогая, неизменяемая, не memoized Бесконечная серия в Scala

Мне нужен бесконечный нестрогий ряд 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 идиомы.)

Однако потоки запоминают их результаты, делая их требования к памяти непостоянными и потенциально очень большими. В документации говорится о том, что memoization можно избежать, если вы не держитесь за голову Stream, но на практике это может быть сложно, Я могу реализовать бесконечный код списка, в котором я не думаю, что я держусь за любые потоковые заголовки, но если у него все еще есть неограниченные требования к памяти, я должен выяснить, является ли проблема в том, что я обрабатываю свои потоки каким-то образом что действительно вызывает воспоминания, или если это что-то еще. Это может быть сложной задачей отладки и имеет запах кода, потому что я пытаюсь обмануть явно memoized структуру данных, чтобы вернуть не memoized результат.

Я хочу что-то с семантикой Stream ожидать без memoization. Похоже, что такой объект существует в Scala. Я экспериментировал с использованием итераторов для реализации бесконечных числовых рядов, но изменчивость итераторов делает это сложным, когда вы начинаете хотеть делать операции по их пониманию. Я также попытался написать свой собственный код с нуля, но не ясно, где я должен начать (должен ли я подкласс Traversable?), Или как избежать переопределения функциональности в map, fold и т.д.

Есть ли у кого-нибудь хороший пример Scala код реализации нестрого, неизменяемого, не memoized бесконечного списка?

В более общем смысле, я понимаю семантику пересекающихся, повторяющихся, последовательностей, потоков и просмотров, но тот факт, что я нахожу этот вопрос настолько досадным, заставляет меня чувствовать Я что-то недопонимаю. Мне кажется, что не строгость и не memoization являются полностью ортогональными свойствами, но Scala, по-видимому, принял конструктивное решение объединить их в Stream и не дал простой возможности очистить их. Является ли это надзором в части Scala или существует некоторая глубокая связь между нестрогой и не-memoization, которую я пропускаю?

Я понимаю, что вопрос довольно абстрактный. Вот еще один дополнительный контекст, который связывает его с конкретной проблемой.

Я столкнулся с этой проблемой в ходе реализации генератора простых чисел, как описано в статье Мейссы О'Нилл " Подлинное сито Эратосфена", и трудно дать простой пример того, где объект 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 бесконечной числовой серии, набитой их наименьшим элементом. (Поэтому я использую BufferedIterator вместо простого Iterator.) Также обратите внимание, что здесь основой для бесконечных рядов являются нечетные целые числа, но наиболее общее решение включает более сложные ряды. В конце основной функции я хочу, чтобы очередь содержала две бесконечные серии:

• 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)

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

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

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)

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