Ending a for-comprehension loop when a check on one of the items returns false

Question

I am a bit new to Scala, so apologies if this is something a bit trivial.

I have a list of items which I want to iterate through. I to execute a check on each of the items and if just one of them fails I want the whole function to return false. So you can see this as an AND condition. I want it to be evaluated lazily, i.e. the moment I encounter the first false return false.

I am used to the for - yield syntax which filters items generated through some generator (list of items, sequence etc.). In my case however I just want to break out and return false without executing the rest of the loop. In normal Java one would just do a return false; within the loop.

In an inefficient way (i.e. not stopping when I encounter the first false item), I could do it:

   (for {
          item <- items
          if !satisfiesCondition(item)
        } yield item).isEmpty

Which is essentially saying that if no items make it through the filter all of them satisfy the condition. But this seems a bit convoluted and inefficient (consider you have 1 million items and the first one already did not satisfy the condition).

What is the best and most elegant way to do this in Scala?

Answer 1

Stopping early at the first false for a condition is done using forall in Scala. (A related question)

Your solution rewritten:

items.forall(satisfiesCondition)

To demonstrate short-circuiting:

List(1,2,3,4,5,6).forall { x => println(x); x < 3 }
1
2
3
res1: Boolean = false

The opposite of forall is exists which stops as soon as a condition is met:

List(1,2,3,4,5,6).exists{ x => println(x); x > 3 }
1
2
3
4
res2: Boolean = true

Answer 2

Scala's for comprehensions are not general iterations. That means they cannot produce every possible result that one can produce out of an iteration, as, for example, the very thing you want to do.

There are three things that a Scala for comprehension can do, when you are returning a value (that is, using yield). In the most basic case, it can do this:

• Given an object of type M[A], and a function A => B (that is, which returns an object of type B when given an object of type A), return an object of type M[B];

For example, given a sequence of characters, Seq[Char], get UTF-16 integer for that character:

val codes = for (char <- "A String") yield char.toInt

The expression char.toInt converts a Char into an Int, so the String -- which is implicitly converted into a Seq[Char] in Scala --, becomes a Seq[Int] (actually, an IndexedSeq[Int], through some Scala collection magic).

The second thing it can do is this:

• Given objects of type M[A], M[B], M[C], etc, and a function of A, B, C, etc into D, return an object of type M[D];

You can think of this as a generalization of the previous transformation, though not everything that could support the previous transformation can necessarily support this transformation. For example, we could produce coordinates for all coordinates of a battleship game like this:

val coords = for {
  column <- 'A' to 'L'
  row    <- 1 to 10
} yield s"$column$row"

In this case, we have objects of the types Seq[Char] and Seq[Int], and a function (Char, Int) => String, so we get back a Seq[String].

The third, and final, thing a for comprehension can do is this:

• Given an object of type M[A], such that the type M[T] has a zero value for any type T, a function A => B, and a condition A => Boolean, return either the zero or an object of type M[B], depending on the condition;

This one is harder to understand, though it may look simple at first. Let's look at something that looks simple first, say, finding all vowels in a sequence of characters:

def vowels(s: String) = for {
  letter <- s
  if Set('a', 'e', 'i', 'o', 'u') contains letter.toLower
} yield letter.toLower

val aStringVowels = vowels("A String")

It looks simple: we have a condition, we have a function Char => Char, and we get a result, and there doesn't seem to be any need for a "zero" of any kind. In this case, the zero would be the empty sequence, but it hardly seems worth mentioning it.

To explain it better, I'll switch from Seq to Option. An Option[A] has two sub-types: Some[A] and None. The zero, evidently, is the None. It is used when you need to represent the possible absence of a value, or the value itself.

Now, let's say we have a web server where users who are logged in and are administrators get extra javascript on their web pages for administration tasks (like wordpress does). First, we need to get the user, if there's a user logged in, let's say this is done by this method:

def getUser(req: HttpRequest): Option[User]

If the user is not logged in, we get None, otherwise we get Some(user), where user is the data structure with information about the user that made the request. We can then model that operation like this:

def adminJs(req; HttpRequest): Option[String] = for {
  user <- getUser(req)
  if user.isAdmin
} yield adminScriptForUser(user)

Here it is easier to see the point of the zero. When the condition is false, adminScriptForUser(user) cannot be executed, so the for comprehension needs something to return instead, and that something is the "zero": None.

In technical terms, Scala's for comprehensions provides syntactic sugars for operations on monads, with an extra operation for monads with zero (see list comprehensions in the same article).

What you actually want to accomplish is called a catamorphism, usually represented as a fold method, which can be thought of as a function of M[A] => B. You can write it with fold, foldLeft or foldRight in a sequence, but none of them would actually short-circuit the iteration.

Short-circuiting arises naturally out of non-strict evaluation, which is the default in Haskell, in which most of these papers are written. Scala, as most other languages, is by default strict.

There are three solutions to your problem:

1. Use the special methods forall or exists, which target your precise use case, though they don't solve the generic problem;
2. Use a non-strict collection; there's Scala's Stream, but it has problems that prevents its effective use. The Scalaz library can help you there;
3. Use an early return, which is how Scala library solves this problem in the general case (in specific cases, it uses better optimizations).

As an example of the third option, you could write this:

def hasEven(xs: List[Int]): Boolean = {
  for (x <- xs) if (x % 2 == 0) return true
  false
}

Note as well that this is called a "for loop", not a "for comprehension", because it doesn't return a value (well, it returns Unit), since it doesn't have the yield keyword.

You can read more about real generic iteration in the article The Essence of The Iterator Pattern, which is a Scala experiment with the concepts described in the paper by the same name.