## Functional Programming in Kotlin by Tutorials

First Edition · Android 12 · Kotlin 1.6 · IntelliJ IDEA 2022

#### Before You Begin

Section 0: 5 chapters

#### Section II: Data Types & Typeclasses

Section 2: 5 chapters

# 10. Algebraic Data Types Written by Massimo Carli

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

In Chapter 2, “Function Fundamentals”, you saw that math and functional programming have a strong relationship. You learned that category theory is the theory of composition, which is one of the main concepts of functions. In Chapter 9, “Data Types”, you also learned the concept of data types by studying examples like `Optional<T>`, `List<T>`, `Either<A, B>` and others. In this chapter, you’ll learn about the strong relationship between a data type and math. In particular, you’ll learn:

• What algebra is and how it translates to the class construct and the `Either<E, T>` data type in Kotlin.
• How and when algebraic data types are useful, including a practical example.
• After addition and multiplication, you’ll see what the implications of exponents are.
• How to mathematically prove the currying operation.
• What a simple `List<T>` has in common with algebra.

Understanding algebraic data types and their use will help you master functional programming, as they’re especially useful for encoding business logic in applications.

Time to do some coding magic with Kotlin and some interesting exercises!

Note: This is a very theoretical chapter that gives you some mathematical proofs of the concepts you’ve met so far in the book. Feel free to skip it or read it later if you want.

## What is algebra?

Algebra is a category of arithmetic that lets you combine numbers with letters representing numbers by using specific rules. Here’s an example of a simple algebraic expression:

``````a * X ^ 2 - b * X + c
``````

In this example, you have:

• Numbers, like the `2`.
• Letters, like `a`, `b` and `c`.
• Operations, like multiplication `*`, addition `+` and exponentiation `^`.

Algebra is the set of rules that allow you to combine all those different symbols. But what does this have to do with Kotlin and functional programming?

Algebra and functional programming have a lot in common. Because of this, programmers can use algebra to understand exactly how functional programming constructs work, starting with product types.

## Data types and multiplication

The Kotlin APIs define many classes, including `Pair<A, B>`, which has the following simple code:

``````public data class Pair<out A, out B>(
public val first: A,
public val second: B
) : Serializable {
// ...
}
``````
``````typealias BoolPair = Pair<Boolean, Boolean>
``````
``````val bool1 = true to true
val bool2 = true to false
val bool3 = false to true
val bool4 = false to false
``````
``````enum class Triage {
RED, YELLOW, GREEN
}
``````
``````typealias BoolTriage = Pair<Boolean, Triage>
``````
``````val triple1 = true to Triage.RED
val triple2 = true to Triage.YELLOW
val triple3 = true to Triage.GREEN
val triple4 = false to Triage.RED
val triple5 = false to Triage.YELLOW
val triple6 = false to Triage.GREEN
``````
``````Boolean * Triage = 2 * 3 = 6
``````
``````typealias Triplet = Triple<UByte, Boolean, Unit>
``````

### Product with the unit type

You already know the `Unit` type has a single instance with the same name, `Unit`. In Struct.kt, add the following definition:

``````typealias UnitTriage = Pair<Unit, Triage>
``````
``````val unit11 = Unit to Triage.RED
val unit21 = Unit to Triage.YELLOW
val unit31 = Unit to Triage.GREEN
``````
``````Unit * Triage = 1 * 3 = 3
``````
``````Unit * Triage = 1 * 3 = 3 = 3 * 1 = Triage * Unit
``````
``````val unit12 = Triage.RED to Unit
val unit22 = Triage.YELLOW to Unit
val unit32 = Triage.GREEN to Unit
``````
``````typealias TriageUnit = Pair<Triage, Unit>
``````
``````Unit * Triage = 1 * 3 = 3 * 1 = Triage * Unit
``````
``````fun isEven(a: Int): Boolean = a % 2 == 0
``````
``````fun booleanToInt(even: Boolean): Int = if (even) 1 else 0
``````
``````val isEvenInt = ::isEven compose ::booleanToInt
``````
``````typealias Unique = Pair<Unit, Unit>
``````

