# 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 `B`s 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
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 `Factory`s 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]] =

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.