10. Algebraic Data Types

Written by Massimo Carli

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

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

In Chapter 2, “Function Fundamentals”, you saw that a type is a way to represent all the possible values a variable of that type can assume. For instance, a Boolean type can contain a value of 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, which you’ll find in this chapter’s material:

typealias BoolPair = Pair<Boolean, Boolean>

To count all the possible values for a variable of type BoolPair, simply add the following code:

val bool1 = true to true
val bool2 = true to false
val bool3 = false to true
val bool4 = false to false

From a pair of Boolean variables, which you can consider a value of 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 = 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

Which proves the possible values are:

Boolean * Triage = 2 * 3 = 6

This illustrates that a Pair<A, B> has as many values as the product of multiplying A’s values by B’s values. This is called the Cartesian product of A and B, which you can represent as A × B. This concept becomes much easier if you use the analogy of a type with a set of values you learned in Chapter 2, “Function Fundamentals”. If A represents all the values of type A and B all the values of type B, the set A × B represents the product of the types A and B. A × B is the set of all pairs (a, b) where a is an element of A and b an element of B.

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

Exercise 10.1: What’s the cardinality of the following type?

typealias Triplet = Triple<UByte, Boolean, Unit>

Note: The cardinality of a set is the number of elements that set can represent. For example, the cardinality of a Boolean would be 2, and the cardinality of the Triage class above is 3.

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>

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

val unit11 = Unit to Triage.RED
val unit21 = Unit to Triage.YELLOW
val unit31 = Unit to Triage.GREEN

You then have:

Unit * Triage = 1 * 3 = 3

This proves the Unit is equivalent to the value 1 when you multiply by it. It’s also important to note that:

Unit * Triage = 1 * 3 = 3 = 3 * 1 = Triage * Unit

This leads you to:

val unit12 = Triage.RED to Unit
val unit22 = Triage.YELLOW to Unit
val unit32 = Triage.GREEN to Unit

Which you can think of as values of type:

typealias TriageUnit = Pair<Triage, Unit>

In the case of Unit and multiplication, consider the following declaration:

Unit * Triage = 1 * 3 = 3 * 1 = Triage * Unit

It looks like TriageUnit and UnitTriage are the same. They aren’t, but, in terms of functions, they’re not so different. You can implement a function that maps every element of TriageUnit to one and only one element of UnitTriage and vice versa. This function is then isomorphic. This means a function of type Fun<A, UnitTriage> isn’t so different from Fun<A, TriageUnit>. This is because you can think of the latter as the composition of the former with an isomorphic function.

Note: Isomorphism was introduced in Chapter 2, “Function Fundamentals”. You’ll continue learning more in Chapter 11: “Functors”, and Chapter 12: “Monoids & Semigroups”.

For a more practical example, consider a function like the following:

fun isEven(a: Int): Boolean = a % 2 == 0

This function has type Fun<Int, Boolean> and returns true if the Int value in input is even. Consider, now, the following function:

fun booleanToInt(even: Boolean): Int = if (even) 1 else 0

This is an isomorphic function of type Fun<Boolean, Int> that maps true to 1 and false to 0. You also could’ve mapped true to 0 and false to 1. The important part is the meaning of the following function:

val isEvenInt = ::isEven compose ::booleanToInt

In this case, you just use different values to represent the same information about the Int passed as input. isEvenInt has type Fun<Int, Int> instead of the type Fun<Int, Boolean> of isEven. The Int value’s information you get from isEvenInt is actually the same as the Boolean you get from isEven. From a mathematical point of view, you can think of them as the same thing and say that TriageUnit and UnitTriage are isomorphic types. From a category theory point of view, you can say that isomorphic types have the same structures.

Exercise 10.2: What’s the cardinality of the following type?

typealias Unique = Pair<Unit, Unit>

Is this isomorphic with 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>

When you try to add the following code, you 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 the type Nothing corresponds to the value 0 for multiplication purposes. In this case, you can say that:

Nothing * Triage = 0 * 3 = 0 = 3 * 0 = Triage * Nothing

Using the set analogy, Nothing represents the empty set. You might wonder if an empty Set<A> is different from an empty Set<B>. They’re definitely isomorphic. You can then say that NothingTriage and Nothing are isomorphic types, as it would be the type you define like:

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
)

