Scala, extending the iterator

Question

Im looking to extended the iterator to create a new method takeWhileInclusive, which will operate like takeWhile but include the last element.

My issue is what is best practice to extend the iterator to return a new iterator which I would like to be lazy evaluated. Coming from a C# background I normal use IEnumerable and use the yield keyword, but such an option doesn't appear to exist in Scala.

for example I could have

List(0,1,2,3,4,5,6,7).iterator.map(complex time consuming algorithm).takeWhileInclusive(_ < 6)

so in this case the takeWhileInclusive would only have resolve the predicate on the values until I get the a result greater than 6, and it will include this first result

so far I have:

object ImplicitIterator {
  implicit def extendIterator(i : Iterator[Any]) = new IteratorExtension(i)
}

class IteratorExtension[T <: Any](i : Iterator[T]) {
  def takeWhileInclusive(predicate:(T) => Boolean) = ?
}

Chromolithography

Did you have had a look at Stream? – Swimmingly

A stream could definitely be more appropriate here in the example case, however I still have the same issue around how best to build the extension method – Chromolithography

Oh, takeWhileInclusive. My old takeTo.... – Extremism

Answer 1

This is one case where I find the mutable solution superior:

class InclusiveIterator[A](ia: Iterator[A]) {
  def takeWhileInclusive(p: A => Boolean) = {
    var done = false
    val p2 = (a: A) => !done && { if (!p(a)) done=true; true }
    ia.takeWhile(p2)
  }
}
implicit def iterator_can_include[A](ia: Iterator[A]) = new InclusiveIterator(ia)

Bookcraft

This is definitely an elegant solution to my problem, cheers! – Chromolithography

I'll take the functional version with neither vars nor vals, thanks! – Ninnette

@Ninnette - If you don't mind the extra overhead, that's a fine alternative. (Normally I wouldn't use a val for the function; I was just trying to separate things out for clarity here.) – Bookcraft

It was more the var I objected to! And I wasn't being particularly serious anyway – Ninnette

Answer 2

You can use the span method of Iterator to do this pretty cleanly:

class IteratorExtension[A](i : Iterator[A]) {
  def takeWhileInclusive(p: A => Boolean) = {
    val (a, b) = i.span(p)
    a ++ (if (b.hasNext) Some(b.next) else None)
  }
}

object ImplicitIterator {
  implicit def extendIterator[A](i : Iterator[A]) = new IteratorExtension(i)
}

import ImplicitIterator._

Now (0 until 10).toIterator.takeWhileInclusive(_ < 4).toList gives List(0, 1, 2, 3, 4), for example.

Dichromatic

Your method's last line can be written more succinctly as a ++ (b take 1) – Nonagon

Answer 3

The following requires scalaz to get fold on a tuple (A, B)

scala> implicit def Iterator_Is_TWI[A](itr: Iterator[A]) = new { 
     | def takeWhileIncl(p: A => Boolean) 
     |   = itr span p fold (_ ++ _.toStream.headOption)
     | }
Iterator_Is_TWI: [A](itr: Iterator[A])java.lang.Object{def takeWhileIncl(p: A => Boolean): Iterator[A]}

Here it is at work:

scala> List(1, 2, 3, 4, 5).iterator takeWhileIncl (_ < 4)
res0: Iterator[Int] = non-empty iterator

scala> res0.toList
res1: List[Int] = List(1, 2, 3, 4)

You can roll your own fold over a pair like this:

scala> implicit def Pair_Is_Foldable[A, B](pair: (A, B)) = new { 
    |    def fold[C](f: (A, B) => C): C = f.tupled(pair) 
    |  } 
Pair_Is_Foldable: [A, B](pair: (A, B))java.lang.Object{def fold[C](f: (A, B) => C): C}

Ninnette

Answer 4

class IteratorExtension[T](i : Iterator[T]) {
  def takeWhileInclusive(predicate:(T) => Boolean) = new Iterator[T] {
    val it = i
    var isLastRead = false

    def hasNext = it.hasNext && !isLastRead
    def next = {
      val res = it.next
      isLastRead = !predicate(res)
      res
    }
  }
}

And there's an error in your implicit. Here it is fixed:

object ImplicitIterator {
  implicit def extendIterator[T](i : Iterator[T]) = new IteratorExtension(i)
}

Extremism

This was where my thinking was heading, thank you for getting there for me! It does offer a good generalised approach. I wish there was a more elegant general solution then having to construct a new iterator. – Chromolithography

Answer 5

scala> List(0,1,2,3,4,5,6,7).toStream.filter (_ < 6).take(2)
res8: scala.collection.immutable.Stream[Int] = Stream(0, ?)

scala> res8.toList 
res9: List[Int] = List(0, 1)

After your update:

scala> def timeConsumeDummy (n: Int): Int = {
     | println ("Time flies like an arrow ...") 
     | n }
timeConsumeDummy: (n: Int)Int

scala> List(0,1,2,3,4,5,6,7).toStream.filter (x => timeConsumeDummy (x) < 6) 
Time flies like an arrow ...
res14: scala.collection.immutable.Stream[Int] = Stream(0, ?)

scala> res14.take (4).toList 
Time flies like an arrow ...
Time flies like an arrow ...
Time flies like an arrow ...
res15: List[Int] = List(0, 1, 2, 3)

timeConsumeDummy is called 4 times. Am I missing something?

Swimmingly

Sorry the example isn't the specific case I'm looking to solve, I will include a more in-depth example to illustrate what I am after – Chromolithography

@JPullar: Your take (2) has vanished and changed place with (_ < 6), while the timeConsumingMethod is on the left of (_ < 6) now. So does (timeConsumingMethod) produce an Int as result, which is compared to (_ < 6) now, or is it the initial List element, which has to be below 6? – Swimmingly

What your showing is correct and what I am after in the lazy evaluation. My issue however, is to emulate how the filter function is evaluating lazily in a custom extension method – Chromolithography

So if timeConsumeDummy returns 2*n - 1, all computations get performed, that's true. – Swimmingly