Chapters

Hide chapters

Functional Programming in Kotlin by Tutorials

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

Section I: Functional Programming Fundamentals

Section 1: 8 chapters
Show chapters Hide chapters

Appendix

Section 4: 13 chapters
Show chapters Hide chapters

15. Managing State
Written by Massimo Carli

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

In Section II, you learned about the concept of data type using the analogy of a container providing its content some context. For instance, Optional<A> represents a box that can either be empty or contain a value of type A. The context of a data type is important when you make it a functor or a monad. In the case of a functor, you can apply to Optional<A> a function Fun<A, B> and get an Optional<B>. If the initial Optional<A> is empty, you’ll get an empty Optional<B>. If Optional<A> contains a value of type A, you apply the function Fun<A, B>, to get a value of type B wrapped in an Optional<B>. If the function you apply is of type Fun<A, Optional<B>>, you give Optional<A> the superpower of a monad and use flatMap to get an Optional<B> whose content depends on whether the value A is present. Different data types provide different contexts and behave differently as functors and monads.

Note: An empty Optional<A> is different from an empty Optional<B> if A is different from B. In short, an empty box of pears is different from an empty box of apples. :]

You also learned that a pure function describes an expression that’s referentially transparent and, more importantly, doesn’t have any side effects. These two properties are connected because when an expression isn’t referentially transparent, it uses some data that’s outside the scope of the function, which is a side effect. A side effect changes the state of the universe outside the function body.

The question now is: Can you create a data type representing a box that encapsulates some data and the effect that happens when you apply functions with map or flatMap to the same data? With this data type, you wouldn’t prevent the change of some state, but you’d be able to control it.

The solution is the State<T> data type, which is the topic of this chapter. Here, you’ll learn:

  • What StateTranformation<S, T> is.
  • How to implement a State<S, T> data type.
  • How the State<S, T> data type works as a functor.
  • How to implement State<T> as an applicative functor.
  • What the State<S, T> monad is.
  • How to apply the State<S, T> monad in a practical example.

This is probably one of those chapters you’ll need to read multiple times, but it’ll definitely be worth it!

The problem

To describe how the State<S, T> data type works, it’s helpful to start with a very simple example. You can follow along with it in the Inventory.kt file in the material for this project. Start by adding this code:

data class Product(val id: String, val name: String)

This is a simple Product data class representing — ahem — a product. :] During an inventory, you want to assign a SKU to it.

Note: A stock keeping unit (SKU) is a scannable bar code that you usually find printed on product labels in retail stores. It’s used to track inventory movement automatically.

In this case, suppose the SKU has the format RAY-PROD-####, where #### represents a four-digit number that must be unique for each product.

Note: Please ignore the fact that, with this format, you can only have 10,000 different SKUs. This just allows the code to remain simple so you can focus on the state. Of course, you can implement your SKU generator algorithm however you want.

You represent a product after the inventory as an instance of SkuProduct, which you add to the same file:

data class SkuProduct(val product: Product, val sku: String)

To assign a unique SKU to every product, use the following code:

var count = 0 // 1

fun createSku(): String = // 2
  "RAY-PROD-${String.format("%04d", count++)}" // 3

In this code, you:

  1. Initialize the global variable count to 0.
  2. Define createSku as a function returning a unique SKU as a String.
  3. Update count, allowing you to get a different SKU at each createSku invocation.

To test the previous function, add and run the following code:

fun main() {
  val prod1 = Product("1", "Cheese")
  val prod2 = Product("2", "Bread")
  val prod3 = Product("3", "Cake")

  SkuProduct(prod1, createSku()) pipe ::println
  SkuProduct(prod2, createSku()) pipe ::println
  SkuProduct(prod3, createSku()) pipe ::println
}

Getting in output:

SkuProduct(product=Product(id=1, name=Cheese), sku=RAY-PROD-0000)
SkuProduct(product=Product(id=2, name=Bread), sku=RAY-PROD-0001)
SkuProduct(product=Product(id=3, name=Cake), sku=RAY-PROD-0002)

Everything looks fine, but it’s actually not! Now that you know all about pure functions and side effects, you surely noted that createSku isn’t pure — every time you invoke it, you change the state of the universe that, in this case, you represent with count.

At this point, you have two main goals:

  • Make createSku pure.
  • Simplify its usage in your inventory.

The first step is introducing the concept of state transformation.

State transformation

createSku is impure because of the side effect related to the count update, which happens every time you invoke createSku. This creates the SKU based on the current value of count, which is the current state. createSku also updates the state, preparing for the next invocation. You can generalize this behavior with the following definition, which you can add to State.kt:

typealias StateTransformer<S> = (S) -> S
val skuStateTransformer: StateTransformer<Int> =
  { state -> state + 1 }
