`traverse` handles the recurring case of mapping a collection with a function that may produce an effect, then combining those effects into one result. For a `List`, an Option-producing function has the shape `A => Option[B]`, and traversal produces `Option[List[B]]`: every successful element yields a list, while one `None` makes the whole result `None`. section 4.3.2 section 4.6
Parse a list in one pass
Parsing strings illustrates why `traverse` is preferable to separately mapping and sequencing. Rather than first construct a `List[Option[Int]]` and then combine it, pass the parser directly: `def traverse[A, B](as: List[A])(f: A => Option[B]): Option[List[B]]` A right fold can apply `f` to each element and use `map2` with `::` to assemble the successful values. `sequence` is then just traversal with the identity function, because its input elements are already Options. section 4.3.2 section 4.6
The same shape works beyond failure handling. With `Either`, traversal returns the first encountered error or a list of results. With `State`, it turns each element into a state action and sequences those actions, preserving the collection’s shape while threading state through the traversal. section 4.6 section 6.8
Generalizing from `List` reveals `Traverse[F]`: an abstraction for data structures whose elements can be visited while an `Applicative[G]` combines effects. Its central operations are `traverse`, which transforms `F[A]` with `A => G[B]` into `G[F[B]]`, and `sequence`, which swaps `F[G[A]]` into `G[F[A]]`. section 12.6 section 12.9
A Traverse instance supports several useful interpretations of the same traversal:
- Use `Id` as the effect to recover ordinary `map`; Traverse therefore extends Functor. section 12.7 section 12.9
- Use a constant applicative built from a Monoid to express `foldMap`, connecting Traverse to Foldable. section 12.7.1
- Use `State` to number elements, collect them into a list, or factor the common state-threading pattern as `mapAccum`. section 12.7.2
- Use applicative products to fuse two traversals into one pass, or compose Traverse instances for nested structures. section 12.7.4 section 12.7.5
Listing 12.9 Numbering the elements in a traversable
extension [A](fa: F[A])
def zipWithIndex: F[(A, Int)] =
fa.traverse(a =>
for
i <- State.get[Int]
_ <- State.set(i + 1)
yield (a, i)
).run(0)(0)
A State-based traversal labels each element with its position by reading and incrementing an integer state at every visit. section 12.7.2
Traversal is especially valuable because the data structure and the effect are independent. Instances for `List`, `Option`, `Tree`, and keyed `Map` reuse the same interface; changing the applicative changes what is accumulated or coordinated without rewriting structure-specific effect logic. section 12.6 section 12.8
