# Foldable

Foldable type class instances can be defined for data structures that can be folded to a summary value.

In the case of a collection (such as `List` or `Vector`), these methods will fold together (combine) the values contained in the collection to produce a single result. Most collection types have `foldLeft` methods, which will usually be used by the associated `Foldable[_]` instance.

`Foldable[F]` is implemented in terms of two basic methods:

• `foldLeft(fa, b)(f)` eagerly performs a left-associative fold over `fa`.
• `foldRight(fa, b)(f)` lazily performs a right-associative fold over `fa`.

Consider a simple list like `List(1, 2, 3)`. You could sum the numbers of this list using folds where `0` is the starting value (`b`) and integer addition (`+`) is the combination operation (`f`). Since `foldLeft` is left-associative, the execution of this fold would look something like `((0 + 1) + 2) + 3`. The execution of a similar `foldRight`-based solution would look something like `0 + (1 + (2 + 3))`. In this case, since integer addition is associative, both approaches will yield the same result. However, for non-associative operations, the two methods can produce different results.

These form the basis for many other operations, see also: A tutorial on the universality and expressiveness of fold

First some standard imports.

``````import cats._
import cats.implicits._
``````

And examples.

``````Foldable[List].fold(List("a", "b", "c"))
// res0: String = abc

Foldable[List].foldMap(List(1, 2, 4))(_.toString)
// res1: String = 124

Foldable[List].foldK(List(List(1,2,3), List(2,3,4)))
// res2: List[Int] = List(1, 2, 3, 2, 3, 4)

Foldable[List].reduceLeftToOption(List[Int]())(_.toString)((s,i) => s + i)
// res3: Option[String] = None

Foldable[List].reduceLeftToOption(List(1,2,3,4))(_.toString)((s,i) => s + i)
// res4: Option[String] = Some(1234)

Foldable[List].reduceRightToOption(List(1,2,3,4))(_.toString)((i,s) => Later(s.value + i)).value
// res5: Option[String] = Some(4321)

Foldable[List].reduceRightToOption(List[Int]())(_.toString)((i,s) => Later(s.value + i)).value
// res6: Option[String] = None

Foldable[List].find(List(1,2,3))(_ > 2)
// res7: Option[Int] = Some(3)

Foldable[List].exists(List(1,2,3))(_ > 2)
// res8: Boolean = true

Foldable[List].forall(List(1,2,3))(_ > 2)
// res9: Boolean = false

Foldable[List].forall(List(1,2,3))(_ < 4)
// res10: Boolean = true

Foldable[Vector].filter_(Vector(1,2,3))(_ < 3)
// res11: List[Int] = List(1, 2)

Foldable[List].isEmpty(List(1,2))
// res12: Boolean = false

Foldable[Option].isEmpty(None)
// res13: Boolean = true

Foldable[List].nonEmpty(List(1,2))
// res14: Boolean = true

Foldable[Option].toList(Option(1))
// res15: List[Int] = List(1)

Foldable[Option].toList(None)
// res16: List[Nothing] = List()

def parseInt(s: String): Option[Int] = scala.util.Try(Integer.parseInt(s)).toOption
// parseInt: (s: String)Option[Int]

Foldable[List].traverse_(List("1", "2"))(parseInt)
// res17: Option[Unit] = Some(())

Foldable[List].traverse_(List("1", "A"))(parseInt)
// res18: Option[Unit] = None

Foldable[List].sequence_(List(Option(1), Option(2)))
// res19: Option[Unit] = Some(())

Foldable[List].sequence_(List(Option(1), None))
// res20: Option[Unit] = None

Foldable[List].forallM(List(1, 2, 3))(i => if (i < 2) Some(i % 2 == 0) else None)
// res21: Option[Boolean] = Some(false)

Foldable[List].existsM(List(1, 2, 3))(i => if (i < 2) Some(i % 2 == 0) else None)
// res22: Option[Boolean] = None

Foldable[List].existsM(List(1, 2, 3))(i => if (i < 3) Some(i % 2 == 0) else None)
// res23: Option[Boolean] = Some(true)

val prints: Eval[Unit] = List(Eval.always(println(1)), Eval.always(println(2))).sequence_
// prints: cats.Eval[Unit] = cats.Eval\$\$anon\$4@16193405

prints.value
// 1
// 2

Foldable[List].dropWhile_(List[Int](2,4,5,6,7))(_ % 2 == 0)
// res25: List[Int] = List(5, 6, 7)

Foldable[List].dropWhile_(List[Int](1,2,4,5,6,7))(_ % 2 == 0)
// res26: List[Int] = List(1, 2, 4, 5, 6, 7)

import cats.data.Nested
// import cats.data.Nested

val listOption0 = Nested(List(Option(1), Option(2), Option(3)))
// listOption0: cats.data.Nested[List,Option,Int] = Nested(List(Some(1), Some(2), Some(3)))

val listOption1 = Nested(List(Option(1), Option(2), None))
// listOption1: cats.data.Nested[List,Option,Int] = Nested(List(Some(1), Some(2), None))

Foldable[Nested[List, Option, *]].fold(listOption0)
// res27: Int = 6

Foldable[Nested[List, Option, *]].fold(listOption1)
// res28: Int = 3
``````

Hence when defining some new data structure, if we can define a `foldLeft` and `foldRight` we are able to provide many other useful operations, if not always the most efficient implementations, over the structure without further implementation.

Note that, in order to support laziness, the signature of `Foldable`’s `foldRight` is

``````def foldRight[A, B](fa: F[A], lb: Eval[B])(f: (A, Eval[B]) => Eval[B]): Eval[B]
``````

as opposed to

``````def foldRight[A, B](fa: F[A], z: B)(f: (A, B) => B): B
``````

which someone familiar with the `foldRight` from the collections in Scala’s standard library might expect. This will prevent operations which are lazy in their right hand argument to traverse the entire structure unnecessarily. For example, if you have:

``````val allFalse = Stream.continually(false)
// allFalse: scala.collection.immutable.Stream[Boolean] = Stream(false, ?)
``````

which is an infinite stream of `false` values, and if you wanted to reduce this to a single false value using the logical and (`&&`). You intuitively know that the result of this operation should be `false`. It is not necessary to consider the entire stream in order to determine this result, you only need to consider the first value. Using `foldRight` from the standard library will try to consider the entire stream, and thus will eventually cause a stack overflow:

``````try {
allFalse.foldRight(true)(_ && _)
} catch {
case e:StackOverflowError => println(e)
}
// java.lang.StackOverflowError
// res29: AnyVal = ()
``````

With the lazy `foldRight` on `Foldable`, the calculation terminates after looking at only one value:

``````Foldable[Stream].foldRight(allFalse, Eval.True)((a,b) => if (a) b else Eval.now(false)).value
// res30: Boolean = false
``````