Home · Android & Kotlin Tutorials

Functional Programming With Kotlin and Arrow — Algebraic Data Types

Learn how to use algebraic operations to better understand functional programming concepts like class constructs, typeclasses and lists in Kotlin & Arrow.

5/5 2 Ratings

Version

  • Kotlin 1.3, Other, IntelliJ IDEA

Functional programming is magic, and in this tutorial, you’ll use simple algebraic operations to get a deeper understanding of the most important functional programming principles.

In the previous tutorial, Functional Programming with Kotlin and Arrow Part 4 – Generate Typeclasses With Arrow, you learned how to generate the code to implement important typeclasses like Functor, Applicative and Monad.

In this tutorial, you’ll build on that knowledge to learn:

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

Understanding algebraic datatypes and how to use them will help you to master functional programming as they are very useful for encoding the business logic in applications.

Time to do some coding magic! :]

Note: The wonderful Bartosz Milewski’s Category Theory for Programmers course inspired this tutorial series. If you are new to Kotlin try Kotlin for Android: An Introduction to learn the fundamentals of Kotlin.

Getting Started

Download the materials for this tutorial using the Download Materials button at the top or bottom of this page. Open the project using IntelliJ 2019.x or greater and you’ll see the following structure:

Sample project structure

All the files are initially empty; it’ll be your job to add the code throughout this tutorial. But before writing any code, it’s important to understand the concept of algebra.

What Is Algebra?

Algebra is a generalization of arithmetic that lets you combine numbers and 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 and 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 has a lot in common and 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 {
  // ...
}

This class consists of a simple pair of values, the first of type A and the second of type B.

In the first tutorial of the series, Functional Programming with Kotlin and Arrow: Getting Started, you saw that a type is a way to represent all the possible values that a variable of that type can assume. For instance, a variable of type Boolean can contain the value true or false.

What about the Pair<A, B> type? How many values are available for a variable of type Pair<A, B>? To understand this, consider the type you’re defining by copying the following code into Struct.kt:

typealias BoolPair = Pair<Boolean, Boolean> 

If you want to count all the possible values for a variable of type BoolPair, simply add the following code:

val bool1 = Pair(true, true)
val bool2 = Pair(true, false)
val bool3 = Pair(false, true)
val bool4 = Pair(false, false)

From a pair of Boolean variables, which you can consider as the value 2, you get 4 values in total. But do you get those four values by adding 2+2 or multiplying 2*2?

Answer this question by adding the following definition to the same file:

enum class Triage {
    RED, YELLOW, GREEN
}

This defines the Triage type, which is an enum with three different values: RED, YELLOW and GREEN. Next, add the following code:

typealias BoolTriage = Pair<Boolean, Triage>

This defines a Pair consisting of a Boolean and a Triage. Now, repeat the same question: How many values does this type have?

To find out, simply use the following code:

val triple1 = Pair(true, Triage.RED)
val triple2 = Pair(true, Triage.YELLOW)
val triple3 = Pair(true, Triage.GREEN)
val triple4 = Pair(false, Triage.RED)
val triple5 = Pair(false, Triage.YELLOW)
val triple6 = Pair(false, Triage.GREEN)

which proves that the possible values are:

Boolean * Triage = 2 * 3 = 6

This brings you to the conclusion that a Pair<A, B> has as many values as the product of multiplying the values of A by the values of B.

Now take a look at what happens when incorporating the Unit type into the multiplication.

Multiplying the Unit Type

In the first tutorial of this series, you learned that the Unit type has a single instance with the same name Unit. In Struct.kt, add the following definition:

typealias UnitTriage = Pair<Unit, Triage>

Now, note that the number of possible values is the value you get by adding the following code to the same file:

val unit1 = Pair(Unit, Triage.RED)
val unit2 = Pair(Unit, Triage.YELLOW)
val unit3 = Pair(Unit, Triage.GREEN)

You then have:

Unit * Triage = 1 * 3 = 3

This proves that the Unit is equivalent to the value 1 when you multiply with it.

Multiplying the Nothing Type

