foldLeft reduces a list by carrying an accumulator from the first element toward the last. It starts with an initial value, then combines that value with each element in turn. Its polymorphic signature separates the list element type A from the accumulated result type B: `foldLeft[A, B](as: List[A], acc: B, f: (B, A) => B): B`. section 3.3.2 section 3.6
The important detail is the argument order of `f`: the current accumulator comes first and the current list element second. On `Cons(hd, tl)`, compute `f(acc, hd)` and recur on `tl` with that new accumulator. On `Nil`, return the accumulator unchanged. section 3.6
@annotation.tailrec
def foldLeft[A, B](as: List[A], acc: B, f: (B, A) => B): B =
as match
case Nil => acc
case Cons(hd, tl) => foldLeft(tl, f(acc, hd), f)
The recursive call is the final action in the `Cons` case. Since no work remains after it returns, the function is tail recursive; the annotation asks the Scala compiler to check that property. section 3.6
Accumulating a sum
For a list of integers, begin at `0` and add each element: `foldLeft(ints, 0, _ + _)`. The same pattern computes a product with `1.0` and multiplication, or a length by adding `1` while ignoring each element. The accumulator determines both the result type and the meaning of the traversal. section 3.6
Reversing while traversing left to right
A left fold can reverse a list by starting with `Nil` and placing each encountered element at the front of the accumulator: `foldLeft(as, Nil: List[A], (acc, a) => Cons(a, acc))`. Because each new element is prepended, the result is built in the opposite order. section 3.6
foldLeft is especially useful when ordinary structural recursion or foldRight would leave pending work on the call stack. A foldRight can be implemented through `reverse` followed by foldLeft, producing a stack-safe version that makes two passes through the list. More generally, folds expose repeated list-recursion structure so operations can be expressed by choosing an initial accumulator and combining function. section 3.3.2 section 3.6
Useful implementation challenges follow naturally:
- Define `sum`, `product`, and `length` with different initial accumulators and combining functions. section 3.3.2
- Implement `reverse` with a list accumulator, then use it to express a stack-safe `foldRight`. section 3.3.2 section 3.6
- Replace direct structural recursion in `append` with an appropriate fold. section 3.3.2
