Scala Traverse and Sequence, in depth: turning List[F[A]] into F[List[A]], from Option to bounded parallel IO

The shape problem

Suppose loadUser(id: Long): IO[User] fetches one user. With a list of ids, ids.map(loadUser) has type List[IO[User]]: a list of separate programs, none combined, none run. What you want is a single IO[List[User]] that, when run, loads every user and gives you the list, or fails if any load fails.

Two signatures capture this. In Cats they are methods of the Traverse type class, available as syntax on any traversable value:

trait Traverse[F[_]] extends Functor[F] with Foldable[F]:
  def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]
  def sequence[G[_]: Applicative, A](fga: F[G[A]]): G[F[A]] =
    traverse(fga)(identity)

Read the type of traverse carefully: the outer container F (List, Vector, Option, a tree) is the thing being walked; the inner G is the effect, and all traverse needs from G is an Applicative, meaning a way to wrap a pure value and a way to combine two independent effects. It does not need flatMap, which is why traverse also works for types like Validated that have no lawful Monad.

Writing traverse for List by hand

Implementing it once removes the mystery. Walk the list from the right, start from an effect containing the empty list, and at each element combine the element's effect with the accumulated effect using map2:

import cats.Applicative
import cats.syntax.all.*

def traverseList[G[_], A, B](as: List[A])(f: A => G[B])(using G: Applicative[G]): G[List[B]] =
  as.foldRight(G.pure(List.empty[B])) { (a, acc) =>
    G.map2(f(a), acc)(_ :: _)
  }

def sequenceList[G[_]: Applicative, A](gas: List[G[A]]): G[List[A]] =
  traverseList(gas)(identity)

traverseList(List("1", "2", "3"))(_.toIntOption)   // Some(List(1, 2, 3))
traverseList(List("1", "x", "3"))(_.toIntOption)   // None

Everything interesting is inside map2. For Option it returns None if either side is None; for Either it keeps the first Left; for IO it runs the left effect, then the right, then combines. The fold just threads those combinations through the list. The real Cats instance for List is more careful, using a lazy map2Eval so that a short-circuiting G stops evaluating once failure is known and deep lists do not blow the stack, but the meaning is identical.

The effect type decides the behaviour

Because the combining rule comes from G, one line of code expresses very different policies. This is the most important practical idea in the article.

import cats.data.ValidatedNec

def parseE(s: String): Either[String, Int] = s.toIntOption.toRight(s"bad: $s")
def parseV(s: String): ValidatedNec[String, Int] = s.toIntOption.toValidNec(s"bad: $s")

val raw = List("4", "x", "9", "y")
raw.traverse(parseE)   // Left(bad: x)                    -- stopped at the first
raw.traverse(parseV)   // Invalid(Chain(bad: x, bad: y))  -- reported both

List(1, 2).traverse(n => List(n, -n))
// List(List(1, 2), List(1, -2), List(-1, 2), List(-1, -2))

The Either and Validated calls are the same shape, and switching between them changes the error policy without touching the traversal. That is the payoff of building on Applicative rather than writing loops.

The standard library: Future.traverse and Future.sequence

Without Cats, the standard library offers Future.traverse and Future.sequence. They have the right types but a crucial difference in behaviour: a Future starts running the moment it is created. So Future.traverse(ids)(fetch) calls fetch for every id immediately, and all requests are in flight at once, limited only by the ExecutionContext and whatever the downstream system tolerates.

import scala.concurrent.{ExecutionContext, Future}

def fetch(id: Long)(using ExecutionContext): Future[User] = ???

// 50,000 ids -> 50,000 concurrent requests. Rarely what you wanted.
def all(ids: List[Long])(using ExecutionContext): Future[List[User]] =
  Future.traverse(ids)(fetch)

// Crude bound: batches of 100, each batch concurrent, batches sequential.
def bounded(ids: List[Long])(using ExecutionContext): Future[List[User]] =
  ids.grouped(100).foldLeft(Future.successful(List.empty[User])) { (acc, batch) =>
    acc.flatMap(done => Future.traverse(batch)(fetch).map(done ++ _))
  }

Also note that if one Future fails, the combined Future fails, but the others keep running because Futures cannot be cancelled. The deeper semantics of Futures and execution contexts are covered in Futures and ExecutionContext. When you need precise control over concurrency and cancellation, use an effect type such as cats-effect's IO.

IO: sequential, parallel and bounded

With IO nothing runs until the program is executed, so the combinator you choose decides concurrency explicitly:

import cats.effect.{IO, IOApp}
import cats.effect.syntax.all.*      // parTraverseN
import cats.syntax.all.*             // traverse, parTraverse, traverse_

def loadUser(id: Long): IO[User] = ???
val ids: List[Long] = (1L to 5000L).toList

val sequential: IO[List[User]] = ids.traverse(loadUser)        // one at a time
val unbounded:  IO[List[User]] = ids.parTraverse(loadUser)     // all at once
val bounded:    IO[List[User]] = ids.parTraverseN(16)(loadUser) // at most 16 in flight

val audit: IO[Unit] = ids.traverse_(id => IO.println(s"checked $id")) // discard results

parTraverse uses the Parallel instance for IO, which runs each effect on its own fiber; if one fails, the remaining fibers are cancelled and the error is raised. parTraverseN provides the same semantics with a concurrency limit, which is almost always what production code against a database or remote API needs. Results come back in input order in all three cases, regardless of completion order. Use traverse_ when you only want the effects, so you do not build a list you will throw away. How fibers are scheduled is covered in the Cats Effect runtime article.

