5

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?

kiritsuku
  • 52,967
  • 18
  • 114
  • 136
Pinch
  • 2,768
  • 3
  • 28
  • 44
  • 2
    @stew's answer is the sane way to do it but if you're just looking for recommended ways to exit a fold early, there's a more general and pretty comprehensive answer here: http://stackoverflow.com/questions/12892701/abort-early-in-a-fold . – Ratan Sebastian Jan 30 '13 at 19:16

3 Answers3

3

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

val b = a.exists(identity)
stew
  • 11,276
  • 36
  • 49
  • I am pretty sure that the code that @Duc posted is only illustrative and that in his real use case he does need to accumulate the values some way. So `exists` would not fit the bill. – Régis Jean-Gilles Jan 30 '13 at 19:17
  • @RégisJean-Gilles What is a way to accumulate Boolean values for which you cannot use exists? – stew Jan 30 '13 at 19:23
  • By real use case, I meant a case where he does not just want to OR a stream a boolean. – Régis Jean-Gilles Jan 30 '13 at 19:29
  • @RégisJean-Gilles what is the real use case then? – stew Jan 30 '13 at 19:30
  • So I change `for (i <- 0 to n-1 if p(i)) return true` to `(for (i <- Stream.range(0, n)) yields p(i)).exists(_ == true)` But it became much slower. What did I do wrong here? – Pinch Jan 30 '13 at 19:42
  • @stew: Maybe am I trying too hard to read between the lines and all he wanted was indeed to OR a stream of boolean, but it just seemed unlikely given that he used a `fold` while there is not much to *accumulate* here. For an example of a more general but similar use case, see my answer. – Régis Jean-Gilles Jan 30 '13 at 19:55
  • @Duc in the first you just test a bunch of values, in the second you create a Stream of values, then search through the stream for the result. Its bound to be faster to not construct the Stream – stew Jan 30 '13 at 19:58
  • @stew: but the stream suppose to be lazy, so the number of times I evaluate p(i) is still the same. Why should it be slower? – Pinch Jan 30 '13 at 20:02
  • @stew: Sorry, it actually does not become slower. Turn off I have another coding bug. Please ignore my above comments! – Pinch Jan 30 '13 at 20:12
3

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.

Régis Jean-Gilles
  • 32,541
  • 5
  • 83
  • 97
  • What you wrote is a `foldRight`, which wouldn't be tail-recursive anyway on Stream. See [this answer](http://stackoverflow.com/a/12893459/53974) for a solution for foldRight, which generalizes the same idea you used, while keeping it parametric on the actual fold function. – Blaisorblade Jan 30 '13 at 20:53
  • Thanks for the link. I won't update the answer again, as I said my answer is already almost off topic toward the end. Using my answer plus the answers you linked to should be more than enough for anyone. Also believe it or not, but the first version of `myReduce` (the one applied on boolean streams) is actually tail recursive (the key difference from the second one being that `||` is a *built-in* short circuit operator)! – Régis Jean-Gilles Jan 30 '13 at 21:26
  • I was basing myself on your comment. But I see your point: `||` has to be compiled, in the end, to the same bytecode as an if to be shortcircuiting (as done by Java), hence it's tail recursive. And Scala correctly implements that, somewhat surprisingly: `import annotation.tailrec; @tailrec def myReduce( s: Stream[Boolean] ): Boolean = s.head || myReduce( s.tail )` – Blaisorblade Jan 30 '13 at 21:45
1

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

Randall Schulz
  • 26,420
  • 4
  • 61
  • 81