9. Data Types

Written by Massimo Carli

In the first section of the book, you learned about the concept of type. In particular, you learned that a type for a variable is a way to represent the set of possible values you can assign to it. For instance, saying that a is an Int means you can assign only integer values to a. The same is true for more complex types like String or custom types like User and so on.

In this chapter, you’ll meet data types, another crucial concept that’s somewhat orthogonal to the concept of type. For instance, the Optional<T> data type is a classic example. It represents the concept of either having an object of type T or not, and doesn’t depend on what T actually is.

In particular, you’ll learn:

• What a data type is.
• How to define the Optional<T> data type.
• The Optional<T> type in the context of data types.
• What lift , map and flatMap functions are.
• The common and important data types List<T> and Either<A, B>.
• What the fold and foldRight functions are and why they’re useful.

As always, you’ll learn all this using the Kotlin language and some fun exercises and challenges.

What is a data type?

In the first section of the book, you learned the crucial definition of a type. You saw that a type is basically a way to represent a set of values you can assign to a variable or, in general, use in your program. Consider, for instance, the following code:

var a: Int = 10
var s: String = "Hello World!"
var b = true

Here, you can say that:

1. a is a variable of type Int. This means you can assign only integer values to a.
2. s is of type String, and you can assign any possible String you can create in Kotlin.
3. You can assign to the Boolean variable b only a value of either true or false.

A type doesn’t just tell you what value you can assign but also what you can’t. In the previous code, you can’t assign true to a, for instance.

You also learned that types and functions together make a category, which is the pillar of composition.

A data type is a different concept that uses the previous types as type parameters. In general, you represent them as M<T> in the case of a single type parameter. Other data types have multiple parameters. For example, you represent a data type with two type parameters as M<A, B>.

As you’ll see, you can think of a data type as a container that provides some common functions so you can interact with its content. The best way to understand data types is by providing some examples, starting with a classic: Optional<T>.

The Optional<T> data type

As mentioned earlier, you can often think of a data type as a container that provides some context. Optional<T> is a classic example because it represents a container that can either:

• Contain a single element of type T.
• Be empty.

Open Optional.kt and write this code:

sealed class Optional<out T> { // 1

  companion object {
    @JvmStatic
    fun <T> lift(value: T): Optional<T> = Some(value) // 4

    @JvmStatic
    fun <T> empty(): Optional<T> = None // 5
  }
}

object None : Optional<Nothing>() // 2
data class Some<T>(val value: T) : Optional<T>() // 3

In this code, you:

1. Define Optional<T> as a sealed class. Note that it has a type parameter T, and it’s covariant.
2. Define None as an object representing the case when the container is empty. All empty containers are the same, and you need the type parameter to be covariant, so you inherit from Optional<Nothing>.
3. Define Some<T> as a data class with a single property of type T.
4. Use some factory methods to get an object of type Some<T> as an Optional<T>. The first method is lift, which allows you to get Optional<T> from a given value of type T.
5. Do the same for None with empty().

Note: If you need a reminder about covariance, look back at Chapter 4, “Expression Evaluation, Laziness & More About Functions”.

But how can you use the Optional<T> data type? A simple test can help.

Using Optional<T>

In OptionalTest.kt, add the following code:

fun strToInt(value: String): Optional<Int> = // 1
  try {
    Optional.lift(value.toInt()) // 2
  } catch (nfe: NumberFormatException) {
    Optional.empty() // 3
  }

fun double(value: Int): Int = value * 2 // 4

In this code, you:

1. Create strToInt as a function that accepts a String and wants to return the Int value in it. This operation can fail, so the return type is an Optional<Int>.
2. Return Some<Int> with the Int value in case of success.
3. Return None in case of error.
4. Define double as a simple function from Int to Int.

Now, how would you implement code that doubles the value you get from strToInt? A first solution is the following:

fun main() {
  val res = strToInt("10") // 1
  when (res) {
    is Some<Int> -> { // 2
      val res2 = double(res.value)
      println("Result is $res2")
    }
    is None -> println("Error!") // 3
  }
}

In this code, you:

1. Invoke strToInt, passing a valid String, getting an Optional<Int> returned, which you store in res.
2. Check the result and, if it’s a Some<Int>, you pass the value to double and print the result.
3. Print an error message in case of error.

Run the code, and you get:

Result is 20

To test the error, just pass a value to strToInt that isn’t a valid Int, like:

val res = strToInt("10aaa")

Running this code, you get:

Error!

The previous code isn’t the best, though. You invoke strToInt and then use a verbose when expression to understand what to do next. Of course, you can do better.

Using lift, map and flatMap

In the previous example, you have strToInt, which is a function of type (String) -> Optional<T>. You want to compose this with double of type (Int) -> Int. Of course, you can’t, because double accepts an Int and strToInt provides an Optional<Int>. To solve this problem, you have two main options. The first is:

1. Use strToInt to get an Optional<Int>.
2. Check if it’s a Some<Int> and get the Int in it.
3. Pass the Int to double.

