Traversable => Итератор Java

Причина, по которой вы не можете лениво получить итератор из traversable, заключается в том, что вы по сути не можете этого сделать. Traversable определяет foreach, а foreach проходит через все без остановки. Нет там лени.

Итак, у вас есть два варианта, оба ужасные, чтобы сделать его ленивым.

Во-первых, вы можете перебирать все это каждый раз. (Я собираюсь использовать итератор Scala, но итератор Java в основном такой же.)

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
  }
}

Если у вас есть эффективная индексированная нарезка, все будет в порядке. Если нет, то каждый «следующий» займет время, линейное по длине итератора, в течение O(n^2) времени только для его прохождения. Но это также не обязательно лениво; если вы настаиваете на том, что это должно быть, вы должны применять O(n^2) во всех случаях и делать

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")
  }
}

Это явно ужасная идея для общего кода.

Другой способ — использовать поток и блокировать обход foreach по мере его выполнения. Правильно, вы должны выполнять межпотоковое взаимодействие при каждом доступе к элементу! Давайте посмотрим, как это работает — здесь я буду использовать потоки Java, так как Scala находится в процессе перехода на акторы в стиле Akka (хотя любой из старых акторов, акторов Akka, акторов Scalaz, акторов Lift или (и т.д.) будет работать)

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
  }
}

Это позволяет избежать катастрофы O(n^2), но связывает поток и обеспечивает отчаянно медленный поэлементный доступ. Я получаю около двух миллионов обращений в секунду на моей машине по сравнению с> 100M для типичного traversable. Это явно ужасная идея для общего кода.

Итак, у вас есть это. Traversable вообще не ленив, и нет хорошего способа сделать его ленивым без значительного ущерба для производительности.

Я сталкивался с этой проблемой раньше и насколько я Могу сказать, никто особенно не заинтересован в том, чтобы упростить получение Iterator, когда все, что вы определили, это foreach.

Но, как вы заметили, проблема toStream, поэтому вы можете просто переопределить это:

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!"))
  }
}

Другой альтернативой может быть определение Iterable вместо Traversable, и тогда вы получите метод iterator напрямую. Не могли бы вы немного подробнее объяснить, что делает ваш Traversable в вашем реальном случае использования?