Нестрогая, неизменяемая, не 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 и, следовательно, не может быть добавлен в очередь приоритетов.

На данный момент похоже, что я пробираюсь в расширения классов коллекций, и это сложно, поэтому я хочу убедиться, что мне не нужно это делать, если это абсолютно необходимо.