Home Android & Kotlin Books Functional Programming in Kotlin by Tutorials

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 scrambled text.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

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
)

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

11. Functors 9. Data Types

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.

© 2022 Razeware LLC

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.

Read for Free with a Subscription

Buy this book for $59.99