Foldable

intermediate

The Typeclass Foldable provide us the ability of, given a type Kind<F, A>, aggregates their values A.

Foldable<F> is implemented in terms of two basic methods:

  • fa.foldLeft(init, f) eagerly folds fa from left-to-right.
  • fa.foldRight(init, f) lazily folds fa from right-to-left.

Beyond these it provides many other useful methods related to folding over Kind<F, A> values.

For the following examples we are going to use some common imports

import arrow.Kind
import arrow.core.*
import arrow.data.ListK
import arrow.data.k
import arrow.instances.monoid
import arrow.instances.listk.foldable.foldable
import arrow.instances.option.foldable.foldable
import arrow.typeclasses.Foldable

and the same two variables to see the different behaviors of Foldable:

val maybeStr: Option<String> = Some("abc")
val strList: ListK<String> = listOf("a", "b", "c").k()

FoldLeft

Left associative fold on F using the provided function.

fun <F> concatenateStringFromLeft(strKind: Kind<F, String>, FO: Foldable<F>): String =
  FO.run {
    strKind.foldLeft("str: ") { base: String, value: String -> base + value }
  }
concatenateStringFromLeft(maybeStr, Option.foldable())
// str: abc
concatenateStringFromLeft(None, Option.foldable())
// str: 
concatenateStringFromLeft(strList, ListK.foldable())
// str: abc

FoldRight

Right associative lazy fold on F using the provided function.

This method evaluates lb lazily, and returns a lazy value to support laziness in a stack-safe way avoiding StackOverflows.

For more detailed information about how this method works see the documentation for Eval<A>.

fun <F> concatenateStringFromRight(strKind: Kind<F, String>, FO: Foldable<F>): String =
  FO.run {
    strKind.foldRight(Eval.now("str: ")) { value: String, base: Eval<String> -> base.map { it + value } }
      .value()
  }
concatenateStringFromRight(maybeStr, Option.foldable())
// str: abc
concatenateStringFromRight(None, Option.foldable())
// str: 
concatenateStringFromRight(strList, ListK.foldable())
// str: cba

Fold

Fold implemented using the given Monoid<A> instance.

fun <F> concatenateString(strKind: Kind<F, String>, FO: Foldable<F>): String =
  FO.run {
    "str: " + strKind.fold(String.monoid())
  }
concatenateString(maybeStr, Option.foldable())
// str: abc
concatenateString(None, Option.foldable())
// str: 
concatenateString(strList, ListK.foldable())
// str: abc

Besides we have combineAll which is an alias for fold.

fun <F> combineAllString(strKind: Kind<F, String>, FO: Foldable<F>): String =
  FO.run {
    "str: " + strKind.combineAll(String.monoid())
  }
combineAllString(maybeStr, Option.foldable())
// str: abc
combineAllString(None, Option.foldable())
// str: 
combineAllString(strList, ListK.foldable())
// str: abc

ReduceLeftToOption

fun <F> reduceLeftToOption(strKind: Kind<F, String>, FO: Foldable<F>): Option<Int> =
  FO.run {
    strKind.reduceLeftToOption({ it.length }) { base: Int, value: String -> base + value.length }
  }
reduceLeftToOption(maybeStr, Option.foldable())
// Some(3)
reduceLeftToOption(None, Option.foldable())
// None
reduceLeftToOption(strList, ListK.foldable())
// Some(3)

ReduceRightToOption

fun <F> reduceRightToOption(strKind: Kind<F, String>, FO: Foldable<F>): Option<Int> =
  FO.run {
    strKind.reduceRightToOption({ it.length }) { value: String, base: Eval<Int> -> base.map { it + value.length } }
      .value()
  }
reduceRightToOption(maybeStr, Option.foldable())
// Some(3)
reduceRightToOption(None, Option.foldable())
// None
reduceRightToOption(strList, ListK.foldable())
// Some(3)

ReduceLeftOption

Reduce the elements of this structure down to a single value by applying the provided aggregation function in a left-associative manner.

