In Scala 2.8 collections, why was the Traversable type added above Iterable?

Question

I know that to be Traversable, you need only have a foreach method. Iterable requires an iterator method.

Both the Scala 2.8 collections SID and the "Fighting Bitrot with Types" paper are basically silent on the subject of why Traversable was added. The SID only says "David McIver... proposed Traversable as a generalization of Iterable."

I have vaguely gathered from discussions on IRC that it has to do with reclaiming resources when traversal of a collection terminates?

The following is probably related to my question. There are some odd-looking function definitions in TraversableLike.scala, for example:

def isEmpty: Boolean = {
  var result = true
  breakable {
    for (x <- this) {
      result = false
      break
    }
  }
  result
}

I assume there's a good reason that wasn't just written as:

def isEmpty: Boolean = {
  for (x <- this)
    return false
  true
}

Deka

Traversable is motivated in Ch. 24 of Programming in Scala, 2nd ed.; in some cases it is easier to implement efficiently foreach than iterator. – Bosomy

Regarding last question: github.com/scala/scala/pull/5101 – Coloquintida

Answer 1

I asked David McIver about this on IRC. He said he no longer remembered all of the reasons, but they included:

• "iterators are often annoying... to implement"

• iterators are "sometimes unsafe (due to setup/teardown at the beginning and end of the loop)"

• Hoped-for efficiency gains from implementing some things via foreach rather than via iterators (gains not necessarily yet actually demonstrated with the current HotSpot compiler)

Deka

Note that in the Scala 2.13 collections rewrite, we got rid of Traversable again and went back to an iterator-based design. – Deka

Answer 2

I suspect one reason is that it's a lot easier to write a concrete implementation for a collection with an abstract foreach method than for one with an abstract iterator method. For example, in C# you can write the implementation the GetEnumerator method of IEnumerable<T> as if it were a foreach method:

IEnumerator<T> GetEnumerator() 
{
    yield return t1;
    yield return t2;
    yield return t3;
}

(The compiler generates an appropriate state machine to drive the iteration through the IEnumerator.) In Scala, you would have to write your own implementation of Iterator[T] to do this. For Traversable, you can do the equivalent of the above implementation:

def foreach[U](f: A => U): Unit = {
  f(t1); f(t2); f(t3)
}

Carabin

I'm pretty new to scala, but since you don't actually return anything, couldn't you just write def foreach[U](f: A => U){f(t1); f(t2); f(t3) } ? – Perla

foreach states that it returns Unit and so discards the result of the body block f(t3) of type U. – Wolverhampton

Answer 3

just regarding your last question:

def isEmpty: Boolean = {
  for (x <- this)
    return false
  true
}

This gets roughly translated by the compiler to:

def isEmpty: Boolean = {
  this.foreach(x => return false)
  true
}

So you are simply not able to break out of foreach, isEmpty will always return true.

This is why "hacky" Breakable was constructed which breaks out of foreach by throwing a Control-Exception, catching it in breakable and returns.

Youthful

Actually you are wrong about return in scala. Scala does support Non-Local Returns. – Braunstein

Uh, this is astonishing, you're right. Has this always been valid?? – Youthful