### Multiplying the Nothing type

In Chapter 2, “Function Fundamentals”, you learned about the `Nothing` type. It’s helpful to know what `Nothing` means in terms of algebraic data types. In Struct.kt, add the following definition:

``````typealias NothingTriage = Pair<Nothing, Triage>
``````
``````val nothing1 : NothingTriage = Pair(???, Triage.RED)
``````
``````Nothing * Triage = 0 * 3 = 0 = 3 * 0 = Triage * Nothing
``````
``````typealias TriageNothing = Pair<Triage, Nothing>
``````

### Multiplying classes

In the previous examples, you used `Pair<A, B>`, but what happens if you define a class like so:

``````data class Struct(
val enabled: Boolean,
val triage: Triage,
val value: Byte
)
``````
``````Struct = Boolean * Triage * Byte = 2 * 3 * 256 = 1536
``````
``````data class AnotherStruct(
val enabled: Boolean,
val triage: Triage,
val name: String
)
``````

The next question is about addition, which is another fundamental algebraic operation. Open Either.kt and copy the following code, which you might remember from Chapter 9, “Data Types”:

``````sealed class Either<out A, out B>
data class Left<A>(val left: A) : Either<A, Nothing>()
data class Right<B>(val right: B) : Either<Nothing, B>()
``````
``````typealias EitherBooleanOrBoolean = Either<Boolean, Boolean>
``````
``````val either1 = Left(true)
val either2 = Left(false)
val either3 = Right(true)
val either4 = Right(false)
``````
``````Boolean + Boolean = 2 + 2 = 4
``````
``````typealias EitherBooleanOrTriage = Either<Boolean, Triage>
``````
``````val eitherTriage1: Either<Boolean, Triage> = Left(true)
val eitherTriage2: Either<Boolean, Triage> = Left(false)
val eitherTriage3: Either<Boolean, Triage> = Right(Triage.RED)
val eitherTriage4: Either<Boolean, Triage> = Right(Triage.YELLOW)
val eitherTriage5: Either<Boolean, Triage> = Right(Triage.GREEN)
``````
``````Boolean + Triage = 2 + 3 = 5
``````
``````typealias MultiEither = Either<UByte, Either<Boolean, Triage>>
``````
``````typealias MultiEither2 = Either<Either<UByte, Boolean>, Triage>
``````

### Addition with Unit and Nothing types

Now it’s easy to see the role of the `Unit` and `Nothing` types in the case of `Either<A, B>`. You already know how to understand this. Enter the following code in Either.kt:

``````typealias EitherBooleanOrNothing = Either<Boolean, Nothing>

val boolNothing1: Either<Boolean, Nothing> = Left(true)
val boolNothing2: Either<Boolean, Nothing> = Left(false)
``````
``````Boolean + Nothing = 2 + 0 = 2
``````
``````typealias EitherBooleanOrUnit = Either<Boolean, Unit>

val boolUnit1: Either<Boolean, Unit> = Left(true)
val boolUnit2: Either<Boolean, Unit> = Left(false)
val boolUnit3: Either<Boolean, Unit> = Right(Unit)
``````
``````Boolean + Unit = 2 + 1 = 3
``````

## Putting algebra to work

After some simple calculations, you now understand that a class can represent values that are, in number, the product of multiplying the possible values of the aggregated types. You also learned that `Either<A, B>` has as many values as the sum of the values of types `A` and `B`.

``````typealias Callback<Data, Result, Error> =
(Data, Result?, Error?) -> Unit
``````
``````// 1
class Response
class Info
class ErrorInfo

// 2
fun runAsync(callback: Callback<Response, Info, ErrorInfo>) {
// TODO
}
``````
``````fun runAsync(callback: Callback<Response, Info, ErrorInfo>) {
// In case of success
callback(Response(), Info(), null)
}
``````
``````fun runAsync(callback: Callback<Response, Info, ErrorInfo>) {
// In case of error
callback(Response(), null, ErrorInfo())
}
``````
``````fun runAsync(callback: Callback<Response, Info, ErrorInfo>) {
// 1
callback(Response(), null, null)
// 2
callback(Response(), Info(), ErrorInfo())
}
``````

