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._

Apart from the familiar foldLeft and foldRight, Foldable has a number of other useful functions.

foldLeft

foldLeft is an eager left-associative fold on F using the given function. 

Foldable[List].foldLeft(List(1, 2, 3), 0)(_ + _) should be(res0)
Foldable[List].foldLeft(List("a", "b", "c"), "")(_ + _) should be(res1)

foldRight

foldRight is a lazy right-associative fold on F using the given function. The function has the signature (A, Eval[B]) => Eval[B] to support laziness in a stack-safe way. 

val lazyResult =
  Foldable[List].foldRight(List(1, 2, 3), Now(0))((x, rest) => Later(x + rest.value))
lazyResult.value should be(res0)

fold

fold, also called combineAll, combines every value in the foldable using the given Monoid instance. 

Foldable[List].fold(List("a", "b", "c")) should be(res0)
Foldable[List].fold(List(1, 2, 3)) should be(
  res1)

foldMap

foldMap is similar to fold but maps every A value into B and then combines them using the given Monoid[B] instance. 

Foldable[List].foldMap(List("a", "b", "c"))(_.length) should be(res0)
Foldable[List].foldMap(List(1, 2, 3))(_.toString) should be(res1)

foldK

foldK is similar to fold but combines every value in the foldable using the given MonoidK[G] instance instead of Monoid[G]. 

Foldable[List].foldK(List(List(1, 2), List(3, 4, 5))) should be(res0)
Foldable[List].foldK(List(None, Option("two"), Option("three"))) should be(res1)

find

find searches for the first element matching the predicate, if one exists. 

Foldable[List].find(List(1, 2, 3))(_ > 2) should be(res0)
Foldable[List].find(List(1, 2, 3))(_ > 5) should be(res1)

exists

exists checks whether at least one element satisfies the predicate. 

Foldable[List].exists(List(1, 2, 3))(_ > 2) should be(res0)
Foldable[List].exists(List(1, 2, 3))(_ > 5) should be(res1)

forall

forall checks whether all elements satisfy the predicate. 

Foldable[List].forall(List(1, 2, 3))(_ <= 3) should be(res0)
Foldable[List].forall(List(1, 2, 3))(_ < 3) should be(res1)

toList

Convert F[A] to List[A]. 

Foldable[List].toList(List(1, 2, 3)) should be(res0)
Foldable[Option].toList(Option(42)) should be(res1)
Foldable[Option].toList(None) should be(res2)

filter_

Convert F[A] to List[A] only including the elements that match a predicate. 

Foldable[List].filter_(List(1, 2, 3))(_ < 3) should be(res0)
Foldable[Option].filter_(Option(42))(_ != 42) should be(res1)

traverse_

traverse the foldable mapping A values to G[B], and combining them using Applicative[G] and discarding the results.

This method is primarily useful when G[_] represents an action or effect, and the specific B aspect of G[B] is not otherwise needed. The B will be discarded and Unit returned instead. 

import cats.implicits._

def parseInt(s: String): Option[Int] =
  Either.catchOnly[NumberFormatException](s.toInt).toOption

Foldable[List].traverse_(List("1", "2", "3"))(parseInt) should be(res0)
Foldable[List].traverse_(List("a", "b", "c"))(parseInt) should be(res1)

compose

We can compose Foldable[F[_]] and Foldable[G[_]] instances to obtain Foldable[F[G]]. 

val FoldableListOption = Foldable[List].compose[Option]
FoldableListOption.fold(List(Option(1), Option(2), Option(3), Option(4))) should be(res0)
FoldableListOption.fold(List(Option("1"), Option("2"), None, Option("3"))) should be(res1)

More Foldable methods

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.

There are a few more methods that we haven't talked about but you probably can guess what they do: 

Foldable[List].isEmpty(List(1, 2, 3)) should be(res0)
Foldable[List].dropWhile_(List(1, 2, 3))(_ < 2) should be(res1)
Foldable[List].takeWhile_(List(1, 2, 3))(_ < 2) should be(res2)