Нестрогие, неизменяемые, незапоминаемые бесконечные серии в Scala

Мне нужен бесконечный нестрогий ряд x₁, x₂, x₃... чтобы я мог работать с одним элементом за раз , не запоминая результаты, чтобы поддерживать постоянное использование памяти. Ради конкретики скажем, что это ряд целых чисел (например, натуральные числа, нечетные числа, простые числа), хотя этот вопрос может относиться к более общим типам данных.

Самый простой способ работать с бесконечными списками — использовать объект Stream в Scala. Распространенной идиомой является написание функции, которая возвращает 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, но на практике это может быть сложно. Я могу реализовать код с бесконечным списком, в котором, как мне кажется, думаю, я не удерживаю какие-либо заголовки потока, но если у него все еще есть неограниченные требования к памяти, я должен выяснить, не заключается ли проблема в том, что я m обрабатывая мои потоки каким-то образом, который вызывает мемоизацию или что-то еще. Это может быть трудной задачей отладки и иметь запах кода, потому что я пытаюсь обмануть явно запомненную структуру данных, чтобы она возвращала не запомненный результат.

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

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

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

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

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

1. 3x(шансы, начиная с 3) (т.е. 9,12,15...)
2. 5x(шансы начиная с 5) (т.е. 25,30,35...)

Вышеприведенное не компилируется, потому что odds.map(...) возвращает Iterator, а не NumericSeries и, следовательно, не может быть добавлен в очередь приоритетов.

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