Kotlin: Functional Domain Modeling #4
In this blog we introduce the foldable pattern. Foldable structures are collections of elements that can be folded to a summary value.
Collections
An invariant is a condition that stays true no matter what else happens. For example, we have said that the last name of an author must be fully capitalized. Consider now a class representing a library book. We expect the book to have an ISBN, a title, a publisher, and at least one author. This last condition is an example of an invariant that can be captured directly in the type system. To ensure that we have one or more book authors, we use the NonEmptyList class. The definition of this class requires that there must always be at least one element, and never empty. With this change, the constraint that there is always at least one author is now enforced automatically. The code is self-documenting and there is no need to write unit tests for this requirement.
This is how our Book class appears:
data class Book(
val title: String,
val publisher: String,
val isbn: ISBN,
val authors: NonEmptyList<Author>
)
Using the smart constructor idiom we have (for the Book class):
fun create(title: String, publisher: String, isbn: String, vararg authors: Author): ValidationNel<String, Book>
Note the authors parameter to function create. It is marked as a vararg so we can pass a variable number of actual parameters of type Author at the call site, including none.
Here is the complete class declaration:
data class Book(
val title: String,
val publisher: String,
val isbn: ISBN,
val authors: NonEmptyList<Author>
) {
companion object {
fun create(title: String, publisher: String, isbn: String, vararg authors: Author): ValidationNel<String, Book> {
val vISBN: ValidationNel<String, ISBN> = ISBN.create(isbn)
return if (authors.isEmpty())
failureNel("Book: at least one author required")
else {
val list: List<Author> = ListF.from(*authors)
vISBN.fmap{isbn: ISBN ->
Book(title, publisher, isbn, NonEmptyListF.from(list))
}
}
} // create
}
} // Book
The class ISBN is formulated as per the classes LastName, FirstName, etc. Within the body of the create function of class Book the vararg parameter authors is considered an Array<Author> and is transformed into a List<Author> from the Dogs library.
The following assert shows successfully creating a Book with two authors:
assertEquals(
successNel(
Book(
"Kotlin in Action", "Manning", ISBN("9781617293290"),
NonEmptyListF.of(
Author(Name(LastName("JEMEROV"), FirstName("Dmitry"), none()), 1992),
Author(Name(LastName("ISAKOVA"), FirstName("Svetlana"), none()), 1995)
)
)
),
Book.create("Kotlin in Action", "Manning", "9781617293290",
Author(Name(LastName("JEMEROV"), FirstName("Dmitry"), none()), 1992),
Author(Name(LastName("ISAKOVA"), FirstName("Svetlana"), none()), 1995)
)
)
The Foldable
Given the authors for an individual book we might wish to implement the following behaviors: (a) compute the sum of each author's age; (b) identify the oldest age among the authors. Although the details of the two behaviors we desire, some similarity exists. For example, in both we will have to process each individual author in the collection of authors.
The foldable type represents structures that can be folded to a summary value. In the case of a collection (such as List or Vector from Dogs) the functions will fold together (combine) the values contained in the collection to produce a single result. The foldable abstracts this capability and is implemented with two basic functions:
fun <A, B> F<A>.foldLeft(e: B, f: (B) -> (A) -> B): B
fun <A, B> F<A>.foldRight(e: B, f: (A) -> (B) -> B): B
Both functions are overloaded with variants that accept the function parameter in its uncurried form. Consider the simple list [1, 2, 3]. You sum the numbers of this list with 0 as the initial value (e) and the integer addition operation for f. Since foldLeft is left-associative, the execution of this fold would be ((0 + 1) + 2) + 3. Using a foldRight would evaluate as 0 + (1 + (2 + 3)). Since integer addition is associative, both yield the same result. For non-associative operations, the functions can produce differing results. Here are two simple examples:
assertEquals(25, ListF.of(5, 4, 8, 6, 2).foldLeft(0){ sum, elem -> sum + elem})
assertEquals(105, ListF.of(1, 3, 5, 7).foldRight(1){elem, prod -> prod * elem})
The use-cases for our book example might be implemented as:
object Analytics {
fun totalAges(authors: NonEmptyList<Author>): Int {
fun age(author: Author): Int = LocalDate.now().year - author.yearOfBirth
return authors.foldLeft(0){ages: Int, author: Author -> ages + age(author)}
} // totalAges
fun oldest(authors: NonEmptyList<Author>): Int {
fun age(author: Author): Int = LocalDate.now().year - author.yearOfBirth
return if (authors.size() == 1)
age(authors.head())
else
authors.foldLeft(age(authors.head())){old: Int, author: Author -> if (age(author) > old) age(author) else old }
} // oldest
} // Analytics
with the NonEmptyList a foldable. Two tests are:
val vBook: ValidationNel<String, Book> =
Book.create("Kotlin in Action", "Manning", "9781617293290",
Author(Name(LastName("JEMEROV"), FirstName("Dmitry"), none()), 1992),
Author(Name(LastName("ISAKOVA"), FirstName("Svetlana"), none()), 1995)
)
assertEquals(57, vBook.fold({0}, {book -> Analytics.totalAges(book.authors)})) // in 2022
assertEquals(30, vBook.fold({0}, {book -> Analytics.oldest(book.authors)})) // in 2022
The implementations for totalAges and oldest have similarities that we can refactor into more generic patterns. For example: (a) both implement a fold over the collection; (b) both take an Int zero as the seed of the fold and and perform a binary operation on two Ints on each iteration. We can unify these seemingly different functions using a monoid.
The Monoid
Let us consider a simple algebraic structure, the monoid, which is defined only by its algebra. Other than satisfying the same laws, instances of the monoid may have little or nothing to do with one another. Nonetheless, we’ll see how this algebraic structure is often all we need to write useful, polymorphic functions.
Monoids are simple, ubiquitous, and useful. Monoids come up all the time in everyday programming, whether we’re aware of them or not. Working with lists, concatenating strings, or accumulating the results of a loop can often be phrased in terms of monoids. We’ll see how monoids are useful to assemble complex calculations from simpler pieces.
Consider the algebra of string concatenation. We can add "foo" + "bar" to get "foobar", and the empty string is an identity element for that operation. That is, if we say (s + "") or ("" + s), the result is always s. Furthermore, if we combine three strings by saying (r + s + t), the operation is associative—it doesn’t matter whether we parenthesize it: ((r + s) + t) or (r + (s + t)).
The term for this kind of algebra is monoid. The laws of associativity and identity are collectively called the monoid laws. A monoid consists of the following:
interface Semigroup<A> {
fun combine(a: A, b: A): A
} // Semigroup
interface Monoid<A : Any> : Semigroup<A> {
val empty: A
} // Monoid
where empty is the identity for the combine operation, and combine is an associative binary operation that takes two value of some type and combines them into one value of the same type. The Dogs library presents these two interfaces as well as a range of instances such as stringMonoid, intAdditionMonoid, ListSemigroup, ListMonoid, etc.
The implementation for function totalAges implements a fold over the collection with an Int zero as the seed for the fold and a binary addition on two Ints. Using intAddMonoid as an instance of Monoid we can define totalAges with:
object Analytics {
fun totalAges(authors: NonEmptyList<Author>): Int {
val mi: Monoid<Int> = intAddMonoid
fun age(author: Author): Int = LocalDate.now().year - author.yearOfBirth
return authors.foldLeft(mi.empty){ages: Int, author: Author -> mi.combine(ages, age(author))}
} // totalAges
// ...
} // Analytics
The operation within the fold is now an operation on a monoid instead of hardcoded operations on a specific type.
The Foldable foldMap
The foldable type also includes the foldMap function:
fun <A, B> F<A>.foldMap(mb: Monoid<B>, f: (A) -> B): B
Function foldMap is similar to our earlier fold operations, but maps every value of type A into a value of type B and then combines them using the given monoid. Here is our final version of Analytics:
object Analytics {
fun totalAges(authors: NonEmptyList<Author>): Int {
fun age(author: Author): Int = LocalDate.now().year - author.yearOfBirth
return authors.foldMap(intAddMonoid, ::age)
} // totalAges
fun oldest(authors: NonEmptyList<Author>): Int {
val intLargerMonoid: Monoid<Int> = object: Monoid<Int> {
override val empty: Int = 0
override fun combine(a: Int, b: Int): Int = max(a, b)
}
fun age(author: Author): Int = LocalDate.now().year - author.yearOfBirth
return authors.foldMap(intLargerMonoid, ::age)
} // oldest
} // Analytics
Both functions use foldMap. In function totalAges the intAddMonoid is used to accumulate the individual age of each author. In function oldest the custom intLargerMonoid is defined to find the largest age of each individual author. So given the foldable type NonEmptyList<A>, a type B that is a monoid, and a mapping function between A and B, we package foldMap into a combinator that abstracts the requirements for totalAges and oldest.
The code for the Dogs library can be found at:
https://github.com/KenBarclay/TBA
