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 Set), 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 folds fa from left-to-right.
• foldRight(fa, b)(f) lazily folds fa from right-to-left.

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[Set].find(Set(1,2,3))(_ > 2)
// res7: Option[Int] = Some(3)

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

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

Foldable[Set].forall(Set(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

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

prints.value
// 1
// 2

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

Foldable[List].dropWhile_(List[Int](1,2,4,5,6,7))(_ % 2 == 0)
// res23: 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)
// res24: Int = 6

Foldable[Nested[List, Option, ?]].fold(listOption1)
// res25: 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
// res26: 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
// res27: Boolean = false