The second — and better — option is:

1. Lift String to an Optional<String>.
2. Apply a transformation to the Optional<String>, getting an Optional<Int>.
3. Apply the double transformation to Optional<Int>, getting another Optional<Int>.
4. Extract the contents of Optional<Int>, or a default value if it’s missing.

The first option is the one you already implemented in the previous paragraph. It’s time to implement the second, then. You call the first step lift because you’re basically taking a value of type T and “lifting” it to an object of type M<T>. In this case, M represents the Optional data type, but you’ll also find the lift function in other data types.

Figure 9.1 describes what you’ll implement:

In the same OptionalTest.kt file, replace the previous main with the following. A keen eye might note that it won’t compile yet:

fun main() {
  // ...
  Optional
    .lift("10")
    .flatMap(::strToInt) // 1
    .map(::double) // 2
    .getOrDefault(-1) // 3
    .pipe(::println)
}

Note: You’ll find the pipe definition you learned in Chapter 8, “Composition” in Definitions.kt in the material for this project.

At the moment, this code doesn’t compile because you need to implement:

1. flatMap
2. map
3. getOrDefault

You’ll learn all about map and flatMap in Chapter 11, “Functors” and Chapter 13, “Understanding Monads”, respectively. At the moment, it’s important to have an idea of how they work to make the previous code compile.

Implementing map

Starting with the map function, you see that it receives a function of type Fun<A, B> as input and returns an Optional<B>. Remember that:

typealias Fun<A, B> = (A) -> B

To better understand how it works, add the following code in Optional.kt:

fun <A, B> Optional<A>.map(fn: Fun<A, B>): Optional<B> = // 1
  when (this) {
    is None -> Optional.empty() // 2
    is Some<A> -> Optional.lift(fn(value)) // 3
  }

In this code, you:

1. Define map as an extension function for Optional<A>. Note how it accepts a function of type Fun<A, B> and returns an Optional<B>.
2. Check if the receiver is None. If it is, the result is also None. Note how you use Optional.empty(), which allows you to return an Optional<B> by type inference.
3. Use lift to return Some<B>, passing the result of the invocation of the function fn.

One function down. Next is flatMap.

Implementing flatMap

While double is a Fun<Int, Int>, strToInt has type Fun<Int, Optional<Int>>, making it incompatible with map. You need something more. Add this code to Optional.kt:

fun <A, B> Optional<A>.flatMap(
  fn: Fun<A, Optional<B>>
): Optional<B> = when (this) { // 1
  is None -> Optional.empty() // 2
  is Some<A> -> {
    val res = fn(value) // 3
    when (res) {
      is None -> Optional.empty() // 4
      is Some<B> -> Optional.lift(res.value) // 5
    }
  }
}

This code is a little more complex. Here:

1. You define flatMap as an extension function of Optional<A>. Note how it accepts a parameter of type Fun<A, Optional<B>> and returns an Optional<B>.
2. You check if the receiver is None. In this case, you just return Optional.empty().
3. Otherwise, invoke fn on the value in Some<B> and check its result.
4. If it’s None, you return Optional.empty().
5. If it’s Some<B>, you return a new Optional<B>, using the same result and the lift function.

Note how even though fn already returns Optional<B>, you’re still wrapping the result in a new Optional<B> instance. This is because every function should return a new immutable object.

Great! One more function to go before you can compile your code.

Implementing getOrDefault

To ensure the previous code compiles, you also need to add getOrDefault to Optional.kt:

fun <A> Optional<A>.getOrDefault(defaultValue: A): A =
  when (this) { // 1
    is None -> defaultValue // 2
    is Some<A> -> value // 3
  }

In this code, you:

1. Define getOrDefault as an extension function for the Optional<A> type. Note how it accepts a value of type A.
2. Check the current receiver and return defaultValue if it’s None.
3. Return value if the receiver is Some<A>.

Now, the previous code in OptionalTest.kt compiles. Run it, and you get:

20

To check the case with the default value, replace the previous main with the following:

  Optional
    .lift("10aa")
    .flatMap(::strToInt)
    .map(::double)
    .getOrDefault(-1)
    .pipe(::println)

Run it, and you get:

-1

A quick review

In the previous section, you met three of the most critical concepts in functional programming. You’ll learn more about them in the following chapters. In particular, you learned:

• What a data type is and in what sense it behaves as a container.
• How to interact with the content of the container the data type represents using map. You’ll learn all about functors in Chapter 11, “Functors”. For now, it’s important to understand that invoking map on a data type M<A> passing a function of type Fun<A, B> as a parameter, you’ll get M<B>.
• How to interact with the content of a data type M<A> using a function of type Fun<A, M<B>>. In this case, map doesn’t work. Instead, you need a function called flatMap. You’ll learn all about flatMap in Chapter 13, “Understanding Monads”. So far, you just need to understand that invoking flatMap on a data type M<A> passing a function of type Fun<A, M<B>> as a parameter, you’ll get M<B>.