Return None if the structure is empty, otherwise the result of combining the cumulative left-associative result of the f operation over all of the elements.

fun <F> getLengthFromLeft(strKind: Kind<F, String>, FO: Foldable<F>): Option<String> =
  FO.run {
    strKind.reduceLeftOption { base: String, value: String -> base + value }
  }
getLengthFromLeft(maybeStr, Option.foldable())
// Some(abc)
getLengthFromLeft(None, Option.foldable())
// None
getLengthFromLeft(strList, ListK.foldable())
// Some(abc)

ReduceRightOption

Reduce the elements of this structure down to a single value by applying the provided aggregation function in a right-associative manner.

Return None if the structure is empty, otherwise the result of combining the cumulative right-associative result of the f operation over the A elements.

fun <F> getLengthFromRight(strKind: Kind<F, String>, FO: Foldable<F>): Option<String> =
  FO.run {
    strKind.reduceRightOption { value: String, base: Eval<String> -> base.map { it + value } }
      .value()
  }
getLengthFromRight(maybeStr, Option.foldable())
// Some(abc)
getLengthFromRight(None, Option.foldable())
// None
getLengthFromRight(strList, ListK.foldable())
// Some(cba)

FoldMap

Fold implemented by mapping A values into B and then combining them using the given Monoid<B> instance.

fun <F> getLenght(strKind: Kind<F, String>, FO: Foldable<F>): Int =
  FO.run {
    strKind.foldMap(Int.monoid()) { it.length }
  }
getLenght(maybeStr, Option.foldable())
// 3
getLenght(None, Option.foldable())
// 0
getLenght(strList, ListK.foldable())
// 3

Traverse_

A typed values will be mapped into Kind<G, B> by function f and combined using Applicative#map2.

This method is primarily useful when <_> represents an action or effect, and the specific A aspect of Kind<G, A> is not otherwise needed.

import arrow.instances.either.applicative.applicative

fun <F> traverse(strKind: Kind<F, String>, FO: Foldable<F>): Either<Int,Unit> =
  FO.run {
    strKind.traverse_(Either.applicative<Int>()) { Right(it.length) }
  }.fix()
traverse(maybeStr, Option.foldable())
// Right(b=kotlin.Unit)
traverse(None, Option.foldable())
// Right(b=kotlin.Unit)
traverse(strList, ListK.foldable())
// Right(b=kotlin.Unit)

Sequence_

Similar to traverse_ except it operates on Kind<F, Kind<G, A>> values, so no additional functions are needed.

import arrow.instances.option.applicative.applicative

fun <F> sequence(strKind: Kind<F, Kind<ForOption, String>>, FO: Foldable<F>):Option<Unit> =
  FO.run {
    strKind.sequence_(Option.applicative())
  }.fix()
  
val maybeStrOpt = Some("abc".some())
val strNoneList = listOf("a".some(), None, "c".some()).k()
val strOptList = listOf("a".some(), "b".some(), "c".some()).k()
sequence(maybeStrOpt, Option.foldable())
// Some(kotlin.Unit)
sequence(None, Option.foldable())
// Some(kotlin.Unit)
sequence(strNoneList, ListK.foldable())
// None
sequence(strOptList, ListK.foldable())
// Some(kotlin.Unit)

Find

Find the first element matching the predicate, if one exists.

fun <F> getIfNotBlank(strKind: Kind<F, String>, FO: Foldable<F>): Option<String> =
  FO.run {
    strKind.find { it.isNotBlank() }
  }
getIfNotBlank(maybeStr, Option.foldable())
// Some(abc)
getIfNotBlank(None, Option.foldable())
// None
getIfNotBlank(strList, ListK.foldable())
// Some(a)

Exists

Check whether at least one element satisfies the predicate.

If there are no elements, the result is false.

fun <F> containsNotBlank(strKind: Kind<F, String>, FO: Foldable<F>): Boolean =
  FO.run {
    strKind.exists { it.isNotBlank() }
  }
containsNotBlank(maybeStr, Option.foldable())
// true
containsNotBlank(None, Option.foldable())
// false
containsNotBlank(strList, ListK.foldable())
// true

