Scala fold + map + filter, in depth: pipeline semantics, strict versus lazy evaluation, fusing passes into one fold, and the Map and Set traps

Three operations, three shapes

Think of the three operations by what they do to the shape of a collection; that predicts their cost and their failure modes.

map(f) keeps the shape and changes the elements. A list of 10 orders becomes a list of 10 results. The output collection type follows the input type wherever the result type allows, which is why List maps to List and Vector maps to Vector. A Set or Map keeps its own invariants, so mapping one can make the output smaller, as shown below.

filter(p) keeps the element type and changes the size. Its partner filterNot inverts the predicate, and partition(p) returns both halves in one traversal.

foldLeft(z)(op) collapses the collection into a single value of any type you choose. Every aggregate is a fold underneath, which is why a map-and-filter chain can always be rewritten as a single fold, which is the main technique of this article.

The worked example: revenue per country from paid orders

We will use one dataset throughout. Each order has a country, a status, a list of line items and a currency. The question: for paid orders only, what is the total revenue per country, counting only line items worth at least 10 units each?

final case class Line(sku: String, qty: Int, unitPrice: BigDecimal)
final case class Order(id: Long, country: String, status: String, lines: List[Line])

val orders: List[Order] = List(
  Order(1, "DE", "PAID",     List(Line("a", 2, 15), Line("b", 1, 4))),
  Order(2, "IN", "PAID",     List(Line("c", 1, 120))),
  Order(3, "DE", "REFUNDED", List(Line("a", 5, 15))),
  Order(4, "IN", "PAID",     List(Line("d", 3, 9), Line("e", 1, 30)))
)

Order 1 contributes 30 to DE (the 4-unit line is too small), order 2 contributes 120 to IN, order 3 is excluded because it was refunded, and order 4 contributes 30 to IN (each 9-unit item fails the 10-unit threshold). The right answer is Map("DE" -> 30, "IN" -> 150). Keep that result in mind; every version below must produce it.

Version one: the strict chain

The most readable version is a straightforward chain:

val v1: Map[String, BigDecimal] =
  orders
    .filter(_.status == "PAID")
    .flatMap(o => o.lines.map(l => (o.country, l)))
    .filter { case (_, l) => l.unitPrice >= 10 }
    .map { case (country, l) => (country, l.unitPrice * l.qty) }
    .groupBy(_._1)
    .map { case (country, pairs) => country -> pairs.map(_._2).sum }

This is correct and clear, and for four orders nobody should touch it. Now count what it allocates for a million orders. filter builds a new list of paid orders. flatMap builds a list of tuples, one per line item. The second filter builds another list. map builds another. groupBy builds a Map of lists, and the final map builds one more list per country before summing it. That is five or six full intermediate structures, each one immediately garbage.

Short-lived garbage is cheap on the JVM but not free: it costs memory bandwidth, more young-generation collections and, for large inputs, premature promotion. Scala collections performance covers the allocation and boxing side in more detail.

Version two: views, iterators and withFilter

A view turns the same chain into a lazy description that is evaluated one element at a time when you finally ask for a result. You add .view at the start and force it at the end:

val v2: Map[String, BigDecimal] =
  orders.view
    .filter(_.status == "PAID")
    .flatMap(o => o.lines.view.map(l => (o.country, l)))
    .filter { case (_, l) => l.unitPrice >= 10 }
    .map { case (country, l) => (country, l.unitPrice * l.qty) }
    .groupMapReduce(_._1)(_._2)(_ + _)

Two things changed. First, filter, flatMap and map on a View return another View, so nothing is built until groupMapReduce pulls elements through. Second, groupMapReduce(key)(f)(reduce) (added in 2.13) replaces the groupBy plus map plus sum combination. It keeps one running value per key instead of a list of everything in the group, so it never holds the grouped elements in memory.

iterator gives you a similar one-element-at-a-time evaluation, with one important difference: an Iterator can be traversed only once. A view is a reusable recipe; every time you force it, it re-runs the whole chain from the source.

For-comprehensions use withFilter for guards. withFilter does not build a filtered collection; it returns a wrapper whose map, flatMap and foreach apply the predicate as they go. So for (o <- orders if o.status == "PAID") yield o.id does one strict allocation for the result, not two. Scala 2.12 collection internals differ, so a 2.12 benchmark does not predict 2.13.

Version three: fuse the chain into one foldLeft

A fold can do the work of every stage in one pass. You carry the result-so-far as the accumulator and decide, per element, whether to skip, transform and combine:

val v3: Map[String, BigDecimal] =
  orders.foldLeft(Map.empty[String, BigDecimal]) { (acc, o) =>
    if (o.status != "PAID") acc
    else o.lines.foldLeft(acc) { (acc2, l) =>
      if (l.unitPrice < 10) acc2
      else acc2.updatedWith(o.country) {
        case Some(total) => Some(total + l.unitPrice * l.qty)
        case None        => Some(l.unitPrice * l.qty)
      }
    }
  }