Based on what you’ve already learned, 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 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 AnotherStruct(
  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 isn’t 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 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>()

This is the Either<E, A> data type, representing a value of type A or a value of type B. For your next step, you’ll repeat the same exercise. But this time, you’ll try to understand how many values the Either<A, B> 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, perhaps, isn’t the best example because, as you saw earlier, 4 is 2 + 2 but also 2 * 2. However, you’ve 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 in total.

Exercise 10.3: What’s the cardinality of the following type?

typealias MultiEither = Either<UByte, Either<Boolean, Triage>>

Is MultiEither isomorphic with MultiEither2, which you define in the following way?

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)

Now, it’s simple to understand that:

Boolean + Nothing = 2 + 0 = 2

The Nothing type, as you saw earlier, 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

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

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.

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

To simulate a typical use case of the previous type, enter 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 the 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 isn’t 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 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 need to translate the semantic of Callback<Data, Result, Error> into an algebraic expression. Then, apply some 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 earlier.

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 the case of success.
2. In the case of an error, the same Response but with an ErrorInfo.

More important than what you can do is what you can’t do. You can’t 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, as you saw earlier in this chapter about isomorphism.

Another way to say this is 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

Becomes:

A + Nothing = A = Nothing + A

This represents a type you can write as:

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

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

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 the Either<A, Unit> type has all the possible values of A plus a single value that is Unit. This is something you could represent like this:

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

Do you recognize it? This is basically the Optional<T> type you learned about in Chapter 9, “Data Types”. You have a value of type A, or you have another single and unique value, which is None here, but could also be Unit.

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 with 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 to associate a Boolean value with a value of the Triage type.

This perfectly describes the (Triage) -> Boolean function type. 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. Think of A ^ B as equivalent to a function from B to A. You can then assert that:

A ^ B = (B) -> A

The consequences of this are surprising.

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.

In the previous section, you learned that exponential A ^ B can be translated in a function from B to A of type (B) -> A or Fun<B, A>. One of the most important properties of exponents is the following:

(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’ve already learned 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 with 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 exactly what you’d call currying. Here’s what you’ll find in Curry.kt in the material for this chapter:

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

This proves the equivalence between the two function types.

Nothing and exponents

As you may know, in math:

A ^ 0 = 1

Using the type analogy, now write:

A ^ Nothing = Unit

Which means:

(Nothing) -> A = Unit

In this case, the tricky thing is that = means isomorphism. So how can you read the previous definition? In Chapter 2, “Function Fundamentals”, you saw a function of type Fun<Nothing, A>, which you called the “absurd function” because you can’t invoke it. To invoke that function, you need a value of type Nothing, which doesn’t exist. Because you can never invoke that function, all the functions of that type are the same. They all have the same meaning, and they all produce — or better, never produce — the same result.

Another way to say that all those functions are the same is: If you take one of those, all the others are equivalent. You can represent all of them with just one, and a way to represent a singleton is with Unit.

Powers and 1

Keep having fun with the following equivalence:

1 ^ A = 1

Whatever the exponent is for 1, you always get 1. Using equivalence with types, you can say that:

(A) -> Unit = Unit

This means there’s only one function from a type A to Unit. It’s a way to reinforce the definition of a terminal object that states there’s a unique morphism from any object to it.

Now, consider this:

A ^ 1 = A

Which translates to:

(Unit) -> A = A

This is another way to define the unit function you also learned about in Chapter 2, “Function Fundamentals”.

Exponentials and addition

Another important property for exponents is:

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

Which translates to:

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

This basically means that a function accepting a value of type B or C to produce a value of type A is isomorphic with a couple of functions — the first from B to A and the second from C to 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()

This is a simple sealed class, which represents all 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 of Either<A, B>:

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. Now, consider the List<A> data type. Using the same reasoning, think of it as something you can define by entering the following code into List.kt:

sealed interface FList<out A>
object Nil : FList<Nothing>
data class FCons<A>(
  val head: A,
  val tail: FList<A> = Nil
) : FList<A>

Does it ring a bell? You used this in Chapter 7, “Functional Data Structures”. This means that a FList<A> can be empty, or you can think of it as a head and tail, which may or may not be empty. You can then create a list of five values in the following way and add it to List.kt:

val countList =
  FCons(1, FCons(2, FCons(3, FCons(4, FCons(5, Nil)))))

An immutable characteristic of math is that it always makes all the pieces work together.

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()
}

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

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

And you get:

15

So far, so good. 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 Nil (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 FList<A> as a possible combination of all the possible FList<A>s 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.

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.