foldRight captures a common pattern in recursive list programs. Summing integers and multiplying doubles differ in three places: the empty-list result, the combining operation, and the element type. Rather than repeat the same traversal, foldRight takes those differences as arguments. It accepts a list of A values, an initial result of B, and a function that combines one A with a B to produce B. The result type need not match the list element type. section 3.3.2
Listing 3.2 Right folds and simple uses
def foldRight[A, B](as: List[A], acc: B, f: (A, B) => B): B =
as match
case Nil => acc
case Cons(x, xs) => f(x, foldRight(xs, acc, f))
def sumViaFoldRight(ns: List[Int]) =
foldRight(ns, 0, (x,y) => x + y)
def productViaFoldRight(ns: List[Double]) =
foldRight(ns, 1.0, _ * _) #1
Its definition has one case for Nil, which returns the accumulator, and one for Cons, which combines the head with the recursively folded tail. sum and product become small applications of the same traversal. section 3.3.2
A useful mental model is constructor replacement: foldRight(as, acc, f) replaces Nil with acc and each Cons with f. For a list shaped like Cons(1, Cons(2, Nil)), folding with f and acc has the shape f(1, f(2, acc)). This explains both why the operation begins collapsing at the rightmost end and why folding with Nil and Cons reconstructs the original list. section 3.3.2 section 3.6
Tracing a right fold
For foldRight(Cons(1, Cons(2, Cons(3, Nil))), 0, (x, y) => x + y), recursion first reaches Nil. The pending calls then collapse as 1 + (2 + (3 + 0)), yielding 6. This operational order matters: strict List foldRight pushes a stack frame for every element before it invokes the combining function, so it traverses the whole list and can overflow the stack on sufficiently large inputs. section 3.3.2 section 3.6
Once the traversal is abstracted, the combining function and accumulator describe many list operations:
- Count elements with 0 and a function that adds one for each element. section 3.6
- Append xs to ys with ys as the accumulator and Cons as the combining function. section 3.6
- Build map and filter results by conditionally consing transformed or retained elements onto an accumulated list. section 3.6
- Flatten mapped lists by appending each produced list to the accumulated remainder. section 3.6
foldRight is not automatically the best choice for every traversal. A strict List version cannot stop early: it reaches the end before the supplied function is called. foldLeft instead carries an updated accumulator through a tail-recursive traversal, and foldRight can be implemented from foldLeft by reversing first. These alternatives make evaluation order and stack use explicit design concerns. section 3.6 section 3.6
def foldRight[B](acc: => B)(f: (A, => B) => B): B = #1
this match
case Cons(h, t) => f(h(), t().foldRight(acc)(f)) #2
case _ => acc
On LazyList, foldRight changes one crucial detail: its accumulator and the second argument of its combining function are nonstrict. A combining function may therefore ignore the unevaluated folded tail. Used with ||, exists stops as soon as a matching element is found, without evaluating the remaining tail; this also makes the fold usable with infinite lazy lists. section 5.3 section 5.6
