Traversable => Java Iterator

Question

I have Traversable and I want to make it in Java Iterator. My problem is that I want everything to be done lazily. If I do .Itator on a workaround, it readily produces the result, copies it to the list, and returns an iterator over the list.

I am sure I am missing something simple here ...

Here is a small test case that shows what I mean:

class Test extends Traversable[String] { def foreach[U](f : (String) => U) { f("1") f("2") f("3") throw new RuntimeException("Not lazy!") } } val a = new Test val iter = a.toIterator 

Answer 1

The reason you can't lazily get an iterator from a workaround is because you essentially can't. Traversable defines foreach , and foreach runs all without stopping. No laziness there.

So, you have two options, both terrible, in order to make him lazy.

First of all, you can iterate over it every time. (I'm going to use Iterator Scala, but the Java Iterator is basically the same.)

 class Terrible[A](t: Traversable[A]) extends Iterator[A] { private var i = 0 def hasNext = i < t.size // This could be O(n)! def next: A = { val a = t.slice(i,i+1).head // Also could be O(n)! i += 1 a } } 

If you have efficient index slicing, this will be fine. If not, each "next" will take time linear along the length of the iterator, for O(n^2) time, just to move it. But that too is not necessarily lazy; if you insist that in all cases you need to enforce O(n^2) and do

 class Terrible[A](t: Traversable[A]) extends Iterator[A] { private var i = 0 def hasNext: Boolean = { var j = 0 t.foreach { a => j += 1 if (j>i) return true } false } def next: A = { var j = 0 t.foreach{ a => j += 1 if (j>i) { i += 1; return a } } throw new NoSuchElementException("Terribly empty") } } 

This is clearly a terrible idea for generic code.

Another way is to use the thread and block foreach traversal as it moves. That's right, you must do cross-threading every time you access an element! Let's see how it works. I will use Java themes here, since Scala is in the middle of the transition to Akka style actors (although any of the old actors or Akka actors or Scalaz or Lift actors, actors or (etc.) will work)

 class Horrible[A](t: Traversable[A]) extends Iterator[A] { private val item = new java.util.concurrent.SynchronousQueue[Option[A]]() private class Loader extends Thread { override def run() { t.foreach{ a => item.put(Some(a)) }; item.put(None) } } private val loader = new Loader loader.start private var got: Option[A] = null def hasNext: Boolean = { if (got==null) { got = item.poll; hasNext } else got.isDefined } def next = { if (got==null) got = item.poll val ans = got.get got = null ans } } 

This avoids the O(n^2) disaster, but binds the stream and desperately slows down phased access. I get about two million hits per second on my machine, compared to s> 100M for a typical crossover. This is definitely a terrible idea for generic code.

So you have it. Traversable is not lazy at all, and there is no good way to make it lazy without compromising performance tremendously.

Answer 2

I ran into this problem before and as far as I can tell, no one is particularly interested in making Iterator easier to get when all you have defined is foreach .

But, as you already noted, the problem is toStream , so you can just override this:

 class Test extends Traversable[String] { def foreach[U](f: (String) => U) { f("1") f("2") f("3") throw new RuntimeException("Not lazy!") } override def toStream: Stream[String] = { "1" #:: "2" #:: "3" #:: Stream[String](throw new RuntimeException("Not lazy!")) } } 

Another alternative would be to define Iterable instead of Traversable , and then you will get the Iterator method directly. Could you explain a little more what makes your Traversable in your actual use case?