`sequence` turns a list of effectful values inside out. For `List[Option[A]]`, it produces `Option[List[A]]`: all `Some` values become one `Some` list, while any `None` makes the whole result `None`. This lets a collection retain the failure behavior of each element rather than extracting values unsafely. section 4.3.2
A common need is parsing many strings with a function that may fail. Mapping `toIntOption` first yields `List[Option[Int]]`; sequencing that list yields either every parsed integer or failure. Doing map followed by sequence traverses the list twice, motivating `traverse`, which combines mapping and sequencing in one pass. section 4.3.2
def sequence[A](as: List[Option[A]]): Option[List[A]] = as.foldRight[Option[List[A]]](Some(Nil))((a, acc) => map2(a, acc)(_ :: _))
The implementation folds from the right, beginning with a successful empty list. Each option is combined with the accumulated option-list through `map2` and list cons, so failure propagates automatically. section 4.6
The same assembly pattern reappears wherever a list contains computations rather than plain values:
- For random-number actions, sequence threads the RNG through each action and collects the generated values. section 6.8
- For state actions, sequence runs each transition in order and returns the collected results with the final state. section 6.8
- For `Either`, sequence returns the first encountered error instead of a list of successful values. section 4.4
From sequence to traverse
Once `traverse(as)(f)` is available, `sequence` needs no separate traversal logic: each list element is already an `Option`, so traverse receives the identity function. This exposes sequence as the special case of traversing with no additional transformation. section 4.6