In the first tutorial of this series, you also learned about the Nothing type, which is a type with no values. What happens if you add the following definition to Struct.kt?

typealias NothingTriage = Pair<Nothing, Triage>

When you try to add the following code, you’ll get an error. This is because you can’t have a value of type Nothing so you can’t create an instance of the NothingTriage type.

val nothing1 : NothingTriage = Pair(???, Triage.RED)

This means that the type Nothing corresponds to the value 0 for multiplication purposes. In this case you can say that:

Nothing * Triage = 0 * 3 = 0

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)

Based on what you learned in this paragraph, you can say that:

Struct = Boolean * Triage * Byte = 2 * 3 * 256 = 1536

The number of possible values is the product of multiplying all the values of the aggregated types. In this last example, Byte has 256 values, so the total number of values is 1,536.

But what happens when you do something like this instead:

data class Struct2(val enabled: Boolean, val triage: Triage, val name: String)

String has many possible values, so you can’t determine an exact result — but having an exact result is also not important. As you’ll see later, the important thing is to understand that you can represent the relationship between types as a multiplication operation.

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 the previous tutorials of this series:

sealed class Either<out A, out B>
class Left<A>(val left: A) : Either<A, Nothing>()
class Right<B>(val right: B) : Either<Nothing, B>()

This is the Either<E, A> data type, which represents a value of type A or a value of type B. For your next step, you’ll repeat the same exercise, trying to understand how many values the Either<E, A> type has in relation to the number of values of A and B.

Start by adding the following definition to Either.kt:

typealias EitherBooleanOrBoolean = Either<Boolean, Boolean>

Then add the following code:

val either1 = Left(true)
val either2 = Left(false)
val either3 = Right(true)
val either4 = Right(false)

This is the list of all possible values of the EitherBooleanOrBoolean type, which you can think of as:

Boolean + Boolean = 2 + 2 = 4

This is, perhaps, not the best example because, as you saw earlier, 4 is 2 + 2 but also 2 * 2. However, you already learned how to solve this problem.

In this case, just add the following definition to Either.kt:

typealias EitherBooleanOrTriage = Either<Boolean, Triage>

Now, add the following values:

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)

This proves that:

Boolean + Triage = 2 + 3 = 5

The Boolean type has 2 values and the Triage type has 3 values, so the EitherBooleanOrTriage type has 2 + 3 = 5 values.

Understanding the Unit and Nothing Types

It’s now easy to see what the role of the Unit and Nothing types are in the case of Either<E, A>. 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)

Now, it’s simple to understand that:

Boolean + Nothing = 2 + 0 = 2

The Nothing type, as you saw earlier for multiplication, translates to 0.

And now for the Unit case, enter:

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)

Which translates to:

Boolean + Unit = 2 + 1 = 3

Just as when you multiplied it earlier, the Unit type counts as 1.

Putting Algebra to Work

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

But how is this knowledge useful?

As a simple example, open TypeSafeCallback.kt and enter the following definition:

typealias Callback<Data, Result, Error> = (Data, Result?, Error?) -> Unit

This is the definition of a Callback<Data, Result, Error> type. This could, for example, represent the operation you invoke to notify something of the result of an asynchronous task.

It’s important to note that you define the Result and Error types as optional.

With this type, you want to consider that:

  • You always receive some data back from the asynchronous function.
  • If the result is successful, you receive the content in a Result object, which is null otherwise.
  • If there are any errors, you receive a value of type Error, which is also null otherwise.

You can simulate a typical use case of the previous type by enering the following code into TypeSafeCallback.kt:

// 1
class Response
class Info
class ErrorInfo

// 2
fun runAsync(callback: Callback<Response, Info, ErrorInfo>) {
    // TODO 
}

In this code you:

  1. Define some types to use as placeholders. You don’t really care about what’s inside those classes here.
  2. Create runAsync with a parameter of Callback<Data, Result, Error>.

An example of when to implement runAsync() is when you’re performing an asynchronous operation and you invoke the callback function, then pass the corresponding parameter. For instance, in case of success, runAsync() might result in the following, where you return some Response and the Info into it:

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

