🎓 A1Learner
🔍
0 of 45 lessons completed

Fold Patterns

A fold pattern is a way of using a fold to build one value from a whole list. The starting value and the combining step decide what gets built.

Order changes a subtraction

Subtraction is not symmetric, so the two folds disagree. The left fold gives one answer and the right fold gives another.

@main def main(): Unit =
  println(List(1, 2, 3).foldLeft(0)((acc, x) => acc - x))
  println(List(1, 2, 3).foldRight(0)((x, acc) => x - acc))

A fold builds a reversed list

The fold starts from an empty list and puts each new item at the front. The finished list runs in the opposite order.

@main def main(): Unit =
  println(List(1, 2, 3).foldLeft(List.empty[Int])((acc, x) => x :: acc))

A fold builds word counts

The fold starts from an empty map and raises the count for each word it meets. The program prints a lookup and then the sorted pairs.

@main def main(): Unit =
  val counts = List("a", "b", "a").foldLeft(Map.empty[String, Int])((acc, word) => acc.updated(word, acc.getOrElse(word, 0) + 1))
  println(counts("a"))
  println(counts.toList.sortBy(pair => pair._1))

Example

@main def main(): Unit =
  val numbers = List(5, 2, 8)
  println(numbers.foldLeft(0)((acc, x) => acc + x))
  println(numbers.foldLeft(List.empty[Int])((acc, x) => x :: acc))
  println(numbers.foldRight(List.empty[Int])((x, acc) => x :: acc))

Key points

  • FoldLeft: A foldLeft walks a list from the first item to the last item.
  • FoldRight: A foldRight walks a list from the last item back to the first item.
  • Accumulator: An accumulator is the running result that each step updates and passes on.
  • Order: The walk order matters whenever the combining step is not symmetric.
  • Building: A fold can build a list or a map just as easily as it builds a number.

In this example, the first fold adds the numbers into a total. The second fold builds the reversed list and the third fold rebuilds the original order. Three folds over one list build three different values.

Note

Scala lists offer both folds directly, so no hand-written recursion is needed for these builds.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Scastie

Exercise

Which fold builds a reversed list most directly?