Now, it’s time to learn the most common and important data types while implementing for them lift, map, flatMap and the equivalent of getOrDefault.

But first, here are some exercises to test your new knowledge! You can find solutions in Appendix I and the challenge matterials for this chapter.

Exercise 9.1: In this chapter, you learned what the Optional<T> data type is, and you implemented some important functions for it, like lift, empty, map and flatMap. Kotlin defines its own optional type represented by ?. How would you implement the lift, empty and getOrDefault functions for it?

Exercise 9.2: In this chapter, you learned what the Optional<T> data type is, and you implemented some important functions for it, like lift, empty, map and flatMap. Kotlin defines its own optional type represented by ?. How would you implement the map and flatMap functions for it?

Exercise 9.3: How would you replicate the example you implemented in OptionalTest.kt using T? instead of Optional<T>? Use the solutions of Exercise 9.1 and Exercise 9.2 to implement this example.

The List<T> data type

So far, you’ve learned that you can think of a data type as a container with a specific context. The context of an Optional<T> is about something that can be there or not. Another fundamental data type is List<T>. In this case, the context is the ability to contain an ordered list of items. It’s important to say that Kotlin already provides the functions you implemented for Optional<T> and T?.

Open ListTest.kt and add the following code:

fun countUpTo(value: Int) = List(value) { it } // 1

fun main() {
  val emptyList = emptyList<Int>() // 2
  val intList = listOf(1, 2, 3) // 3
  intList.map(::double).forEach(::println) // 4
  println("---")
  intList.flatMap(::countUpTo).forEach(::println) // 5
}

In this code, you have examples of:

1. Defining countUpTo, which is a function of type Fun<Int, List<Int>>. countUpTo just generates a List<Int> with values from 0 to the value you pass in input. It doesn’t really matter what this function does; the type of countUpTo is what matters.

2. Creating an empty List<Int> using the emptyList builder function.

3. Using listOf to create a List<Int>.

4. Using map to apply the double function to all the elements of a List<Int>. Note that you invoke the map function on List<Int>, and you get another List<Int>.

5. Using flatMap, passing the reference to countUpTo.

When you run that code, you get:

2 // 1
4
6
---
0 // 2
0
1
0
1
2

As you can see:

1. map returns a new List<Int> that contains values that are the double of the values of the original list.
2. flatMap returns a List<Int> of the List<Int> you get applying countUpTo to each element. The flat in the name also gives the idea that you don’t get a List<List<Int>>, but the values of the list you get from countUpTo are flattened in a single List<Int>.

Folding

List<T> has a couple of magic functions that are very important and useful in the implementation of other functions. To see why, open Folding.kt and add the following code:

fun List<Int>.imperativeSum(): Int {
  var sum = 0
  for (i in 0 until size) {
    sum += this[i]
  }
  return sum
}

Note: In Chapter 12, “Monoids & Semigroups”, you’ll learn even more about the fold functions.

At this point, you’re probably disappointed because this function calculates the sum of all the values in a List<Int> using an imperative approach. In Chapter 5, “Higher-Order Functions”, you learned how to use a declarative approach, and in Chapter 6, “Immutability & Recursion”, you learned how to use recursion to achieve immutability. In any case, the previous code teaches you that you basically accumulate the different values of the list in a sum variable. You can also use that in your tests to check if other implementations are correct. Run this code:

fun main() {
  val list = listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
  list.imperativeSum() pipe ::println
}

And you get the following output, which is the sum of the first ten positive integers.

55

Note: If you want to have some fun, you can use the following expression as an alternative way of printing the result of imperativeSum.

 List<Int>::imperativeSum compose ::println epip list

You already have pipe, epip and compose in the Composition.kt and Definitions.kt files in the material for this chapter.

With all this in mind, add the following code:

fun List<Int>.declarativeSum(): Int {
  tailrec fun helper(pos: Int, acc: Int): Int {
    if (pos == size) {
      return acc
    }
    return helper(pos + 1, this[pos] + acc)
  }
  return helper(0, 0)
}

You’re basically doing the same as the imperative approach but using helper as a tailrec function receiving as input the index pos of the current value in the list and acc as the current sum. In this case, there’s no mutation, and the approach is declarative. Test declarativeSum by running this code:

val list = listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
list.declarativeSum() pipe ::println

And getting the same result:

55

So far, so good. But this code works only for Ints. You can do much better. To understand how, add the following code for a function that calculates the product of the values in a List<Int>:

fun List<Int>.declarativeProduct(): Int {
  tailrec fun helper(pos: Int, acc: Int): Int {
    if (pos == size) {
      return acc
    }
    return helper(pos + 1, this[pos] * acc)
  }
  return helper(0, 1)
}

Run:

val list = listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
list.declarativeProduct() pipe ::println

And you get:

3628800

Note that declarativeProduct follows the same pattern as declarativeSum with some crucial differences:

1. Of course, declarativeSum calculates the sum and declarativeProduct the product. More importantly, they differ in the way you accumulate all the elements into a sort of… accumulator, acc. In declarativeSum, you add the current value to acc. In declarativeProduct, you multiply the current value by acc.
2. In declarativeSum, the initial value for the accumulator is 0. In declarativeProduct, the initial value is 1.

From the previous observations, you entail that you can represent declarativeProduct and declarativeSum using a common abstraction accepting as input something that tells where one differs from the other. In this case:

1. The initial value for the accumulator.
2. How you combine each element with the current value you’ve accumulated.

In the same Folding.kt file, add the following code:

fun <T, S> List<T>.declarativeFold(
  start: S,
  combineFunc: (S, T) -> S
): S { // 1
  tailrec fun helper(pos: Int, acc: S): S { // 2
    if (pos == size) {
      return acc
    }
    return helper(pos + 1, combineFunc(acc, this[pos])) // 3
  }
  return helper(0, start) // 4
}

In this code, you:

1. Define declarativeFold as an extension function of List<T>, which accepts as an input parameter an initial value of type S for the accumulator and a function of type (S, T) -> S that tells how you combine an element with the accumulator itself. Note how the return type is S, which is the type of the accumulator.
2. Implement a helper function with two input parameters. The first is the position pos of the current element you’re evaluating. The second is the current value acc for the accumulator. If you reach the end of the list, you return the current value for the accumulator, acc. Note how helper is a tailrec function.
3. Call helper recursively for the next position, pos + 1, if you’re not at the end of List<T>. Note how the value for the accumulator is what you get by invoking combineFunc with the current acc value and the current element.
4. Invoke helper from the first position, 0, and the initial value, start.

With this function, you can run the following code:

list.declarativeFold(0) { acc, item ->
  acc + item
} pipe ::println
list.declarativeFold(1) { acc, item ->
  acc * item
} pipe ::println

Getting the output you’d expect:

55
3628800

In this case, you invoke the same declarativeFold function, passing:

1. 0 as initial value { acc, item -> acc + item} as a combine function for the sum.
2. 1 as initial value { acc, item -> acc * item} as a combine function for the product.

As mentioned at the beginning of this section, you’ll see how powerful this function is. Before proceeding, it’s also important to say that List<T> already has a fold function with the same signature as declarativeFold, which you created with a different name to avoid conflicts.

This means you can use the existing fold like in this code:

val list = listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
list.fold(0) { acc, item -> acc + item } pipe ::println
list.fold(1) { acc, item -> acc * item } pipe ::println

Getting exactly the same result:

55
3628800

The Kotlin List<T> also provides a foldRight method, which differs in how the combination happens. It’s very important to look at this function as well.

Folding right

Imagine you have a list of objects, and you want to group them together. To do this, you have two different options. You can:

• Start from the first element and accumulate the other objects as soon as you iterate over them.
• Start from the first element and, because you have others, put that object aside and go to the next one. You repeat this operation until you get the last object. Then, you start to take the most recent object you put aside and combine it with the one you have in your hands. You repeat this operation until you combine the object you put aside first.

Some code can probably help. Consider the following code you wrote earlier, using a shorter list to save some space.

val list = listOf(1, 2, 3, 4, 5)
list.declarativeFold(0) { acc, item -> acc + item } pipe ::println

In this code, you use declarativeFold to calculate the sum of the first 5 integers you previously put into a List<Int>. It’s useful to see what happens when you run this code:

(1,2,3,4,5).declarativeFold(0)
helper(0, 0) // 1
  helper(1, combineFunc(0, 1))  // 2
    helper(2, combineFunc(1, 2))  // 2
      helper(3, combineFunc(3, 3)) // 2
        helper(4, combineFunc(6, 4)) // 2
          helper(5, combineFunc(10, 5)) // 2
           15  // 3
        15
      15      
    15
  15
15

You can see that:

1. Initially, you invoke helper(0, 0) because you start from the index, 0, and the initial value is 0.
2. When you’re not at the end of the List<Int>, you invoke helper again, passing the new position, pos + 1, as the next to evaluate and the new value for the sum you’re accumulating. To get this, you need to invoke combineFunc, passing the current value of acc and the current element in the List<Int>. You do this until you reach the end of the List<Int>. Because you’re returning the result of the same helper, this is a tailrec function.
3. At the end of the list, you return the value of acc.

It’s also useful to see how the values in the list are actually aggregated:

combineFunc(combineFunc(combineFunc(combineFunc(combineFunc(0, 1), 2), 3), 4), 5)

Replacing the combineFunc invocation with +, as an example, you get:

(((((0 + 1) + 2) + 3) + 4) + 5)

Note how you’re accumulating values on the left, taking one new item at a time from the right. This is why the declarativeFold you implemented is also called foldLeft.

However, that’s not the only way to implement this. In the same Folding.kt file, add this code:

