Lazy foldRight early termination confusion

Question

While going though Functional Programming in Scala, I came across the following code snippet:

def foldRight[A](z: => B)(f: (A,=>B) => B):B = uncons match {
  case Some((h,t)) => f(h,t.foldRight(z)(f))
  case None => z 
}

The authors then go ahead and state the following:

This looks very similar to the foldRight we wrote for List, but notice how our combining function, f, is non-strict in its second parameter. If f chooses not to evaluate its second parameter, this terminates the traversal early. We can see this by using foldRight to implement exists, which checks to see if any value in the Stream matches a given predicate.

Then the author states the following:

def exists(p: A => Boolean): Boolean =
  foldRight(false)((a, b) => p(a) || b)

My question is how does the combining function f causes early termination in the exists method? I don't think I was able to understand how that happens from the text.

Answer 1

In f(h,t.foldRight(z)(f)), the first argument provided to f is h, the second argument is t.foldRight(z)(f). The way foldRight is defined is that the second argument of its f argument is a by-name argument which will not be evaluated until needed (and will be evaluated everytime it is needed). So in f: (A, =>B) => B, the first argument of type A is a normal argument, but the second one of type B is a by-name argument.

So pretend you defined f like this:

f(a: A, b: => Boolean): Boolean = predicate(a) || b

If predicate(a) is true then b is never needed and will never be evaluated. That is the way the or operator works.

So say for exists applied to some Stream. For the first element to be uncons-ed that will exist (where p(h) is true) this code:

uncons match {
  case Some((h,t)) => f(h,t.foldRight(z)(f))
  case None => z 
}

Is the same as this code (we assume we have a non-empty stream, so we can remove the second case):

f(h,t.foldRight(z)(f))

Which is then equivalent to (expanding f):

p(h) || t.foldRight(z)(f)

But p(h) is true so:

true || t.foldRight(z)(f)

And that's the same as just true and no need to continue calling foldRight, so early termination happens!