If there’s an error, you could use the following code to return the Response along with ErrorInfo, which encapsulates information about the problem.

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

But there’s a problem with this: The type you define using the Callback<Data, Result, Error> typealias is not type-safe. It describes values that make no sense in runAsync()‘s case. That type doesn’t prevent you from having code like the following:

fun runAsync(callback: Callback<Response, Info, ErrorInfo>) {
    // 1
    callback(Response(), null, null)
    // 2
    callback(Response(), Info(), ErrorInfo())
}

Here you you might:

  1. Have a Response without any Info or ErrorInfo.
  2. Return both Info and ErrorInfo.

This is because the return type allows those values. You need a way to implement type safety.

Using Algebra for Type Safety

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

What you’re expecting from the callback is:

A Result AND an Info OR a Result AND an ErrorInfo

You can represent the previous sentence as:

Result * Info + Result * ErrorInfo

Now, apply the associative property and get:

Result * (Info + ErrorInfo)

This is similar to what you saw in the previous paragraphs.

Next, translate this to the following and add it to TypeSafeCallback.kt:

typealias SafeCallback<Data, Result, Error> = (Pair<Data, Either<Error, Result>>) -> Unit

The safe version of runAsync now looks like the following code, which you can also add to TypeSafeCallback.kt:

fun runAsyncSafe(callback: SafeCallback<Response, Info, ErrorInfo>) {
    // 1
    callback(Response() to Right(Info()))
    // 2
    callback(Response() to Left(ErrorInfo()))
}

The only values you can return using the safe callback are:

  1. A Response and an Info object, in case of success.
  2. In case of error, the same Response but with an ErrorInfo.

More important than what you can do is what you cannot do. You cannot return both Info and ErrorInfo, but you must return at least one of them.

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

Which translates into:

A * Unit = A = Unit * A

This tells you that Pair<A, Unit> is the same as Pair<Unit, A>, which is the same as A.

typealias UnitType<A> = Pair<A, Unit>

It also means that adding a property of type Unit to an existing type doesn’t add any useful information.

You also know that:

A + 0 = A = 0 + A

This becomes:

A + Nothing = A = Nothing + A

This represents a type that you can write as:

typealias NothingType<A> = Either<Nothing, A>

Finally, you can write:

A * 0 = 0 = 0 * A

Which becomes:

A * Nothing = 0 = Nothing * A

You can write this as:

typealias NothingPair<A> = Pair<A, Nothing>

You can’t create a Pair using a value of type A and Nothing, so this is basically the Nothing type.

Using Algebra With the Optional Type

Another curious thing is that:

A + 1 = A + Unit = Either<A, Unit>
1 + A = Unit + A = Either<Unit, A>

This means that the Either<A, Unit> type has all the possible values of A plus a single value which is Unit. It’s something you could represent like:

sealed class Opt<out A>
object None : Opt<Nothing>()
class Some<A>(value: A) : Opt<A>()

Do you recognize it? This is basically the Optional type. You have a value of type A or you have another single and unique value which is None here, but could also be Unit.

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

Start by writing the following expression:

// 1
A ^ 2 = A * A = Pair<A,A>
// 2
A ^ 3 = A * A * A = Pair<A, Pair<A,A>> = Pair<Pair<A,A>, A>
// ...

Starting from a given type A, you can see that:

  1. You can represent the value A ^ 2 as A * A, which is equivalent to Pair<A,A>.
  2. For the same reason, you can think of A ^ 3 as A * A * A, which is equivalent to Pair<A,Pair<A,A>> or Pair<Pair<A,A>, A>.

The same is true for each value of the exponent.

But what about the meaning of the expression A ^ B, where A and B are types? How many possible values can you represent with a type that corresponds to the expression, like Boolean ^ Triage?

This is less intuitive and needs some more work.

If the analogy between types and algebra is true, the number of values for the type Boolean ^ Triage should be 8 because:

Boolean ^ Triage = 2 ^ 3 = 8