fun <T, S> List<T>.declarativeFoldRight(
  start: S,
  combineFunc: (T, S) -> S
): S { // 1
  fun helper(pos: Int): S { // 2
    if (pos == size) { // 3
      return start
    }
    return combineFunc(this[pos], helper(pos + 1)) // 4
  }
  return helper(0)
}

In this case:

1. You define declarativeFoldRight as an extension function of List<T>. Note how the first parameter is the same initial value for the accumulator as for declarativeFold. However, the second parameter, combineFunc, differs because now the type S is the second parameter. This helps you to visualize the folding by keeping what you accumulate on the right.
2. The helper function now has a single parameter: the position, pos, of the current item.
3. When the recursion reaches the end of the list, you return the initial value, start.
4. If you’re not at the end of the list, you return the result of the invocation of combineFunc, passing the current item as the first parameter and the result of the recursive invocation of helper for the following item.

Here’s also a visual representation of what’s happening in this case:

Note: Here, combineFunc is replaced with comb to save some space!

(1,2,3,4,5).declarativeFoldRight(0)
  helper(0)
    comb(1, helper(2))  
      comb(1, comb(2, helper(3)))
        comb(1, comb(2, comb(3, helper(4))))
          comb(1, comb(2, comb(3, comb(4, helper(5)))))
            comb(1, comb(2, comb(3, comb(4, comb(5, helper(6))))))
            comb(1, comb(2, comb(3, comb(4, comb(5, 0)))))
          comb(1, comb(2, comb(3, comb(4, 5))))
        comb(1, comb(2, comb(3, 9)))
      comb(1, comb(2, 12))
    comb(1, 14)
  15  
15

Using + again in place of the combineFunc invocation, you have:

(1 + (2 + (3 + (4 + (5 + 0)))))

Here, note two main things:

1. The recursive nature of the invocations isn’t tailrec because the invocation of helper isn’t the last operation.
2. You start combining from the last element and keep adding while returning from the invocation stack.

Run this code:

val list = listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
list.foldRight(0) { item, acc -> acc + item } pipe ::println
list.foldRight(1) { item, acc -> acc * item } pipe ::println

And you get the same result you got previously:

55
3628800

Note: Notice that acc is the second param in the lambda you use as combineFunc. This is for consistency with the Kotlin foldRight function.

This is true because addition and multiplication are symmetrical, so a + b = b + a and a * b = b * a. To see the difference, you just need to use a non-symmetric function like String concatenation. Run this code:

val list = listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
list.map(Int::toString).declarativeFold("") { acc, item ->
  acc + item
} pipe ::println
list.map(Int::toString).fold("") { acc, item ->
  acc + item
} pipe ::println
list.map(Int::toString).declarativeFoldRight("") { item, acc ->
  acc + item
} pipe ::println
list.map(Int::toString).foldRight("") { item, acc ->
  acc + item
} pipe ::println

And see that the results are different when using declarativeFold and declarativeFoldRight or the existing Kotlin implementations:

12345678910
12345678910
10987654321
10987654321

Here, you can see that using declarativeFold or fold produces a different result than declarativeFoldRight or foldRight.

Exercise 9.4: Implement a function that reverses a String using one of the folding functions you’ve implemented in this chapter.

Exercise 9.5: In this chapter, you implemented declarativeFold and declarativeFoldRight as extension functions for List<T>. How would you implement them for Iterable<T>?

What about FList<T>?

In Chapter 7, “Functional Data Structures”, you implemented FList<T> — whose code is available in FList.kt in this chapter’s material — as an example of a functional data structure. The existing of is equivalent to the lift function you learned here. It basically “lifts” the values you pass as a vararg to an FList<T>. Also, empty already provides the empty FList<T>. But what about fold, foldRight, map and flatMap?

Note: Implementing all these functions for FList<T> is a great exercise. Feel free to try it out on your own, skip this section or come back to it later if you want and go straight to learning about the Either<A, B> data type. In any case, see you there!

Implementing fold and foldRight

In the previous section, you learned what fold and foldRight are, but you didn’t have any proof of how important these functions are. As a first step, you’ll implement fold and foldRight for FList<T>. Open FListExt.kt and add the following code:

tailrec fun <T, S> FList<T>.fold(
  start: S,
  combineFunc: (S, T) -> S
): S = when (this) { // 1
  is Nil -> start // 2
  is FCons<T> -> {
    tail.fold(combineFunc(start, head), combineFunc) // 3
  }
}

In this code:

1. You define fold as an extension function of FList<T>. It accepts an initial value of type S and a combineFunc of type (S, T) -> S.

2. You use the same pattern you learned in Chapter 7, “Functional Data Structures”. Here, you test if the current receiver is Nil. If it is, you just return the initial value, start.

3. Otherwise, you’re combining head with the start value. It’s important to see that you’re using this combined value as the new starting value when invoking fold again on the tail. The fold invocation on tail makes this function tailrec.

Test the previous implementation by running the following code:

