Scala - map over sequence, stopping immediately when element cannot be processed

Question

I'd like a function that maps a function f over a sequence xs, and if f(x) (where x is an element of xs) produces a Failure then don't process any further elements of xs but immediately return Failure. If f(x) succeeds for all x then return a Success containing a sequence of the results.

So the type signature might be something like

def traverse[A, B](xs: Seq[A])(f: A => Try[B]): Try[Seq[B]]

And some test cases:

def doWork(i: Int): Try[Int] = {
  i match {
    case 1 => Success(10)
    case 2 => Failure(new IllegalArgumentException("computer says no"))
    case 3 => Success(30)
  }
}

traverse(Seq(1,2,3))(doWork)
res0: scala.util.Try[Seq[Int]] = Failure(java.lang.IllegalArgumentException: computer says no)

traverse(Seq(1,3))(doWork)
scala.util.Try[Seq[Int]] = Success(List(10, 30))

What would be the most elegant way to implement this?

Answer 1

Simple implementation:

def traverse[A, B](xs: Seq[A])(f: A => Try[B]): Try[Seq[B]] =
  xs.foldLeft[Try[Seq[B]]](Success(Vector())) { (attempt, elem) => for {
    seq <- attempt
    next <- f(elem)
  } yield seq :+ next
  }

Trouble here that while function will not evaluate f after the Failure will occur, function will traverse the sequence to the end , which could be undesirable in case of some complex Stream, so we may use some specialized version:

def traverse1[A, B](xs: Seq[A])(f: A => Try[B]): Try[Seq[B]] = {
  val ys = xs map f
  ys find (_.isFailure) match {
    case None => Success(ys map (_.get))
    case Some(Failure(ex)) => Failure(ex)
  }
}

which uses intermediate collection, which leads to unnecessary memory overhead in case of strict collection

or we could reimplement fold from scratch:

def traverse[A, B](xs: Seq[A])(f: A => Try[B]): Try[Seq[B]] = {
  def loop(xs: Seq[A], acc: Seq[B]): Try[Seq[B]] = xs match {
    case Seq() => Success(acc)
    case elem +: tail =>
      f(elem) match {
        case Failure(ex) => Failure(ex)
        case Success(next) => loop(tail, acc :+ next)
      }
  }
  loop(xs, Vector())
}

As we could see inner loop will continue iterations while it deals only with Success