In Scala, how to work around TraversableLike.toIterator's inefficient intermediate Stream

Question

(Gen)TraversableOnce.toIterator is overridden in TraversableLike as toStream.iterator, causing an intermediate stream to occur.

As a simple example, say I'm trying to implement a simple izip utility that always coerces its arguments to iterators before calling zip so as to yield an efficient iterator over both collections.

The following is inefficient (due to the intermediate Stream):

def izip[A,B](xs: TraversableOnce[A], ys: TraversableOnce[B]) =
  xs.toIterator zip ys.toIterator

and must be expanded to:

def izip[A,B](xs: Iterable[A], ys: Iterable[B]) =
  xs.iterator zip ys.iterator
def izip[A,B](xs: Iterator[A], ys: Iterable[B]) =
  xs zip ys.iterator
def izip[A,B](xs: Iterable[A], ys: Iterator[B]) =
  xs.iterator zip ys
def izip[A,B](xs: Iterator[A], ys: Iterator[B]) =
  xs zip ys
// .. and more needed to handle Traversables as well

Is there a better way?

Answer 1

I think that traits guarantee only the existence of a given method, not its implementation. They can provide a default implementation, but subtype can override it.

So even if TraversableLike provides an implementation for toIterator, the actual implementation of the object you pass will be used.

If you have performance problems with standard collections, perhaps the real issue is elsewhere. If it's a custom collection, you should override toIterator with a sensible definition.