This does one traversal of the orders and one of each order's lines, allocates only the updated map entries, and does not need any tuples. It is also clearly harder to read: the filter conditions are now if branches, the projection is buried inside updatedWith,.

The general recipe for fusing works for any chain. A filter(p) becomes if (!p(x)) acc else .... A map(f) becomes val y = f(x) before combining. A flatMap(g) becomes an inner fold over g(x). The terminal aggregate becomes the combine step. For several aggregates at once, use a small case class as the accumulator instead of a tuple, so readers never decode acc._2._1.

fold, foldLeft, foldRight and reduce in a pipeline

foldLeft processes elements from first to last and lets the accumulator have a different type from the elements.

fold(z)(op) requires the accumulator and the elements to share a type (strictly, a supertype of the element type), and its documentation says the operation must be associative and z must be a neutral element. The contract permits any grouping, which is what let the old parallel collections split work, so xs.fold(0)(_ - _) is only right by accident. Use fold only for genuinely associative operations with a true identity, such as + with zero or set union with the empty set.

foldRight processes from last to first. In the 2.13 library the default implementation reverses the collection and folds left, so on a List it is stack-safe but allocates a reversed copy. It is not lazy: on an infinite LazyList it never returns.

reduce, reduceLeft and max use the first element as the starting value, so they throw UnsupportedOperationException on an empty collection. In a pipeline, emptiness is often caused by an upstream filter that removed everything. Use reduceOption, maxOption or a fold with an explicit zero whenever the input can be empty.

Picking the right combinator instead of a chain

Many chains are really one standard combinator in disguise. Using the specific combinator is usually both shorter and cheaper.

collect deserves special mention. It takes a PartialFunction and keeps only the elements for which it is defined, transforming them at the same time. For example: orders.collect { case Order(id, _, "PAID", _) => id }.

The shape traps: Map, Set and String

Because map tries to return the same kind of collection it was called on, the output inherits the invariants of that collection. That produces silent, data-losing bugs.

val stock = Map("apple" -> 3, "pear" -> 3, "fig" -> 7)

// Intended: invert to count -> name. Actually: keys collide, entries are lost.
val byCount = stock.map { case (name, n) => n -> name }
// Map(3 -> "pear", 7 -> "fig")   -- "apple" is gone

val parities = Set(1, 2, 3, 4).map(_ % 2)
// Set(1, 0)  -- four inputs, two outputs

The fix is to decide whether you want the collection semantics. If duplicates matter, convert first with .toList or .toSeq, or go through .view. If you really want an inverted map, decide what to do on collisions explicitly, for example with groupMap(_._2)(_._1), which keeps every name per count.

Strings behave the same way: "abc".map(_.toUpper) returns a String, but "abc".map(_.toInt) returns an IndexedSeq[Int], because an Int cannot be a character of a string. And in 2.13, Map.mapValues is deprecated because it used to return a lazy view that recomputed the function on every access. Use map.view.mapValues(f).toMap when you want a strict result, or the newer transform when the function needs the key too.

Failure modes in production

Trade-offs and a decision rule

The three styles are not ranked; they suit different situations.

• Strict chain: best default for small and medium collections, such as request handling, configuration or test fixtures. Easiest to read and debug.
• View or iterator chain: same readability, single pass, much less allocation. Use it when the input is large or when you only need part of the result, such as a find or take(10). Remember that iterators are single-use and views re-run every time they are forced.
• Fused fold: best when you need several aggregates in one pass, when the accumulator is a non-trivial state machine, or when profiling shows the pipeline is hot. Name the accumulator type and keep the per-element logic in a small, separately tested function.

A practical rule: write the strict chain first, check that it produces the right answer on a hand-computed example like the one above, and only then change the evaluation strategy if measurements say it matters. For timing, use JMH (through the sbt-jmh plugin) rather than a hand-written loop with System.nanoTime, which mostly measures JIT warm-up. For the wider choice of which collection to use in the first place, see Scala collections, and for the difference between methods and function values that you pass into these combinators, see methods versus functions.

What to do next

1. Copy the order example into a Scala 2.13 or Scala 3 worksheet and check that all three versions return Map("DE" -> 30, "IN" -> 150).
2. Search your codebase for .map { on values typed as Set or Map and check that collapsing duplicates is intended.
3. Replace every reduce, max or min that can see an empty input with the Option variant or a fold with an explicit zero.
4. Find groupBy(...).map(... .sum) patterns and rewrite them with groupMapReduce.
5. Pick one hot pipeline, benchmark the strict, view and fused versions with JMH, and keep the most readable one that meets your latency budget.
6. Audit every fold call and confirm the operation is associative and the zero is a true identity.