Early-termination foldLeft for Scala Streams

The foldRight and foldLeft methods for Scala Streams cannot terminate early, so here is my attempt to provide that functionality through the "enrich my library" pattern:

implicit class StreamWithLazyFold[A](s: Stream[A]) {
    def foldLeft1[B](z: B)(f: (B, A) => (B, Boolean)): B = s match {
      case _ if s.isEmpty => z
      case h #:: t => {
        val (z1, stop) = f(z, h.asInstanceOf[A])
        if(stop) z1
        else t.asInstanceOf[Stream[A]].foldLeft1(z1)(f)
      }
    }
  }

Test:

s.foldLeft1(true)((x, y) => {
    println("run!")
    val b = (y < 3) && x
    (b, !b)
  })

It prints "run!" only 3 times.

One question arises immediately: how do I generalize this to all Seqs?

All suggestions are welcome, of course.

Your foldLeft1 method looks fine.

• You don't need asInstanceOf. You pattern match a Stream[A] so the head will always be A and the tail Stream[A].

• A case block doesn't need parentheses, but this is mostly a choice of preferred style.

The second case block could then look like :

case h #:: t => 
  val (z1, stop) = f(z, h)
  if (stop) z1 else t.foldLeft1(z1)(f)

If we want to generalize your foldLef1 method, we can see that foldLeft is implemented in TraversableOnce for Stream, List, ... (source on GitHub). So we could create an implicit class for TraversableOnce.

We cannot use pattern matching if we are using TraversableOnce to get the current element and the rest elements. If we look at the implementation of foldLeft for inspiration, we can see that it uses foreach and a mutable variable. That is no good in our case since we don't (necessarily) want to loop over all the elements of our collection (or iterator, ...).

We can use toIterator to get an Iterator to loop over our elements, and with an Iterator we can stop iterating whenever we want, that looks just like we want.

We can adjust the code of your foldLeft1 for Stream to use an Iterator :

implicit class FoldLazy[A](trav: TraversableOnce[A]) {
  def foldLeft1[B](z: B)(f: (B, A) => (B, Boolean)) = {
    def go(it: Iterator[A], z: B): B = 
      if (it.hasNext) {
        val (z1, stop) = f(z, it.next)
        if (stop) z1 else go(it, z1)
      } else z
    go(trav.toIterator, z)
  }
}

Which we can use :

Stream(1,2,3).foldLeft1(0)((acc, elem) => (acc + elem, elem % 2 == 0))  // 3
List(1,2,3).foldLeft1(0)((acc, elem) => (acc + elem, elem % 2 == 0))    // 3
Vector(1,2,3).foldLeft1(0)((acc, elem) => (acc + elem, elem % 2 == 0))  // 3

Note that this doesn't work for Array, since Array is only a TraversableOnce through ArrayOps or WrappedArray, and the Scala compiler doesn't apply multiple (nested) implicit conversions.

StackExchange Code Review Q#108803, answer score: 4