typealias StateTransformer<S, T> = (S) -> Pair<T, S>
val skuStateTransformer: StateTransformer<Int, String> = { state ->
  "RAY-PROD-${String.format("%04d", state)}" to state + 1
}
fun main() {
  val prod1 = Product("1", "Cheese")
  val prod2 = Product("2", "Bread")
  val prod3 = Product("3", "Cake")

  val state0 = 0 // 1
  val (sku1, state1) = skuStateTransformer(state0) // 2
  SkuProduct(prod1, sku1) pipe ::println // 3
  val (sku2, state2) = skuStateTransformer(state1) // 4
  SkuProduct(prod2, sku2) pipe ::println // 5
  val (sku3, state3) = skuStateTransformer(state2) // 6
  SkuProduct(prod3, sku3) pipe ::println // 7
}
SkuProduct(product=Product(id=1, name=Cheese), sku=RAY-PROD-0000)
SkuProduct(product=Product(id=2, name=Bread), sku=RAY-PROD-0001)
SkuProduct(product=Product(id=3, name=Cake), sku=RAY-PROD-0002)

A state transformer visual intuition

Before proceeding, there’s something you should fix. skuStateTransformer receives an Int as input and returns a String for the SKU and another Int for the new state. In the inventory problem, you need something else because you need to start from a Product and get a SkuProduct.

val assignSku: (Product, Int) -> Pair<SkuProduct, Int> = // 1
  { product: Product, state ->
    val newSku = "RAY-PROD-${String.format("%04d", state)}" // 2
    SkuProduct(product, newSku) to state + 1 // 3
  }
val curriedAssignSku:
      (Product) -> StateTransformer<Int, SkuProduct> =
  assignSku.curry()
(njomo) (hey srapo) Slodazn Upr Iyh KsaRnihewr eryangFso
Cukeqo 44.5: Mkixe dtiwfgerzad

fun main() {
  val prod1 = Product("1", "Cheese")
  val prod2 = Product("2", "Bread")
  val prod3 = Product("3", "Cake")

  val state0 = 0
  val (skuProd1, state1) = curriedAssignSku(prod1)(state0)
  skuProd1 pipe ::println
  val (skuProd2, state2) = curriedAssignSku(prod2)(state1)
  skuProd2 pipe ::println
  val (skuProd3, state3) = curriedAssignSku(prod3)(state2)
  skuProd3 pipe ::println
}
SkuProduct(product=Product(id=1, name=Cheese), sku=RAY-PROD-0000)
SkuProduct(product=Product(id=2, name=Bread), sku=RAY-PROD-0001)
SkuProduct(product=Product(id=3, name=Cake), sku=RAY-PROD-0002)

Introducing the State<S, T> data type

The StateTransformer<T, S> type you defined earlier is a function type. What you need now is a data type so you can apply all the typeclasses; like functor, applicative and monad; you applied for Optional<T>, Either<A, B> or Result<T>. To do this, you just need to add the following code to the State.kt file:

data class State<S, T>(val st: StateTransformer<S, T>)
operator fun <S, T> State<S, T>.invoke(state: S) = st(state)

Implementing lift

The first operation you need to implement is lift, also called return in other languages. This is the function you use to get a value of type T and put it into the box related to the specific data type, in this case, State<S, T>. In State.kt, change the State<S, T> definition like this:

data class State<S, T>(
  val st: StateTransformer<S, T>
) {

  companion object { // 1
    @JvmStatic
    fun <S, T> lift(
      value: T // 2
    ): State<S, T> = // 3
      State({ state -> value to state }) // 4
  }
}
fun main() {
  val initialState = State.lift<Int, Product>(Product("1", "Cheese"))
}

State<S, T> as a functor

After lift, it’s time to make State<S, T> a functor. This means providing an implementation of the map function of type (State<S, A>) -> (Fun<A, B>) -> (State<S, B>).

fun <S, A, B> State<S, A>.map( // 1
  fn: Fun<A, B> // 2
): State<S, B> = // 3
  State { state ->  // 4
    val (a, newState) = this(state) // 5
    fn(a) to newState // 6
  }
val skuSerial = { sku: String -> sku.takeLast(4) } // 1

val skuState: State<Int, String> = State { state: Int -> // 2
  "RAY-PROD-${String.format("%04d", state)}" to state + 1
}

val skuSerialState = skuState.map(skuSerial) // 3

fun main() { // 4
  skuState(0) pipe ::println
  skuSerialState(0) pipe ::println
}
(RAY-PROD-0000, 1)
(0000, 1)

State<S, T> as an applicative functor

