foldLeft early termination in a Stream[Boolean]?

Question

I have a:

val a : Stream[Boolean] = ...

When I foldLeft it as follows

val b = a.foldLeft(false)(_||_)

Will it terminate when it finds the first true value in the stream? If not, how do I make it to?

Answer 1

It would not terminate on the first true. You can use exists instead:

val b = a.exists(identity)

Answer 2

No it won't terminate early. This is easy to illustrate:

val a : Stream[Boolean] = Stream.continually(true)
// won't terminate because the strea
val b = a.foldLeft(false)(_||_)

stew showed that a simple solution to terminate early, in your specific case, is

val b = a.exists(identity).

Even simpler, this is equivalent to:

val b = a.contains(true)

A more general solution which unlike the above is also applicable if you actually need a fold, is to use recursion (note that here I am assuming the stream is non-empty, for simplicity):

def myReduce( s: Stream[Boolean] ): Boolean = s.head || myReduce( s.tail )
val b = myReduce(a)

Now the interesting thing of the recursive solution is how it can be used in a more general use case where you actually need to accumulate the values in some way (which is what fold is for) and still terminate early. Say that you want to add the values of a stream of ints using an add method that will "terminate" early in a way similar to || (in this case, it does not evaluate its right hand side if the left hand side is > 100):

def add(x: Int, y: => Int) = if ( x >= 100 ) x else x + y
val a : Stream[Int] = Stream.range(0, Int.MaxValue)
val b = a.foldLeft(0)(add(_, _))

The last line won't terminate, much like in your example. But you can fix it like this:

def myReduce( s: Stream[Int] ): Int = add( s.head, myReduce( s.tail ) )
val b = myReduce(a)

WARNING: there is a significant downside to this approach though: myReduce here is not tail recursive, meaning that it will blow your stack if iterating over too many elements of the stream. Yet another solution, which does nto blow the stack, is this:

val b = a.takeWhile(_ <= 100).foldLeft(0)(_ + _)

But I fear I have gone really too far on the off topic side, so I'd better stop now.

Answer 3

You could use takeWhile to extract the prefix of the Stream on which you want to operate and then apply foldLeft to that.