### Using algebra for type safety

Algebraic data types can help with type safety. You need to translate the semantic of `Callback<Data, Result, Error>` into an algebraic expression. Then, apply some mathematic rules.

``````A Result AND an Info OR a Result AND an ErrorInfo
``````
``````Result * Info + Result * ErrorInfo
``````
``````Result * (Info + ErrorInfo)
``````
``````typealias SafeCallback<Data, Result, Error> =
(Pair<Data, Either<Error, Result>>) -> Unit
``````
``````fun runAsyncSafe(callback: SafeCallback<Response, Info, ErrorInfo>) {
// 1
callback(Response() to Right(Info()))
// 2
callback(Response() to Left(ErrorInfo()))
}
``````

## Other algebraic properties

The analogy between types and algebra is fun because it reveals some interesting facts. For instance, you know that:

``````A * 1 = A = 1 * A
``````
``````A * Unit = A = Unit * A
``````
``````A + 0 = A = 0 + A
``````
``````A + Nothing = A = Nothing + A
``````
``````typealias NothingType<A> = Either<Nothing, A>
``````
``````A * 0 = 0 = 0 * A
``````
``````A * Nothing = 0 = Nothing * A
``````
``````typealias NothingPair<A> = Pair<A, Nothing>
``````

### Algebra with the Optional type

Another curious thing is that:

``````A + 1 = A + Unit = Either<A, Unit>
1 + A = Unit + A = Either<Unit, A>
``````
``````sealed class Opt<out A>
object None : Opt<Unit>()
class Some<A>(value: A) : Opt<A>()
``````

## Fun with exponents

So far, you’ve seen what multiplication and addition mean in the context of types. Next, you’ll see what you can express using exponents.

``````// 1
A ^ 2 = A * A = Pair<A, A>
// 2
A ^ 3 = A * A * A = Pair<A, Pair<A, A>> = Pair<Pair<A, A>, A>
// ...
``````
``````Boolean ^ Triage = 2 ^ 3 = 8
``````
``````fun func0(triage: Triage): Boolean = when (triage) {
Triage.RED -> false
Triage.YELLOW -> false
Triage.GREEN -> false
}

fun func1(triage: Triage): Boolean = when (triage) {
Triage.RED -> false
Triage.YELLOW -> false
Triage.GREEN -> true
}

fun func2(triage: Triage): Boolean = when (triage) {
Triage.RED -> false
Triage.YELLOW -> true
Triage.GREEN -> false
}

fun func3(triage: Triage): Boolean = when (triage) {
Triage.RED -> false
Triage.YELLOW -> true
Triage.GREEN -> true
}

fun func4(triage: Triage): Boolean = when (triage) {
Triage.RED -> true
Triage.YELLOW -> false
Triage.GREEN -> false
}

fun func5(triage: Triage): Boolean = when (triage) {
Triage.RED -> true
Triage.YELLOW -> false
Triage.GREEN -> true
}

fun func6(triage: Triage): Boolean = when (triage) {
Triage.RED -> true
Triage.YELLOW -> true
Triage.GREEN -> false
}

fun func7(triage: Triage): Boolean = when (triage) {
Triage.RED -> true
Triage.YELLOW -> true
Triage.GREEN -> true
}
``````
``````A ^ B = (B) -> A
``````

### Proving currying

In Chapter 8, “Composition”, you learned about the `curry` function. It basically allows you to define the equivalence between a function of type `(A, B) -> C` with a function of type `(A) -> (B) -> C`. But where does `curry` come from? Is it something that always works, or is it a fluke? It’s time to prove it.

``````(A ^ B) ^ C = A ^ (B * C)
``````
``````A ^ (B * C) = (A ^ B) ^ C
``````
``````(Pair<B, C>) -> A = (C) -> (B) -> A
``````
``````(B, C) -> A = (C) -> (B) -> A
``````
``````fun <A, B, C> Fun2<A, B, C>.curry(): (A) -> (B) -> C = { a: A ->
{ b: B ->
this(a, b)
}
}
``````