Looking at the signature of map for the State<S, A>, notice that it accepts a function of type Fun<A, B> as input. As you know, Fun<A, B> is the type of function with a single input parameter of type A returning a value of type B.

typealias Fun2<T1, T2, R> = (T1, T2) -> R
typealias Fun3<T1, T2, T3, R> = (T1, T2, T3) -> R
typealias Fun4<T1, T2, T3, T4, R> = (T1, T2, T3, T4) -> R
typealias Chain2<T1, T2, R> = (T1) -> (T2) -> R
typealias Chain3<T1, T2, T3, R> = (T1) -> (T2) -> (T3) -> R
typealias Chain4<T1, T2, T3, T4, R> =
  (T1) -> (T2) -> (T3) -> (T4) -> R
fun <S, A, B, C> State<S, Pair<A, B>>.map2(
  fn: Fun2<A, B, C>
): State<S, C> =
  State { state ->
    val (pair, newState) = this(state) // Or st(state)
    val value = fn(pair.first, pair.second)
    value to newState
  }
fun <S, A, B, C> State<S, Pair<A, B>>.map2(
  fn: Chain2<A, B, C> // 1
): State<S, C> =
  State { state ->
    val (pair, newState) = this(state) // Or st(state)
    val value = fn(pair.first)(pair.second)  // 2
    value to newState
  }
fun <S, T, R> State<S, T>.ap(
  fn: State<S, (T) -> R>
): State<S, R> {
  // TODO
}
fun replaceSuffix(
  input: String,
  lastToRemove: Int,
  postfix: String
) = input.dropLast(lastToRemove) + postfix
val cReplaceSuffix = ::replaceSuffix.curry()
infix fun <S, A, B> State<S, (A) -> B>.appl(a: State<S, A>) =
  a.ap(this) // 1

fun main() {
  val initialStateApp = State
    .lift<Int, Chain3<String, Int, String, String>>(
      cReplaceSuffix
    ) // 2
  val inputApp = State.lift<Int, String>("1234567890") // 3
  val lastToRemoveApp = State.lift<Int, Int>(4) // 3
  val postfixApp = State.lift<Int, String>("New") // 3
  val finalStateApp = initialStateApp appl
    inputApp appl lastToRemoveApp appl postfixApp // 4

  inputApp(0) pipe ::println // 5
  finalStateApp(0) pipe ::println // 5
}
fun <S, T, R> State<S, T>.ap( // 1
  fn: State<S, (T) -> R> // 2
): State<S, R> = // 3
  State { s0: S -> // 4
    val (t, s1) = this(s0) // 5
    val (fnValue, s2) = fn(s1) // 6
    fnValue(t) to s2 // 7
  }
(1234567890, 0)
(123456New, 0)

State<S, T> as a monad

Now, it’s finally time to give State<S, T> the power of a monad by implementing flatMap. To do that, you could follow the same process you learned in Chapter 13, “Understanding Monads”, providing implementation to fish, bind, flatten and finally flatMap. That was a general process valid for all monads, but now you can go straight to the solution, starting with the following code you write in StateMonad.kt:

fun <S, A, B> State<S, A>.flatMap( // 1
  fn: (A) -> State<S, B> // 2
): State<S, B> = TODO() // 3
fun <S, A, B> State<S, A>.flatMap(
  fn: (A) -> State<S, B>
): State<S, B> =
  State { s0: S -> // 1
    val (a, s1) = this(s0) // 2
    fn(a)(s1) // 3
  }
val assignSkuWithState: // 1
      (Product) -> State<Int, SkuProduct> =
  { prod: Product ->
    State(curriedAssignSku(prod)) // 2
  }

fun main() {
  val prod1 = Product("1", "First Product") // 3
  val initialState = State.lift<Int, Product>(prod1) // 4
  val finalState = initialState.flatMap(assignSkuWithState) // 5
  finalState(0) pipe ::println // 6
}
(SkuProduct(product=Product(id=1, name=First Product), sku=RAY-PROD-0000), 1)

A practical example

In the previous example, you didn’t have the chance to appreciate the hidden state transformation that the State<S, T> monad does for you behind the scenes. As a more complicated example, suppose you have an FList<Product>, and you want to assign each one a unique value for the SKU, getting an FList<SkuProduct> as output.