ForAll

Check whether all elements satisfy the predicate.

If there are no elements, the result is true.

fun <F> isNotBlank(strKind: Kind<F, String>, FO: Foldable<F>): Boolean =
  FO.run {
    strKind.forAll { it.isNotBlank() }
  }
isNotBlank(maybeStr, Option.foldable())
// true
isNotBlank(None, Option.foldable())
// true
isNotBlank(strList, ListK.foldable())
// true

IsEmpty

Returns true if there are no elements. Otherwise false.

fun <F> isFoldableEmpty(strKind: Kind<F, String>, FO: Foldable<F>): Boolean =
  FO.run {
    strKind.isEmpty()
  }
isFoldableEmpty(maybeStr, Option.foldable())
// false
isFoldableEmpty(None, Option.foldable())
// true
isFoldableEmpty(strList, ListK.foldable())
// false

NonEmpty

Returns true if there is at least one element. Otherwise false.

fun <F> foldableNonEmpty(strKind: Kind<F, String>, FO: Foldable<F>): Boolean =
  FO.run {
    strKind.nonEmpty()
  }
foldableNonEmpty(maybeStr, Option.foldable())
// true
foldableNonEmpty(None, Option.foldable())
// false
foldableNonEmpty(strList, ListK.foldable())
// true

Size

The size of this Foldable.

Note: will not terminate for infinite-sized collections.

fun <F> foldableSize(strKind: Kind<F, String>, FO: Foldable<F>): Long =
  FO.run {
    strKind.size(Long.monoid())
  }
foldableSize(maybeStr, Option.foldable())
// 1
foldableSize(None, Option.foldable())
// 0
foldableSize(strList, ListK.foldable())
// 3

FoldMapM

Monadic folding on F by mapping A values to Kind<G, B>, combining the B values using the given Monoid<B> instance.

Similar to foldM, but using a Monoid<B>.

import arrow.instances.option.monad.monad

fun <F> getLengthWithMonoid(strKind: Kind<F, String>, FO: Foldable<F>): Option<Int> =
  FO.run {
       strKind.foldMapM(Option.monad(), Int.monoid()) { Some(it.length) }
  }.fix()
getLengthWithMonoid(maybeStr, Option.foldable())
// Some(3)
getLengthWithMonoid(None, Option.foldable())
// Some(0)
getLengthWithMonoid(strList, ListK.foldable())
// Some(3)

FoldM

Left associative monadic folding on F.

The default implementation of this is based on foldL, and thus will always fold across the entire structure. Certain structures are able to implement this in such a way that folds can be short-circuited (not traverse the entirety of the structure), depending on the G result produced at a given step.

import arrow.instances.either.monad.monad

fun <F> maybeConcatenateString(strKind: Kind<F, String>, FO: Foldable<F>): Either<String,String> =
  FO.run {
    strKind.foldM(
      Either.monad<String>(),
      "str: "
    ) { base: String, value: String -> Right(base + value) }
  }.fix()
maybeConcatenateString(maybeStr, Option.foldable())
// Right(b=str: abc)
maybeConcatenateString(None, Option.foldable())
// Right(b=str: )
maybeConcatenateString(strList, ListK.foldable())
// Right(b=str: abc)

Get

Get the element at the index of the Foldable.

import arrow.instances.either.monad.monad
import arrow.instances.either.foldable.foldable

fun foldableGet(strKind: EitherOf<String, String>): Option<String> =
  with(Either.foldable<String>()) {
    strKind.get(Either.monad(), 0)
  }

val rightStr = Either.right("abc") as Either<String, String>

foldableGet(rightStr)
// Some(abc)

Data types

Module Data types
arrow.core Either, Id, Option, Try, Tuple2
arrow.data Coproduct, EitherT, Ior, ListK, MapK, NonEmptyList, OptionT, SequenceK, SetK, Validated
arrow.effects FlowableK, FluxK, MaybeK, ObservableK
arrow.typeclasses Const

Type Class Hierarchy