How to convert an imperative double for-loop to functional style without return in Scala?

Question

I have the following Scala code, imperative style, and I was wondering if there is an equivalent in functional style avoiding the use of return:

def function(c: Char, vector: Vector[Vector[Char]]): (x:Int , y:Int) = {
  for (x <- vector.indices)
    for (y <- vector(x).indices)
      if (vector(x)(y) == c)
        return (x, y)
  throw new NoSuchElementException
}

I'm wondering if there's an alternative, as efficient as this one, without the use of return.

Answer 1

Let's start with the following naive implementation:

def function(c: Char, levelVector: Vector[Vector[Char]]): Option[(Int, Int)] = (
  for {
    (row, x) <- levelVector.zipWithIndex
    (cell, y) <- row.zipWithIndex
    if cell == c
  } yield (x, y)
).headOption

(Note that I'm returning the value in an Option instead of throwing an exception in the case where there's no match, but you could add .getOrElse(throw new NoSuchElementException) if you wanted the original behavior.)

This implementation is likely to be just fine in many scenarios, but it's kind of wasteful, since it creates a lot of intermediate collections and checks every element even after it finds a match. (It's worth noting that your imperative implementation also creates intermediate collections, but they're only ranges, and it's not nearly as bad as this naive functional implementation.)

The following version is likely to be more efficient, but still avoids return:

def function(c: Char, levelVector: Vector[Vector[Char]]): Option[(Int, Int)] =
  levelVector.view.zipWithIndex.map {
    case (row, x) => (x, row.indexOf(c))
  }.collectFirst {
    case (x, y) if y >= 0 => (x, y)
  }

Here we use view to avoid creating a bunch of intermediate collections, and collectFirst to stop checking after we find a match.

If you know that the performance of this method is really important (it's probably not), you should still avoid return (which involves throwing an exception in Scala's implementation) and instead use var and while. This is a pretty reasonable thing to do for something this simple—just make sure you wrap up all of the mutable state inside the method.

The next step in a more functional direction would be to try to avoid the use of indices altogether—it's very often possible to reframe the problem in such a way that you don't need them, and doing so will often make your program more elegant (if not more performant).