Sequence to Eithers

 Hello,

I often use Either[E, T] where E is my custom error type and T is some useful value.

Given a Seq[A] and a function A => Either[E, B], I would like to get a Either[E, Seq[B]], where the function is applied in order to elements of Seq[A] until it either returns Left[E], in which case it is no further applied and Left[E] is the end result, or until it has returned Right[B] for every element, in which case all the Bs constitute new seq: Seq[B]] and the end result is Right(seq)

Thanks!

 Best, Oliver

That is called traverse and it is provided by cats. And, just for List you can write your own tail-recursive function.

1 Like

It’s really easy to roll your own, especially if you don’t care about the collection type being preserved.

def traverse[A, E, B](as: Seq[A])(f: A => Either[E, B]): Either[E, Seq[B]] = Right( as.map(a => f(a) match {
  case Right(b) => b
  case Left(e) => return Left(e) 
}))

If you do care about preserving the collection type, you can use either the 2.12 or 2.13 strategy (depending on which you use) to generalize over collections, but the logic is the same.

Rust actually has this built in to the language with the postfix ? operator (early return of error value), and I add it as a macro, so when I’m doing something like this it’s just

  Right(as.map(a => f(a).?))

which is almost unbelievably easy, and so I use it ubiquitously (not just for this task).

Note that if the error case comes up very often, this isn’t the best-performing because it requires throwing and catching a stackless exception. If errors are common, you probably want to use a builder and iterator instead (so you can do the early return from a while loop, so it’s a local return without needing exceptions rather than a nonlocal return).

1 Like

Hello and welcome to the very interesting subject of sequence and traverse!





1 Like

Thanks for all the feedback! I was hoping the standard lib would have something. I might check out cats in the future. For now, I rolled my own.


def traverse[A, B](aSeq: Seq[A])(fun: A => Either[Snag, B]): Either[Snag, Seq[B]] = {
    var snagOpt: Option[Snag] = None
    var bSeq: Seq[B] = Seq.empty
    val aIter = aSeq.iterator
    while(snagOpt.isEmpty && aIter.hasNext) {
      fun(aIter.next()) match {
        case Left(snag) => snagOpt = Some(snag)
        case Right(b) => bSeq :+= b
      }
    }
    snagOpt match {
      case Some(snag) => Left(snag)
      case None => Right(bSeq)
    }
  }

That may have terrible performance depending on what Seq is.

Just stick with List or some other concrete collection.

def traverse[A, B, E](list: List[A])(f: A => Either[E, B]): Either[E, List[B]] = {
  @annotation.tailrec
  def loop(remaining: List[A], acc: List[B]): Either[E, List[B]] =
    remaining match {
      case a :: tail =>
        f(a) match {
          case Right(b) =>
            loop(
              remaining = tail,
              b :: acc
            )
          
          case Left(e) =>
            Left(e)
        }
    
      case Nil =>
        Right(acc.reverse)
    }
  
  loop(remaining = list, acc = List.empty)
}

Or, if you want something more generic, consider this (only works on 2.13, but you can adapt it to 2.12):

import scala.collection.Factory
import scala.collection.mutable.Builder

def traverseAs[A, B, C[_], E](data: C[A])
                             (f: A => Either[E, B])
                             (implicit ev: C[A] <:< IterableOnce[A], factory: Factory[B, C[B]]): Either[E, C[B]] = {
  val iter = data.iterator                       

  @annotation.tailrec
  def loop(acc: Builder[B, C[B]]): Either[E, C[B]] =
    iter.nextOption() match {
      case Some(a) => f(a) match {
        case Right(b) => loop(acc += b)
        case Left(e)  => Left(e)
      }
    
      case None => Right(acc.result())
    }

  loop(acc = factory.newBuilder)
}

This all seems unnecessarily complicated if it’s okay if it’s not super fast, and unnecessarily slow if you want it fast.

In 2.12, the following is all you need to preserve collection types and be full speed:

import collection.generic.CanBuildFrom

def traverse[A, CC[A] <: collection.Iterable[A], E, B](xs: CC[A])(f: A => Either[E, B])(implicit cbf: CanBuildFrom[Nothing, B, CC[B]]): Either[E, CC[B]] = {
  val builder = cbf()
  val i = xs.iterator
  while (i.hasNext) f(i.next) match {
    case Right(b) => builder += b
    case Left(e) => return Left(e)
  }
  Right(builder.result)
}

The types setting stuff up are complicated because of the CanBuildFrom stuff, but the inside is a simple loop.

Thanks for the code! How about 2.13?

Almost identical:

import scala.collection.Factory

def traverse[A, CC[A] <: collection.Iterable[A], E, B](xs: CC[A])(f: A => Either[E, B])(implicit cbf: Factory[B, CC[B]]): Either[E, CC[B]] = {
  val builder = cbf.newBuilder
  val i = xs.iterator
  while (i.hasNext) f(i.next) match {
    case Right(b) => builder += b
    case Left(e) => return Left(e)
  }
  Right(builder.result)
}

