Chapters
Chapters

Chapters

Hide chapters

Functional Programming in Kotlin by Tutorials

First Edition · Android 12 · Kotlin 1.6 · IntelliJ IDEA 2022

Before You Begin

Section 0: 5 chapters
Show chapters Hide chapters

Section I: Functional Programming Fundamentals

Section 1: 8 chapters
Show chapters Hide chapters

Section II: Data Types & Typeclasses

Section 2: 5 chapters
Show chapters Hide chapters

Section III: Functional Programming in Practice

Section 3: 7 chapters
Show chapters Hide chapters

Appendix

Section 4: 13 chapters
Show chapters Hide chapters

9. Data Types
Written by Massimo Carli

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

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:

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

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

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

Result is 20

val res = strToInt("10aaa")

Error!

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:

Imgaiciv<Tmdibb> Npcesv Aln Enraureg<Efl> Amyoobav<Acb> fip jonIdSiqiu() cisv() wzuyPum
Hocije 2.7 - Puld bobf Ipyiacer<R>

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

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

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
  }

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

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
  }

20

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

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

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

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
}

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

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
}

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

55

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

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

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

55

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

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

3628800

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
}

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

55
3628800

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

55
3628800

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:

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

(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

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

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

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

(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

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

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

55
3628800

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

12345678910
12345678910
10987654321
10987654321

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?

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

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
}

55
3628800

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

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

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
  }

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

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.

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

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

1
2
3
4
5
6

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

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

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

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.

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

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

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

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
}

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.

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

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
}

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

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

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

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

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

100

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

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.

8. Composition
10. Algebraic Data Types
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now