fun main() {
  val numbers = FList.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
  numbers.fold(0) { acc, item -> acc + item } pipe ::println
  numbers.fold(1) { acc, item -> acc * item } pipe ::println
}

You get exactly what you got previously with a List<Int>.

55
3628800

In the same FListExt.kt file, now add this code:

fun <T, S> FList<T>.foldRight(
  start: S,
  combineFunc: (T, S) -> S
): S = when (this) {
  is Nil -> start
  is FCons<T> -> {
    combineFunc(head, tail.foldRight(start, combineFunc))
  }
}

In this code, note that foldRight isn’t tailrec anymore, similar to its List<T> counterpart. This is because you return the result of combineFunc.

Test it again by adding this code to main and running it:

FList.of(
  *("supercalifragilisticexpialidocious"
    .toCharArray().toTypedArray())
)
  .foldRight(StringBuilder()) { item, acc ->
    acc.append(item)
    acc
  } pipe ::println

Besides the magic of converting a String into an Array<Char>, you’re using foldRight on the String itself. The output is:

suoicodilaipxecitsiligarfilacrepus

Implementing map

map is one of the most crucial functions, and you’ll meet it many times when implementing your code. Its implementation is very simple. In FListExt.kt, add the following code:

fun <T, S> FList<T>.map(fn: Fun<T, S>): FList<S> = // 1
  when (this) {
    is Nil -> FList.empty() // 2
    is FCons<T> -> FCons(fn(head), tail.map(fn)) // 3
  }

This code follows most of the patterns you’ve seen in the previous examples. Here:

1. You define map as an extension function of FList<T>. It accepts a function of type Fun<T, S> and returns an FList<S>.
2. You return Nil if the current receiver is Nil.
3. If the current receiver isn’t Nil, it means it has a head of type T. In this case, you return a new FList<S> where the head is the value of type S you get from fn(head) and the tail is what you get by invoking map on it.

To test map, run the following code:

FList.of(1, 2, 3, 4, 5)
  .map(::double)
  .forEach(::println)

And the output is:

2
4
6
8
10

Implementing flatMap

flatMap is probably the most challenging function to implement. It’s also part of the proof that fold and foldRight should be fundamental elements of your functional programming skills.

To implement the actual flatMap, you need another function. In FListExt.kt, add the following code:

fun <T> FList<T>.append(rhs: FList<T>): FList<T> =
  foldRight(rhs, { item, acc -> FCons(item, acc) })

As the name says, this appends an FList<T> to another you have as the receiver. This is another example of the use of the magic foldRight. Here, you:

• Start with the FList<T> you want to append as the initial value.
• Then, iterate over the elements in the receiver FList<T>, adding it as head every time.

Run this code in main to test how append works:

val first = FList.of(1, 2, 3)
val second = FList.of(4, 5, 6)
first
  .append(second)
  .forEach(::println)

You get:

1
2
3
4
5
6

Finally, in the same file, add the following code:

fun <T, S> FList<T>.flatMap(
  fn: Fun<T, FList<S>>
): FList<S> = foldRight(
  FList.empty() // 1
) { item, acc ->
  fn(item).append(acc) // 2
}

Here’s another use of foldRight. In this code, you:

1. Start with the empty FList<S>.
2. Invoke fn on each item in the receiver, FList<T>, getting an FList<S>. The value you return is the FList<S> you get by appending the previous accumulator.

To test this code, run the equivalent example you met earlier with List<T>. First, add this function:

fun countUpToFList(value: Int) = FList.of(*Array(value) { it })

Here, you define countUpToFList as a simple function that, given a value, returns an FList<Int> from 1 to the value itself. Note that you’re using the spread (*) operator to pass in an Array for varargs.

Then, use countUpToFList to test your flatMap in main:

val intList = FList.of(1, 2, 3)
intList.flatMap(::countUpToFList).forEach(::println)

This is similar to what you’ve done in previous chapters.

When you run this code, you get:

0
0
1
0
1
2

The Either<A, B> data type

Optional<T>, List<T> and FList<T> are examples of data types with a single type parameter. Life isn’t always so simple, however, and sometimes you need something more.

While Optional<T> represents a kind of container that can either be empty or contain an object of type T, there might be a case when the container is never empty and contains a value of type A or a value of type B. For instance, black or white, true or false, 1 or 0 or, more philosophically, right or wrong. This data type is Either<A, B>.

Open Either.kt, and add the following code:

sealed class Either<out A, out B> { // 1

  companion object {
    @JvmStatic
    fun <A> left(left: A): Either<A, Nothing> = Left(left) // 4

    @JvmStatic
    fun <B> right(right: B): Either<Nothing, B> = Right(right) // 4
  }
}

data class Left<A>(val left: A) : Either<A, Nothing>() // 2
data class Right<B>(val right: B) : Either<Nothing, B>() // 3

In this code, you define:

1. Either<A, B> as a sealed class in the type parameters A and B. Note how Either<A, B> is covariant for both A and B.
2. Left<A> as a data class containing a value of type A.
3. Right<B> as a data class containing a value of type B.
4. The builders left and right, which return a Left<B> and a Right<A>, respectively, as objects of the abstract type Either<A, B>.