But what does the number 8 represent? It represents how you can take the number of values of Boolean to the power of the number of values of Triage. This can happen in multiple ways — which are the number of ways you can associate a Boolean value to a value of the Triage type.

This perfectly describes the (Triage) -> Boolean function type. You can prove this by adding the following code to Exponents.kt:

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
}

There are exactly 8 different ways of mapping a Triage value into a Boolean value. You can think of A ^ B as equivalent to a function from B to A. You can then assert that:

A ^ B = (B) -> A

Understanding Currying

You can use what you learned in the previous paragraph to prove some interesting facts. Given three types A, B and C, you know that:

(A ^ B) ^ C = A ^ (B * C)

The equality = is symmetric so you can also write:

A ^ (B * C) = (A ^ B) ^ C 

Now, recall what you learned in the previous paragraphs about multiplication and exponentiation and translate that to:

(Pair<B,C>) -> A = (C) -> (B) -> A 

Using some Kotlin notation, you can write this as:

(B,C) -> A = (C) -> (B) -> A 

Sorting the types’ variables in an easier way, you can read that equation by saying that a function of two input parameters, A and B, and output C (A, B) -> C is equivalent to a function with an input parameter of A and an output parameter of function type (B) -> C. This is called currying. You define currying by adding the following code to Exponents.kt.

fun <A, B, C> Func2<A, B, C>.currying(): (A) -> (B) -> C = { a: A ->
    { b -> this(a, b) }
}

Func2<A, B, C> is a typealias. Define it by copying the following code to Exponents.kt:

typealias Func2<A, B, C> = (A, B) -> C

This represents any function with two input parameters and one output parameter.

As you saw earlier, the equivalence is symmetric so you can define the inverse function by adding the following code:

fun <A, B, C> Chain<A, B, C>.uncurrying(): Func2<A, B, C> = { a: A, b: B ->
    this(a)(b)
}

Add this as well:

typealias Chain<A, B, C> = (A) -> (B) -> C

This is a typealias that defines a function’s type with a single input parameter and another function as an output parameter.

Carrying and the Flip Function

When you work on platforms like Android, it’s not uncommon to use functions like the one below. Enter the following code into Exponents.kt:

// 1
typealias Task = () -> Unit

// 2
fun runDelayed(task: Task, delay: Long) {
    // 3
    thread {
        // 4
        sleep(delay)
        // 5
        task()
    }
}

With this example you:

  1. Define the Task typealias for any generic function which contains some code to execute at some time in the future.
  2. Create a function, runDelayed(), which has a Task as its first parameter and the delay as the second.
  3. Start a thread to simulate the async execution of the task.
  4. Use sleep() to wait for the delay you pass as a parameter.
  5. Run the task, invoking the related parameter.

What’s important here is that the delay parameter comes second. This is not unusual; in Android, you can find similar methods like:

fun postDelayed(r: Runnable, delayMillis: Long): Boolean

The same happens, for instance, in other contexts like the one related to the following constructor for String:

String(byteArrayOf(), Charsets.ISO_8859_1)

As you can see, in this case, the Charset is the second parameter. You have to include it in every place where you use that specific constructor in the same way as the delay in the previous snippets of code. How can you make the code easier to write and maintain?

As a first step, define flip() by copying the following code into Exponents.kt:

fun <A, B, C> Chain<A, B, C>.flip(): Chain<B, A, C> = { b: B ->
    { a ->
        this(a)(b)
    }
}

This is a higher-order function that transforms a function of type (A) -> (B) -> C into a function of type (B) -> (A) -> C. There, the first two parameters are swapped or, as the function name says, flipped.

Now, use this function to define a new run1SecondDelayed by entering the following code into Exponents.kt:

val run1SecondDelayed = ::runDelayed // 1
    .currying() // 2
    .flip()(1000L) // 3

In this code, you define run1SecondDelayed by:

  1. Using the reference to the existing runDelayed(), which is of type (Task, Long) -> Unit.
  2. Applying currying() to get a new function of type (Task) -> (Long) -> Unit.
  3. Using flip() to get a function of type (Long) -> (Task) -> Unit, which you invoke using a specific duration value.

