# Functional Programming With Kotlin and Arrow — Algebraic Data Types

**, Kotlin 1.3, Other, IntelliJ IDEA**

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

### Sign up/Sign in

With a **free** Kodeco account you can download source code, track your progress,
bookmark, personalise your learner profile and more!

Already a member of Kodeco? Sign in

### Sign up/Sign in

With a **free** Kodeco account you can download source code, track your progress,
bookmark, personalise your learner profile and more!

Already a member of Kodeco? Sign in

### Sign up/Sign in

With a **free** Kodeco account you can download source code, track your progress,
bookmark, personalise your learner profile and more!

Already a member of Kodeco? Sign in

## Contents

## Functional Programming With Kotlin and Arrow — Algebraic Data Types

35 mins

- Getting Started
- What Is Algebra?
- Data Types and Multiplication
- Multiplying the Unit Type
- Multiplying the Nothing Type
- Multiplying Classes
- Data Types and Addition
- Understanding the Unit and Nothing Types
- Putting Algebra to Work
- Using Algebra for Type Safety
- Other Algebraic Properties
- Using Algebra With the Optional Type
- More Fun With Exponents
- Understanding Currying
- Carrying and the Flip Function
- Using Algebra With the List Type
- Functional Lists and Algebra
- Where to Go From Here?

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

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:

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:

- Define some types to use as placeholders. You don’t really care about what’s inside those classes here.
- 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:

- Have a
`Response`

without any`Info`

or`ErrorInfo`

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

- A
`Response`

and an`Info`

object, in case of success. - 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:

- You can represent the value
`A ^ 2`

as`A * A`

, which is equivalent to`Pair<A,A>`

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

- Define the
`Task`

typealias for any generic function which contains some code to execute at some time in the future. - Create a function,
`runDelayed()`

, which has a`Task`

as its first parameter and the`delay`

as the second. - Start a thread to simulate the async execution of the task.
- Use
`sleep()`

to wait for the delay you pass as a parameter. - 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:

- Using the reference to the existing
`runDelayed()`

, which is of type`(Task, Long) -> Unit`

. - Applying
`currying()`

to get a new function of type`(Task) -> (Long) -> Unit`

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

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

- The
`Zero`

value. - A set of all the possible
`Successor`

s.

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:

- The first value as
`ZERO`

. -
`ONE`

as the successor of`ZERO`

. -
`TWO`

as the successor of`ONE`

. -
`THREE`

as the successor of`TWO`

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

- Functional Programming With Kotlin and Arrow: Getting Started
- Functional Programming With Kotlin and Arrow Part 2: Categories and Functors
- Functional Programming With Kotlin and Arrow: Generate Typeclasses With Arrow
- Functional Programming With Kotlin and Arrow: More on Typeclasses

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.