Useful variants

• flatTraverse: when the function returns G[List[B]] for each element, flatTraverse traverses and flattens, giving G[List[B]] rather than G[List[List[B]]]. Typical use: loading the orders for each of several customers.
• traverseFilter: the function returns G[Option[B]]; Nones are dropped from the result. Typical use: look up each id and skip the ones that do not exist, without treating absence as failure.
• Traversing an Option: maybeId.traverse(loadUser) turns Option[Long] into IO[Option[User]], running the effect only when a value is present. This replaces a surprising amount of match-and-wrap boilerplate.
• sequence on effects you already hold: List[Either[E, A]] to Either[E, List[A]], or Option[IO[A]] to IO[Option[A]].

def ordersOf(c: CustomerId): IO[List[Order]] = ???
def find(id: Long): IO[Option[User]] = ???

customers.flatTraverse(ordersOf)    // IO[List[Order]]
ids.traverseFilter(find)            // IO[List[User]], missing ids skipped

The laws, and why they matter to you

Traverse instances obey laws, and each law is a guarantee you can rely on when refactoring:

• Identity. Traversing with a function that has no effect (the Id applicative) is the same as map. Traverse never adds, drops or reorders elements.
• Composition. Traversing with f and then traversing the result with g equals one traversal with the composed effect. This is what lets you fuse or split traversals safely.
• Naturality. Converting the effect type afterwards (for example Either to Option) gives the same answer as converting inside the traversal.

The practical consequence: the order of results always matches the order of inputs, even under parTraverse. If you find yourself sorting the output of a traversal to restore order, something else is wrong. The laws are tested in Cats with discipline and ScalaCheck, and you should test any instance you write the same way.

Writing a Traverse instance for your own type

Any data structure that can be walked can be traversable. Here is a binary tree; a lawful instance needs traverse, foldLeft and foldRight, and Cats derives map, sequence and dozens of other operations from them:

import cats.{Applicative, Eval, Traverse}

enum Tree[+A]:
  case Leaf
  case Node(left: Tree[A], value: A, right: Tree[A])

given Traverse[Tree] with
  def traverse[G[_], A, B](t: Tree[A])(f: A => G[B])(using G: Applicative[G]): G[Tree[B]] =
    t match
      case Tree.Leaf => G.pure(Tree.Leaf)
      case Tree.Node(l, v, r) =>
        G.map3(traverse(l)(f), f(v), traverse(r)(f))(Tree.Node(_, _, _))

  def foldLeft[A, B](t: Tree[A], b: B)(f: (B, A) => B): B = t match
    case Tree.Leaf => b
    case Tree.Node(l, v, r) => foldLeft(r, f(foldLeft(l, b)(f), v))(f)

  def foldRight[A, B](t: Tree[A], lb: Eval[B])(f: (A, Eval[B]) => Eval[B]): Eval[B] = t match
    case Tree.Leaf => lb
    case Tree.Node(l, v, r) => foldRight(l, Eval.defer(f(v, foldRight(r, lb)(f))))(f)

The in-order traversal (left, value, right) defines the effect order, and must agree with the fold order. This version recurses, which is fine for balanced trees; a deep degenerate tree would need a stack-safe formulation.

Worked example: validate a config, then load prices with a limit

A pricing job reads a list of SKU lines from configuration, must report every malformed line at once, and then fetches prices from an API that allows 20 concurrent requests.

final case class Sku(code: String)

def parseSku(line: String): ValidatedNec[String, Sku] =
  if line.matches("[A-Z]{3}-\\d{4}") then Sku(line).validNec
  else s"malformed SKU: '$line'".invalidNec

def price(s: Sku): IO[BigDecimal] = ???

def run(lines: List[String]): IO[Map[Sku, BigDecimal]] =
  lines.traverse(parseSku).toEither match
    case Left(errs) =>
      IO.raiseError(new IllegalArgumentException(errs.toList.mkString("; ")))
    case Right(skus) =>
      skus.parTraverseN(20)(s => price(s).map(s -> _)).map(_.toMap)

Two traversals, two different applicatives, each chosen for its policy: Validated to accumulate configuration errors, bounded parallel IO to respect the API limit. Adding a retry or timeout is a change to price alone.

Trace the data flow. With lines ABC-0001, abc-2 and XYZ, the first traversal produces Invalid carrying two messages, the job fails before a single HTTP call, and the operator sees both bad lines in one log entry instead of fixing them one deploy at a time. With 400 valid lines, the second traversal keeps exactly 20 requests in flight, starting a new one as each finishes, and yields the pairs in line order before toMap collapses them. If request 137 fails, the in-flight siblings are cancelled and the whole IO fails with that error; wrap price with attempt if you would rather collect per-SKU failures and carry on.

Failure modes

If traverse feels like a more powerful fold, that is because it is one: compare with the plain folds in fold, map and filter, which combine values, where traverse combines effects.

What to do next

1. Search your code for Future.sequence and Future.traverse over unbounded inputs and add a concurrency limit.
2. Replace hand-written loops that accumulate Eithers with traverse, and switch to ValidatedNec wherever users should see every error.
3. Replace pattern matches that wrap optional values in effects with option.traverse.
4. In cats-effect code, choose explicitly between traverse, parTraverse and parTraverseN at every call over a collection, and document the limit.
5. Use traverse_ for effect-only loops and flatTraverse or traverseFilter where you currently flatten or filter afterwards.
6. If you define a container type, give it a Traverse instance and test it with the Cats law checks.