val products = FList.of(
  Product("1", "Eggs"),
  Product("2", "Flour"),
  Product("3", "Cake"),
  Product("4", "Pizza"),
  Product("5", "Water")
)
var currentCount = 0
fun inventoryMap(products: FList<Product>): FList<SkuProduct> {
  return products.map {
    SkuProduct(it,
      "RAY-PROD-${String.format("%04d", currentCount++)}")
  }
}
fun main() {
  inventoryMap(products).forEach(::println)
}
SkuProduct(product=Product(id=1, name=Eggs), sku=RAY-PROD-0000)
SkuProduct(product=Product(id=2, name=Flour), sku=RAY-PROD-0001)
SkuProduct(product=Product(id=3, name=Cake), sku=RAY-PROD-0002)
SkuProduct(product=Product(id=4, name=Pizza), sku=RAY-PROD-0003)
SkuProduct(product=Product(id=5, name=Water), sku=RAY-PROD-0004)
fun inventoryMapWithCount(
  products: FList<Product>
): FList<SkuProduct> {
  var internalCount = 0
  return products.map {
    SkuProduct(it,
      "RAY-PROD-${String.format("%04d", internalCount++)}")
  }
}
fun listInventory(
  products: FList<Product>
): (Int) -> Pair<Int, FList<SkuProduct>> =
  when (products) { // 1
    is Nil -> { count: Int -> count to Nil } // 2
    is FCons<Product> -> { count: Int -> // 3
      val (newState, tailInventory) =
        listInventory(products.tail)(count)
      val sku = "RAY-PROD-${String.format("%04d", newState)}"
      newState + 1 to FCons(
        SkuProduct(products.head, sku), tailInventory)
    }
  }
fun main() {
  listInventory(products)(0).second.forEach(::println)
}
SkuProduct(product=Product(id=1, name=Eggs), sku=RAY-PROD-0004)
SkuProduct(product=Product(id=2, name=Flour), sku=RAY-PROD-0003)
SkuProduct(product=Product(id=3, name=Cake), sku=RAY-PROD-0002)
SkuProduct(product=Product(id=4, name=Pizza), sku=RAY-PROD-0001)
SkuProduct(product=Product(id=5, name=Water), sku=RAY-PROD-0000)
fun <S, A, B, C> State<S, A>.zip( // 1
  s2: State<S, B>, // 2
  combine: (A, B) -> C // 3
): State<S, C> = // 4
  State { s0 -> // 5
    val (v1, s1) = this(s0) // 6
    val (v2, s2) = s2(s1) // 7
    combine(v1, v2) to s2 // 8
  }
val addSku: (Product) -> State<Int, SkuProduct> = // 1
  { prod: Product ->
    State<Int, SkuProduct> { state: Int ->
      val newSku = "RAY-PROD-${String.format("%04d", state)}"
      SkuProduct(prod, newSku) to state + 1
    }
  }

fun inventory(
  list: FList<Product>
): State<Int, FList<SkuProduct>> = // 2
  when (list) { // 3
    is Nil -> State.lift(Nil) // 4
    is FCons<Product> -> {
      val head = State.lift<Int, Product>(list.head) // 5
        .flatMap(addSku)
      val tail = inventory(list.tail) // 6
      head.zip(tail) { a: SkuProduct, b: FList<SkuProduct> -> // 7
        FCons(a, b)
      }
    }
  }
fun main() {
  inventory(products)(0).first.forEach(::println)
}
SkuProduct(product=Product(id=1, name=Eggs), sku=RAY-PROD-0000)
SkuProduct(product=Product(id=2, name=Flour), sku=RAY-PROD-0001)
SkuProduct(product=Product(id=3, name=Cake), sku=RAY-PROD-0002)
SkuProduct(product=Product(id=4, name=Pizza), sku=RAY-PROD-0003)
SkuProduct(product=Product(id=5, name=Water), sku=RAY-PROD-0004)

Key points

  • A data type is like a container that provides some context to its content.
  • A state represents any value that can change.
  • You can use the concept of state to model the side effect of an impure function.
  • The context of a data type impacts how you interact with its content when applying some functions.
  • The State<S, T> data type encapsulates the concept of state transition.
  • StateTransformer<S, T> abstracts a value and a state update.
  • State<S, T> is a data type that encapsulates a StateTransformer<S, T>.
  • You can make State<S, T> a functor providing the implementation for map.
  • map on a State<S, T> applies a function to the value of type T but leaves the state unchanged.
  • Making State<S, T> an applicative functor allows you to apply functions with multiple parameters.
  • You can make State<S, T> a monad, providing implementation for the flatMap.
  • The State<S, T> allows you to define two different types of transactions. The first, on the value, is visible. The second, on the state transition, is hidden.

Where to go from here?

Congratulations! This is definitely one of the most challenging chapters of the book. Using most of the concepts from the first two sections of the book, you learned how to use the State<S, T> data type and how to implement lift, map, app, appl and flatMap. Finally, you applied the State<S, T> monad to a real example, showing how it’s possible to keep the state transaction hidden. The concept of side effects is one of the most important in functional programming, and in the next chapter, you’ll learn even more about it.

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 reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now