A Foldable is a typeclass for type constructors whose elements can be reduced to one result. It abstracts over the container: summing integers should not depend on whether they live in a List, Vector-like IndexedSeq, LazyList, tree, or Option. Its core operations are foldRight, foldLeft, and foldMap; combineAll reduces elements directly when their element type has a Monoid. section 10.6 section 10.9
trait Foldable[F[_]]:
extension [A](as: F[A])
def foldRight[B](acc: B)(f: (A, B) => B): B
def foldLeft[B](acc: B)(f: (B, A) => B): B
def foldMap[B](f: A => B)(using m: Monoid[B]): B
def combineAll(using m: Monoid[A]): A =
as.foldLeft(m.empty)(m.combine)
The interface separates a structure F[_] from its element type A. A fold supplies an accumulator or maps each A into a monoidal result, so the same reduction vocabulary works across shapes. section 10.6
The operations can be derived from one another. foldLeft and foldRight can be expressed through foldMap using monoids of endofunctions, while foldMap can be expressed through foldRight and a result Monoid. An implementation must override at least one fundamental operation, however, or mutually derived defaults recurse forever. It may also override derived methods when the underlying structure has a more efficient implementation. section 10.9
Useful instances make the abstraction concrete:
- List and LazyList delegate left and right folds to their underlying operations. section 10.9
- IndexedSeq can override foldMap with divide-and-conquer foldMapV for more efficient evaluation. section 10.9
- Tree folds recursively through branches; Option returns the accumulator or monoid empty value when absent. section 10.9
- toList is derivable with foldRight, though a List instance can return itself directly. section 10.9
Reducing a tree or collecting a bag
A Tree instance combines the folded left and right branches with the target Monoid. The same foldMap pattern can turn an IndexedSeq into a frequency map by mapping every element to a one-entry map and combining those maps. The reduction logic stays independent of the input shape. section 10.9 section 10.9
Foldable only promises that elements can be visited and reduced; it does not promise that the original shape can be rebuilt. Therefore a Foldable need not be a Functor. Traverse is stronger: it extends both Functor and Foldable, and can define foldMap by traversing with a constant applicative built from a Monoid. section 12.7.1 section 12.9