The use of a sealed class guarantees that an Either<A, B> can only be an object Left<A> or Right<B>. But when would this be useful? As mentioned earlier, a classic example deals with error handling. In this scenario, the name of the possible values gives a hint. Right<A> is successful, and Left<B> represents something wrong.

Open EitherTest.kt, and add the following code:

fun strToIntEither(
  str: String
): Either<NumberFormatException, Int> = try {
  Either.right(str.toInt())
} catch (nfe: NumberFormatException) {
  Either.left(nfe)
}

This is another version of the strToInt function that converts a String to the Int it contains. As you know, this can fail and throw a NumberFormatException. This would make the function impure because an exception is a side effect.

In the previous chapters, you learned that you can make a function pure by moving the side effect as part of the return value. This is what’s happening here. The only difference now is that the return value is an Either<NumberFormatException, Int>. In the case of success, strToIntEither returns Right<Int>. In the case of failure, it returns Left<NumberFormatException>.

The question now is: How do you interact with this value? The good news is that you already know the answer. Either<A, B> is a container with an object of type A or B in it. Every container should provide functions that allow you to interact with the content. The most important functions are still map and flatMap. Of course, their meaning is slightly different in the context of Either<A, B>. You can start simple, with map.

Implementing map

The most important and — fortunately — the easiest functionality to implement is map. But how can you provide a function of type Fun<A, B> if you don’t even know if Either<A, B> is Left<A> or Right<B>? The answer is very simple: You provide two. Add the following code to Either.kt:

fun <A, B, C, D> Either<A, B>.bimap(
  fl: (A) -> C,
  fr: (B) -> D
): Either<C, D> = when (this) {
  is Left<A> -> Either.left(fl(left))
  is Right<B> -> Either.right(fr(right))
}

As you see, bimap accepts two functions as input parameters. The first, fl, is the function of type Fun<A, C> — you apply this to the value of type A if Either<A, B> is Left<A>. fr, however, is a function of type Fun<B,C> — you apply this if Either<A, B> is Right<B>.

Note: In Chapter 11, “Functors”, you’ll learn that a data type providing a function like bimap is a bifunctor.

Sometimes, you don’t want to provide two functions. For this reason, Either<A, B> should also provide two different map functions.

To see how, just add the following code in the same Either.kt file:

fun <A, B, C> Either<A, B>.leftMap(
  fl: (A) -> C
): Either<C, B> = when (this) {
  is Left<A> -> Either.left(fl(left)) // 1
  is Right<B> -> this // 2
}

fun <A, B, D> Either<A, B>.rightMap(
  fr: (B) -> D
): Either<A, D> = when (this) {
  is Right<B> -> Either.right(fr(right)) // 3
  is Left<A> -> this // 4
}

In this case:

1. leftMap applies the function of type Fun<A, C> to the value in Left<A>.
2. You return the receiver itself if the receiver is Right<B>.
3. rightMap applies the function of type Fun<B, D> to the value in Right<A>.
4. You return the receiver itself if the receiver is Left<A>.

Before showing an example using these, it’s helpful to see some accessor methods.

Implementing accessors

If you think of every data type as a container, it’s often useful to define a function to get their content, like the getOrDefault function you met earlier. In this case, you can use different approaches. In Scala, for instance, the Either<A, B> type provides a getOrDefault only for the Right<B> value.

If you decide to do the same, you can add the following code to the same Either.kt file:

fun <A, B> Either<A, B>.getOrDefault(
  defaultValue: B
): B = when (this) {
  is Left<A> -> defaultValue
  is Right<B> -> right
}

This function returns defaultValue if it’s Left<A> and the right value if it’s Right<B>.

Nothing prevents you from implementing a specific function for Left<A> and Right<B>, like these you can add to the same file:

fun <A, B> Either<A, B>.getRightOrDefault(
  defaultValue: B
): B = when (this) {
  is Left<A> -> defaultValue
  is Right<B> -> right
}

fun <A, B> Either<A, B>.getLeftOrDefault(
  defaultValue: A
): A = when (this) {
  is Left<A> -> left
  is Right<B> -> defaultValue
}

Defining a flip function that swaps the two types, like this, is also interesting:

fun <A, B> Either<A, B>.flip(): Either<B, A> = when (this) {
  is Left<A> -> Either.right(left)
  is Right<B> -> Either.left(right)
}

This allows you to use getOrDefault after flip to access the value for Left<A>. A lot of fun!

These functions allow you to run an example of the use for bimap, mapLeft and mapRight. Open EitherTest.kt and add the following code:

fun main() {
  val squareValue = { a: Int -> a * a }
  val formatError = { ex: Exception ->
    "Error ${ex.localizedMessage}"
  }
  strToIntEither("10").bimap(formatError, squareValue) // 1
    .getOrDefault(-1).pipe(::println)
  strToIntEither("10").bimap(formatError, squareValue) // 2
    .flip().getOrDefault("No Error!")
    .pipe(::println)
  strToIntEither("10").rightMap(squareValue) // 3
    .getOrDefault(-1).pipe(::println)
  strToIntEither("10aaa").leftMap(formatError) // 4
    .getOrDefault("Generic Error").pipe(::println)
}

You can try different combinations, but here you have examples of using:

1. bimap passing formatError to format the error message in the case of the Left<A> value, and squareValue to square the value in the case of Right<B>.
2. bimap with the same formatError and squareValue functions, but using flip to get the value in the case of Left<A>.
3. rightMap to square the value only in the case of Right<B>.
4. leftMap to format the error message only in the case of Left<A>.

Implementing flatMap

As mentioned earlier, Either<A, B> is usually right-biased. This means you usually find functions like map and flatMap applicable to the Right<B> side of it, which usually represents success. Left<A> usually represents failure, and there’s not normally too much to do in this case. For this reason, you’ll implement flatMap for the Right<B> side. In Either.kt, add the following code:

fun <A, B, D> Either<A, B>.flatMap(
  fn: (B) -> Either<A, D>
): Either<A, D> = when (this) { // 1
  is Left<A> -> Either.left(left) // 2
  is Right<B> -> {
    val result = fn(right) // 3
    when (result) {
      is Left<A> -> Either.left(result.left) // 4
      is Right<D> -> Either.right(result.right) // 5
    }
  }
}

In this case, you:

1. Define flatMap as an extension function for Either<A, B>. Note how the function fn you pass in as a parameter has type (B) -> Either<A, D>, which means the type for Left<A> doesn’t change. In Chapter 12, “Monoids & Semigroups”, you’ll see much more about this. Finally, the return type is Either<A, D>.

2. Return a Left<A> if the receiver is already of that type.

3. Invoke fn in the right value if the receiver is a Right<B>, getting an Either<A, D>.

4. Return a Left<A> if you get a Left<A> as a result of fn.

5. Finally, return a new Right<D>, using the value of the same type you get from fn.

As a simple example, add the following code to EitherTest.kt:

fun main() {
  val squareValue = { a: Int -> a * a }

  strToIntEither("10")
    .rightMap(squareValue)
    .rightMap(Int::toString)
    .flatMap(::strToIntEither) // HERE
    .getOrDefault(-1)
    .pipe(::println)
}

Running the previous code, you get:

100

Using Either<A, B> in a failure/success scenario is very common, and for this reason, Kotlin provides the Result<T> data type, which you’ll learn about in Chapter 14, “Error Handling With Functional Programming”.

Challenges

You’ve already done some interesting exercises dealing with data types. But here’s an opportunity to have some more fun with a few challenges.

Challenge 9.1: Filtering

How would you implement a filter function on a List<T> using fold or foldRight? You can name it filterFold. Remember that given:

typealias Predicate<T> = (T) -> Boolean

The filterFold function for a List<T> should have this signature:

fun <T> List<T>.filterFold(predicate: Predicate<T>): List<T> {
 // Implementation  
}

Challenge 9.2: Length

How would you implement the length function for a List<T> that returns its size using fold or foldRight?

Challenge 9.3: Average

How would you implement the avg function for a List<Double> that returns the average of all the elements using fold or foldRight?

Challenge 9.4: Last

How would you implement the lastFold function for a List<T> that returns the last element using fold or foldRight? What about firstFold?

Key points

• A type is basically a way to represent a set of values you can assign to a variable or, in general, use in your program.
• A data type is a way to represent a value in a specific context. You can usually think of a data type as a container for one or more values.
• Optional<T> is a data type that represents a container that can be empty or contain a value of type T.
• lift is the function you use to “elevate” a value of type T into a data type of M<T>.
• map allows you to interact with a value in a data type applying a function. You’ll learn all about map in Chapter 11, “Functors”.
• flatMap allows you to interact with a value in a data type M<T> using a function that also returns an M<T>. You’ll learn all about flatMap in Chapter 13, “Understanding Monads”.
• List<T> is a data type that contains an ordered collection of values of type T.
• fold and foldRight are magical functions you can use to implement many other functions.
• The Either<A, B> data type allows you to represent a container that can only contain a value of type A or a value of type B.
• You usually use Either<A, B> in the context of success or failure in the execution of a specific operation.
• Either<A, B> has two type parameters. For this reason, it defines functions like bimap, leftMap and rightMap that you apply explicitly on one of the values.
• Some data types with multiple parameters, like Either<A, B>, have functions that are biased on one of them. For instance, Either<A, B> is right-biased and provides functions that implicitly apply to its Right<B> side.

Where to go from here?

In this chapter, you had a lot of fun and implemented many important functions for the most important data type. In the following chapters, you’ll see even more data types and learn about functors and monads in more detail. In the next chapter, you’ll have some fun with math. Up next, it’s time to learn all about algebraic data types.