10
Algebraic Data Types
Written by Massimo Carli
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as
text.You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.
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
andc
. - 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
)
Data types and addition
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
Exponentials and addition
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 head: 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 ofA
andB
. - A Cartesian product of a type
A
and a typeB
is a new type, represented asA × B
. Its values are all the pairs(a, b)
that you can create using a valuea
fromA
and a valueb
fromB
. - The term isomorphic means “having the same form or structure”. Two types,
A
andB
, are isomorphic if a function of typeFun<A, B>
maps each value ofA
to one and only one value inB
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 typeFun<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.