The result is a function of type (Task) -> Unit, which you invoke with the following simple code:

    run1SecondDelayed {
        println("Printed after 1 sec")
    }

Note that you specify the duration just once. You can do the same with the String constructor by writing code like:

// 1
val strContr: Func2<ByteArray, Charset, String> = ::String
// 2
val isoStrConstr = strContr.currying().flip()(Charsets.ISO_8859_1)

In this code, you:

  1. Define strContr as the reference to the constructor, which accepts an array of bytes as the first parameter and the Charset as the second. It’s important to note that Kotlin requires an explicit type definition to address a specific constructor overload.
  2. Apply currying and flip to set the Charset in a single location.

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
class Successor(prec: NaturalNumber) : NaturalNumber()

This is a simple sealed class which represents all the natural numbers as:

  1. The Zero value.
  2. A set of all the possible Successors.

As an example, add the following to the same file:

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

Here you define:

  1. The first value as ZERO.
  2. ONE as the successor of ZERO.
  3. TWO as the successor of ONE.
  4. THREE as the successor of TWO.
  5. And so on…

What’s more interesting is, comparing the previous definition with the one about Either<E, A>, you can say that:

NaturalNumber = 1 + NaturalNumber

This is because you translate Either into an addition operation, but the previous addition becomes:

NaturalNumber = 1 + NaturalNumber
NaturalNumber = 1 + (1 + NaturalNumber)
NaturalNumber = 1 + (1 + (1 + NaturalNumber))
NaturalNumber = 1 + (1 + (1 + (1 + NaturalNumber)))
...

This suggests that the Set of NaturalNumber can be seen as a sequence of ones, one for each natural number.

Consider now the List<A> data type. Using the same reasoning, you can think of it as something you can define by entering the following code into List.kt:

sealed class FList<out A>
object FEmpty : FList<Nothing>()
class Tail<A>(val head: A, val tail: FList<A>) : FList<A>()

Use the name FList — aka, Functional List — to distinguish it from the existing List type.

This means that a FList<A> can be empty, or you can think of it as a head and a tail which might be empty or not. You can then create a list of five values in the following way, and add it to List.kt:

val countList = Tail(1, Tail(2, Tail(3, Tail(4, Tail(5, FEmpty)))))

Functional Lists and Algebra

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

fun FList<Int>.sum(): Int = when (this) {
    is FEmpty -> 0
    is Tail<Int> -> head + tail.sum()
}

Now, test it by copying and running the following code in List.kt:

fun main() {
    println(countList.sum())
}

But from an algebraic point of view, you write the previous FList<A> type like this:

FList<A> = 1 + A * FList<A>

This is because it can be the FEmpty (and so the 1) or a Pair of an object of type A and another FList<A>.

Now, repeat what you did in the case of the NaturalNumber and get:

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

This allows you to see the FList<A> as a possible combination of all the possible FList<A> of length 0, 1, 2, 3 and so on.

The + here has the meaning of a logical OR so an FList<A> is an empty Flist OR a single element of type A OR a pair of elements of type A OR a triplet of elements of type A and so on.

Write this as:

FList<A> = 1 + A * FList<A>    =>
FList<A> - A * FList<A> = 1    =>

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

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

This is the geometric series, which is equivalent to:

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

It’s curious how a complex data type like List<A> has an algebraic relationship.

Where to Go From Here?

Download the completed project by using the Download Materials button at the top or bottom of this tutorial. You can find other tutorials in this series at:

Congratulations! In this tutorial, you learned how algebra can help you understand the main concepts and tools of functional programming.

In the next tutorials in this series, you’ll see how these apparently theoretical concepts have important practical implications.

In the next tutorial, you’ll have the opportunity to go deeper into side effect management by using Arrow Fx.

If you have any comments or questions, feel free to join in the forum below.

Average Rating

5/5

Add a rating for this content

2 ratings

More like this

Contributors

Comments