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.

Answer 3

forall is definitely the best choice for the specific scenario but for illustration here's good old recursion:

@tailrec def hasEven(xs: List[Int]): Boolean = xs match {
  case head :: tail if head % 2 == 0 => true
  case Nil  => false
  case _ => hasEven(xs.tail)
}

I tend to use recursion a lot for loops w/short circuit use cases that don't involve collections.

Answer 4

UPDATE:

DO NOT USE THE CODE IN MY ANSWER BELOW!

Shortly after I posted the answer below (after misinterpreting the original poster's question), I have discovered a way superior generic answer (to the listing of requirements below) here: https://stackoverflow.com/a/60177908/501113

---

It appears you have several requirements:

1. Iterate through a (possibly large) list of items doing some (possibly expensive) work
2. The work done to an item could return an error
3. At the first item that returns an error, short circuit the iteration, throw away the work already done, and return the item's error

A for comprehension isn't designed for this (as is detailed in the other answers).

And I was unable to find another Scala collections pre-built iterator that provided the requirements above.

While the code below is based on a contrived example (transforming a String of digits into a BigInt), it is the general pattern I prefer to use; i.e. process a collection and transform it into something else.

def getDigits(shouldOnlyBeDigits: String): Either[IllegalArgumentException, BigInt] = {
  @scala.annotation.tailrec
  def recursive(
      charactersRemaining: String = shouldOnlyBeDigits
    , accumulator: List[Int] = Nil
  ): Either[IllegalArgumentException, List[Int]] =
    if (charactersRemaining.isEmpty)
      Right(accumulator) //All work completed without error
    else {
      val item = charactersRemaining.head
      val isSuccess =
        item.isDigit //Work the item
      if (isSuccess)
        //This item's work completed without error, so keep iterating
        recursive(charactersRemaining.tail, (item - 48) :: accumulator)
      else {
        //This item hit an error, so short circuit
        Left(new IllegalArgumentException(s"item [$item] is not a digit"))
      }
    }
  recursive().map(digits => BigInt(digits.reverse.mkString))
}

When it is called as getDigits("1234") in a REPL (or Scala Worksheet), it returns: val res0: Either[IllegalArgumentException,BigInt] = Right(1234)

And when called as getDigits("12A34") in a REPL (or Scala Worksheet), it returns: val res1: Either[IllegalArgumentException,BigInt] = Left(java.lang.IllegalArgumentException: item [A] is not digit)

You can play with this in Scastie here: https://scastie.scala-lang.org/7ddVynRITIOqUflQybfXUA