Is using Scala's Iterator ++ (concat) recursively stack-safe?

Question

Suppose you are using an API that allows you to scroll through a resultset in pages. Each page returns an ID for the subsequent page.

It's an established idiom that you can use Scala Iterator and its lazy concat (++) operator recursively to do this:

def allResults: Iterator[Result] = {
  def nextPage(pageId: String): Iterator[Result] = {
    val page = invoke api
    Iterator(page.results) ++ nextPage(page.nextPageId)
  }
  val firstPage = invoke api
  Iterator(firstPage.results) ++ nextPage(firstPage.nextPageId)
}

Is this idiom stack-safe? Or are there other efficiency gotchas to worry about?

score 2 · Answer 1 · answered Jun 23 '17 at 19:38

I believe this is stack-safe, specifically because of the fact that the ++ method takes a call-by-name parameter, as you mentioned.

This will work for Iterators and Streams, but not for "non-lazy" collections like Lists and Maps.

In those cases, you should use an accumulator and annotate your method with @tailrec to be sure that you won't use up more stack than expected as in https://stackoverflow.com/a/3114248/854793

score 1 · Answer 2 · answered Sep 26 '17 at 22:20

I get a StackOverflowError on Scala 2.11.11 when using Iterator.++ but not when using Stream.#::. I think this must be a bug in Iterator.++ in Scala 2.11.11. On Scala 2.12.2 both work:

def iter(n: Int): Iterator[Int] = if (n <= 0) Iterator.empty else { Iterator.single(n) ++ iter(n - 1) } iter(100000).foreach(print)

That leads to a StackOverflowError on Scala 2.11.11 but on Scala 2.12.2 it works fine. Using Stream.#:: works fine on both as well. Perhaps this is a bug in Scala 2.11.11?

def stream(n: Int): Stream[Int] = if (n <= 0) Stream.empty else { n #:: stream(n - 1) } stream(1000000).foreach(print)

Is using Scala's Iterator ++ (concat) recursively stack-safe?

2 Answers2