How do you stop building an Option[Collection] upon reaching the first None?

Question

When building up a collection inside an Option, each attempt to make the next member of the collection might fail, making the collection as a whole a failure, too. Upon the first failure to make a member, I'd like to give up immediately and return None for the whole collection. What is an idiomatic way to do this in Scala?

Here's one approach I've come up with:

def findPartByName(name: String): Option[Part] = . . .

def allParts(names: Seq[String]): Option[Seq[Part]] =
  names.foldLeft(Some(Seq.empty): Option[Seq[Part]]) {
    (result, name) => result match {
      case Some(parts) =>
        findPartByName(name) flatMap { part => Some(parts :+ part) }
      case None => None
    }
  }

In other words, if any call to findPartByName returns None, allParts returns None. Otherwise, allParts returns a Some containing a collection of Parts, all of which are guaranteed to be valid. An empty collection is OK.

The above has the advantage that it stops calling findPartByName after the first failure. But the foldLeft still iterates once for each name, regardless.

Here's a version that bails out as soon as findPartByName returns a None:

def allParts2(names: Seq[String]): Option[Seq[Part]] = Some(
  for (name <- names) yield findPartByName(name) match {
    case Some(part) => part
    case None => return None
  }
)

I currently find the second version more readable, but (a) what seems most readable is likely to change as I get more experience with Scala, (b) I get the impression that early return is frowned upon in Scala, and (c) neither one seems to make what's going on especially obvious to me.

The combination of "all-or-nothing" and "give up on the first failure" seems like such a basic programming concept, I figure there must be a common Scala or functional idiom to express it.

Answer 1

Scala collections have some options to use laziness to achieve that.

You can use view and takeWhile:

def allPartsWithView(names: Seq[String]): Option[Seq[Part]] = {
    val successes = names.view.map(findPartByName)
                              .takeWhile(!_.isEmpty)
                              .map(_.get)
                              .force
    if (!names.isDefinedAt(successes.size)) Some(successes)
    else None
}

Using ifDefinedAt avoids potentially traversing a long input names in the case of an early failure.

You could also use toStream and span to achieve the same thing:

def allPartsWithStream(names: Seq[String]): Option[Seq[Part]] = {
    val (good, bad) = names.toStream.map(findPartByName)
                                    .span(!_.isEmpty)
    if (bad.isEmpty) Some(good.map(_.get).toList)
    else None
}

I've found trying to mix view and span causes findPartByName to be evaluated twice per item in case of success.

The whole idea of returning an error condition if any error occurs does, however, sound more like a job ("the" job?) for throwing and catching exceptions. I suppose it depends on the context in your program.

Answer 2

The return in your code is actually a couple levels deep in anonymous functions. As a result, it must be implemented by throwing an exception which is caught in the outer function. This isn't efficient or pretty, hence the frowning.

It is easiest and most efficient to write this with a while loop and an Iterator.

def allParts3(names: Seq[String]): Option[Seq[Part]] = {
  val iterator = names.iterator
  var accum = List.empty[Part]
  while (iterator.hasNext) {
    findPartByName(iterator.next) match {
      case Some(part) => accum +:= part
      case None => return None
    }
  }
  Some(accum.reverse)
}

Because we don't know what kind of Seq names is, we must create an iterator to loop over it efficiently rather than using tail or indexes. The while loop can be replaced with a tail-recursive inner function, but with the iterator a while loop is clearer.