### Nothing and exponents

As you may know, in math:

``````A ^ 0 = 1
``````
``````A ^ Nothing = Unit
``````
``````(Nothing) -> A = Unit
``````

### Powers and 1

Keep having fun with the following equivalence:

``````1 ^ A = 1
``````
``````(A) -> Unit = Unit
``````
``````A ^ 1 = A
``````
``````(Unit) -> A = A
``````

Another important property for exponents is:

``````A ^ (B + C) = A ^ B * A ^ C
``````
``````(Either<B, C>) -> A = Pair<(B) -> A, (C) -> A>
``````

## Using algebra with the List type

As a last bit of fun with algebra and types, enter the following definition into List.kt:

``````sealed class NaturalNumber
// 1
object Zero : NaturalNumber()
// 2
data class Successor(val prev: NaturalNumber) : NaturalNumber()
``````
``````// 1
val ZERO = Zero
// 2
val ONE = Successor(Zero)
// 3
val TWO = Successor(Successor(Zero)) // Successor(ONE)
// 4
val THREE = Successor(Successor(Successor(Zero))) // Successor(TWO)
// 5
// ...
``````
``````NaturalNumber = 1 + NaturalNumber
``````
``````NaturalNumber = 1 + NaturalNumber
NaturalNumber = 1 + (1 + NaturalNumber)
NaturalNumber = 1 + (1 + (1 + NaturalNumber))
NaturalNumber = 1 + (1 + (1 + (1 + NaturalNumber)))
...
``````
``````sealed interface FList<out A>
object Nil : FList<Nothing>
data class FCons<A>(
val tail: FList<A> = Nil
) : FList<A>
``````
``````val countList =
FCons(1, FCons(2, FCons(3, FCons(4, FCons(5, Nil)))))
``````

### Functional lists and algebra

Now, what if you want to calculate the sum of the elements in `FList<Int>`? You do it by implementing a recursive function, like this:

``````fun FList<Int>.sum(): Int = when (this) {
is Nil -> 0
is FCons<Int> -> head + tail.sum()
}
``````
``````fun main() {
println(countList.sum())
}
``````
``````15
``````
``````FList<A> = 1 + A * FList<A>
``````
``````FList<A>  = 1 + A * FList<A>
= 1 + A * (1 + A * FList<A>) = 1 + A + A ^ 2 + A * FList<A>
= 1 + A + A ^ 2 + A ^ 3 + A ^ 4 * FList<A>
...
``````
``````FList<A> = 1 + A * FList<A>    =>
FList<A> - A * FList<A> = 1    =>

FList<A> * (1 - A) = 1         =>

1
FList<A> =  -------
(1 - A)
``````
``````               1
FList<A> =  ------- = 1 + A + A^2 + A^3 + A^4 + .... + A^N + ...
(1 - A)
``````

## Key points

• Algebra is a category of arithmetic that lets you combine numbers with letters representing numbers by using specific rules.
• You can think of a type as the Cartesian product of the types of its properties. For instance, `Pair<A, B>` is the Cartesian product of `A` and `B`.
• A Cartesian product of a type `A` and a type `B` is a new type, represented as `A × B`. Its values are all the pairs `(a, b)` that you can create using a value `a` from `A` and a value `b` from `B`.
• The term isomorphic means “having the same form or structure”. Two types, `A` and `B`, are isomorphic if a function of type `Fun<A, B>` maps each value of `A` to one and only one value in `B` and vice versa.
• Two isomorphic types are equivalent in the sense that you can use one or the other without adding or removing any type of information.
• Exponents like `A ^ B` are equivalent to the function type `Fun<B, A>`.
• Exponents’ properties allow you to have evidence of some important functional programming concepts. For instance, the fact that `(A ^ B) ^ C = A ^ (B * C)` proves currying.

## Where to go from here?

Wow! In this chapter, you had a lot of fun using math to prove some important functional programming tools like currying. As mentioned in the chapter’s introduction, these concepts give you some helpful information for thinking more functionally. In the next chapter, you’ll start learning all about the concept of functors and the `map` function.

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.