Thank you, but where is the Factory coming from?

scala.collection provides implicit Factorys for all of the collection types.

The most relevant piece of documentation for understanding Martijn’s code is https://docs.scala-lang.org/overviews/core/custom-collection-operations.html , which assumes some background acquaintance with https://docs.scala-lang.org/overviews/core/architecture-of-scala-213-collections.html .

1 Like

purely for fun (https://scastie.scala-lang.org/WAJiDyxPRSesWTk8VfzqlA)

def parseInt(s: String): Either[Throwable,Int] = 
  scala.util.Try(s.toInt).toEither

// https://pursuit.purescript.org/packages/purescript-birds/1.0.0/docs/Aviary.Birds#v:cardinal
def cardinal[A,B,C](f: (A, B) => C)(b: B, a: A): C = 
  f(a,b) 

def map2[A,B,C,E](ea: Either[E,A], eb: Either[E,B])(f: (A, B) => C): Either[E,C] =
  for {
    a <- ea
    b <- eb
  } yield f(a, b)

def applyAndCons[E,A,B](f: A => Either[E,B])(head:A,tail:Either[E,Seq[B]]): Either[E,Seq[B]] = 
  map2(f(head),tail)(_ +: _)

def traverse[A,B,E](as: Seq[A])(f: A => Either[E,B]): Either[E,Seq[B]] =
  as.foldRight[Either[E,Seq[B]]](Right(Nil))(applyAndCons(f))

// produces the reverse of traverse
def treverse[A,B,E](as: Seq[A])(f: A => Either[E,B]): Either[E,Seq[B]] =
  as.foldLeft[Either[E,Seq[B]]](Right(Nil))(cardinal(applyAndCons(f)))

assert( traverse(List("1","2","3","4","5"))(parseInt) == Right(List(1,2,3,4,5)) )
assert( treverse(List("1","2","3","4","5"))(parseInt) == Right(List(5,4,3,2,1)) )

def traverse2[A,B,E](as: Seq[A])(f: A => Either[E,B]): Either[E,Seq[B]] =
  treverse(as)(f).map(_.reverse)

assert( traverse2(List("1","2","3","4","5"))(parseInt) 
        ==
        traverse(List("1","2","3","4","5"))(parseInt) )

nice! - I had a go at using fold

  def parseInt(s: String): Either[Throwable,Int] = 
    scala.util.Try(s.toInt).toEither

  def traverse[A, E, B](as: Seq[A])(f: A => Either[E, B]): Either[E, Seq[B]] =
    Right(
      as.map(a =>
        f(a).fold(e => return Left(e), 
                  b => b)
      )
    )

  assert( traverse(List("1","2","3","4","5"))(parseInt)
          == Right(List(1,2,3,4,5)) )

  assert( traverse(List("1","2","x","4","5"))(parseInt).toString
           == "Left(java.lang.NumberFormatException: For input string: \"x\")" )

@philipschwarz - Yeah, the fold version is a little shorter, but I find the pattern match clearer when I come back to read the code, so I approximately always use the pattern match. (Also, the match tends to be lower overhead, though I haven’t tested with the latest inliner etc. to see if it can simplify the fold to not need closures etc. and just do a match.)

The foldRight versions are very compact but unless you’re using a memoized list (e.g. LazyList in 2.13, Stream in 2.12), as you say, it’s better for fun than for serious use. (They are fun, though!)

1 Like

“clearer when I come back to read the code” - yes

“unless you’re using a memoized list” - right

just wondering: given that IterableOnce.foreach is defined as follows

  def foreach[U](f: A => U): Unit = {
    val it = iterator
    while(it.hasNext) f(it.next())
  }

maybe this would also be acceptable?

  def traverse[A, CC[A] <: collection.Iterable[A], E, B](xs: CC[A])(f: A => Either[E, B])
                                                        (implicit cbf: Factory[B, CC[B]]): Either[E, CC[B]] = {
    val builder = cbf.newBuilder
    xs.iterator.foreach (a =>
      f(a) fold(
        e => return Left(e),
        b => builder += b
      )
    )
    Right(builder.result)
  }

  assert( traverse(List("1","2","3","4","5"))(parseInt)
    == Right(List(1,2,3,4,5)) )

  assert( traverse(List("1","2","x","4","5"))(parseInt).toString
    == "Left(java.lang.NumberFormatException: For input string: \"x\")" )

In general you can’t count on extensive inlining by the Scala compiler, and the JVM also generally is imperfect, so this is probably not equivalent. You have to throw a stackless exception, create a closure, etc., which you don’t have to in the version where you manually run the iterator.

1 Like

Thanks all for your input - I think Builders should be more prominently featured in the documentation so that people know they are the way to go to build collections element by element.