Scala Streams и их использование стековой памяти

Question

Предположим, у меня есть рекурсивно определенный Stream: например,

def from(n:Int):Stream[Int] = Stream.cons(n, from(n+1))

Я думаю, это требует постоянной памяти стека. Это правильно? Правильно ли это для любого рекурсивно определенного stream? Можете ли вы вспомнить какой-нибудь рекурсивно определенный пример stream, который использует непостоянную память стека?

Answer 1

Вы спрашиваете, требует ли доступ к потоку постоянной памяти стека?

Если да, то ответ да: apply для Stream s определяется в терминах drop (определение в LinearSeqOptimized), а drop является хвост-рекурсивным , поэтому компилируется в цикл while.

Это делает drop по сути следующим образом:

def drop(n: Int) : Stream[A] = {
  var _this = this
  var _n = n

  while(!(_n <= 0 || _this.isEmpty)) {
    _this = _this.tail
    _n = _n - 1
  }
  _this
}

Таким образом, единственное увеличение размера стека может произойти из-за вызова _this.tail. В вашем определении from этот вызов никогда не увеличит стек: все, что он делает, это создает экземпляр Stream.cons (поскольку рекурсивный вызов фактически не оценивается в этой точке).