Kotlin - Better APIs with Compositional Design Patterns

# Better APIs with <br /> Compositional Design Patterns

<br />

---

# 🥅 Goals of this talk

> How we designed the APIs of `Collector` and `Schedule` in Arrow
    
Introduction to **compositional** design patterns

- Functor and Applicative
- (Free) monad

---

# 🏹 Arrow - `arrow-kt.io`
    
Set of libraries for every Kotlin developer <br />
inspired by functional programming
 
* _Core_: typed errors, non-empty collections
* _Collectors_: aggregation with single traversal
* _Fx_: high-level concurrency, resources
* _Resilience_: retries, circuit breakers
* _Optics_: immutable data transformation
* _STM_: transactional operations

All of them Multiplatform-ready

---

# 🏹 Arrow - `arrow-kt.io`
    
Set of libraries for every Kotlin developer <br />
inspired by functional programming
 
* _Core_: ...
* _Collectors_: **aggregation with single traversal**
* _Fx_: ...
* _Resilience_: **retries**, ...
* _Optics_: ...
* _STM_: ...

---

class: center, middle, title-slide
count: false
    
# Introducing the characters

---

# 🧺 Collector

Aggregate several computations into a single pass over a sequence

```kotlin
val average = list.sum() / list.size
```

- The `list` is iterated twice
- This may not be possible for sequences

---

# 🧺 Collector

Aggregate several computations into a single pass over a sequence

.code70[
```kotlin
val averageCollector = zip(
  Collectors.sum,
  Collectors.length
) { x, y -> x / y }

val average = list.collect(averageCollector)
```
]

- Everything is computed in a single pass

---

# ⏲️ Schedule

Description of a policy for executing jobs and (potential) delays between them

- To _retry_ until one succeeds
- To _repeat_ the same job multiple times

Simplest pattern for _resilience_, just try again

---
    
# ⏲️ Schedule examples

// retry with exponential back-off
Schedule.exponential<Unit>(250.milliseconds)

// 1. exponential back-off for 60 seconds
// 2. at most 100 retries spaces by 60 seconds
// with some random noise (jitter)
Schedule.exponential<A>(10.milliseconds)
    .doWhile { _, duration -> duration < 60.seconds }
    .andThen(spaced<A>(60.seconds) and recurs(100))
    .jittered()
```
]

---

# ⏲️ Schedule examples

Using a `Schedule` is pretty easy

- `retry` repeats if an exception is thrown
- More variations for custom error conditions
    
--

> You can read about that in the docs <br />
> here we want to talk about the **internals**
    
---

# 🛡️ `Schedule<Input, Output>`

.margin-top[
- `Input` specifies the data you base your decision upon
- `Output` specifies the result of the action
]

```kotlin
recurs(10) : Schedule<A, Int>
       // iteration count ↲

doWhile(f) : Schedule<A, A>
      // same value back ↲
```

---

# 😵‍💫 Complex implementation
    
Internal `State` type parameter

---
    
# 😵‍💫 Complex implementation

Internal `State` type parameter
    
Unchecked casts

...
    
<br />
    
> We looked for alternatives for a long time

---

class: center, middle, title-slide
count: false
    
# Compositional design patterns
    
---

# 🌱 Functor

This is a pattern over _generic_ types

```kotlin
fun <A, B> Whatever<`A`>.map(
  transform: (A) -> B
): Whatever<`B`>
```

- Transforms each element using `transform`
- Keeps the shape of the structure<super>*</super>

---

# 🌱 Examples of functor

- Map-key values are functors for a fixed key

---

# 🌱 Examples of functor

- Non-sequential containers

.code60[
```kotlin
fun <A, B> BinaryTree<`A`>.map(
  transform: (A) -> B
): BinaryTree<`B`> = when (this) {
  is Leaf ->
    Leaf(transform(value))
  is Node ->
    Node(left.map(transform), right.map(transform))
}
```
]

---

# 🌱 Examples of functor

.margin-top[
- Iterable types: `List`, `Set`, ...
- Map-key values are functors for a fixed key
- Non-sequential containers
]

- Nullable types

---

# 🪴 Functors are compositional

We can write `map` for `F<G<A>>` <br />
from the `map`s of each of them

---

# 🪴 Functors are compositional

We can write `map` for `Map<String, Int?>` <br />
from the `map`s of `Map<String, A>` and `A?`

.code60[
```kotlin
fun <A, B> Map<String, A>.mapValues(...): Map<String, B>
fun <C, D> C?.map(...): D? = this?.let(transform)

fun <U, V> Map<String, U>.map(
  transform: (U) -> V
): Map<String, V> =
  this.mapValues { it?.let(transform) }
```
]

---

# 🪴 Functors are compositional

We can write `map` for `F<G<A>>` <br />
from the `map`s of each of them

```kotlin
fun <A, B> F<A>.mapF(...): F<B>
fun <C, D> G<C>.mapG(...): G<D>

fun <U, V> F<G<U>>.map(
  transform: (U) -> V
): F<G<V>> =
  this.mapF { it.mapG(transform) }
```

---

# 🪴 Functors are compositional

We can write `map` for `F<G<A>>` <br />
from the `map`s of each of them

💡 _We can derive mappers for a complex type_<br />
     _from the mappers of its components_

📚 Having a large library of "basic" mappers <br />
     becomes quite useful

---

# 🧮 Functions are functors

---

# 🧮 Functions are functors

.code60[
```kotlin
fun <E, A, B> ((E) -> A).map(
  transform: (A) -> B
): (E) -> B = { e: E ->
  val a = this(e)
  val b = transform(a)
  b
}
```
]

---

# 🧮 Functions are functors

.code60[
```kotlin
fun <E, A, B> ((E) -> A).map(
  transform: (A) -> B
): (E) -> B = { e: E -> transform(this(e)) }
```
]

Function composition! 🤗

---

# 🪷 Applicative

Similar to functor, but for transformations <br />
with any number of arguments <super>*</super>

```kotlin
fun <A, B, ..., Z> zip(
  a: Whatever<A>,
  b: Whatever<B>,
  ...,
  transform: (A, B, ...) -> Z
): Whatever<Z>
```

.font60[
<super>*</super> Actually you only need the binary case, and you can get the rest by repetition
]

---

# 🪷 Examples of applicative

```kotlin
fun <T1, T2, R> Flow<T1>.zip(
  other: Flow<T2>,
  transform: suspend (T1, T2) -> R
): Flow<R>

fun <T1, T2, R> Flow<T1>.combine(
  flow: Flow<T2>,
  transform: suspend (a: T1, b: T2) -> R
): Flow<R>
```

---

# 🪷 Examples of applicative

.margin-top[
- `Flow` follows this pattern _twice_
- Lists and sets
- Nullable types
- Functions with a given input type
]

Not much time to dive into them ⏳

> Applicatives are also compositional

---

---

# 💡 **The** idea

`map` and `combine` as the basic API

> Let's define `Collector` and `Schedule` as a composition of basic blocks
> so we can derive most implementations

> auto-magically  🧚 🧚 🧚 🧚 🧚 🧚 🧚 🧚 🧚

---

# 🧺 Collector

First idea: encapsulate the arguments to `fold`

.code60[
```kotlin
interface Collector<in Element, Result> {
  public fun supply(): Result
  public fun accumulate(current: Result, value: Element)
}
```
]

## Is `Collector` a functor?

Unfortunately **not** (try at home!)

---

# 🧺 Collector

Second idea: separate **accumulator** from result

* The accumulator type may not agree with element or results

interface CollectorI<Acc, in Element, out Result> {
  public fun supply(): Acc
  public fun accumulate(current: Acc, value: Element)
  public fun finish(current: Acc): Result
}
```
]

Implementations use **local mutability**

---

# 🧺 Collector

## Is `CollectorI` a functor?

Yes, we just need to "fix" the result

.code60[
```kotlin
public fun <E, R, S> Collector<E, `R`>.map(
  transform: suspend (Result) -> S,
): Collector<E, `S`> = of(
  supply = this::supply,
  accumulate = this::accumulate,
  finish = { current -> `transform(this.finish(current))` },
)
```
]

---

# 🧺 Collector

## Is `CollectorI` an applicative?

.code70[
```kotlin
fun <E, A, B, R, S, V> zip(
  collector1: CollectorI<A, E, R>,
  collector2: CollectorI<B, E, S>,
  combine: (R, S) -> V
) : CollectorI<`_`, E, V>
```
]

What do we need to have as accumulator?

---

# 🧺 Collector

## Is `CollectorI` an applicative?

.code70[
```kotlin
fun <E, A, B, R, S, V> zip(
  collector1: CollectorI<A, E, R>,
  collector2: CollectorI<B, E, S>,
  combine: (R, S) -> V
) : CollectorI<`Pair<A, B>`, E, V>
```
]

- Supply and accumulate in parallel
- At the end, apply `combine` to the results

---

# 🧚 Type arguments

Add more type parameters to clarify intermediate states

* Implementation becomes "the single one"

> Veel parameters maken werk licht

Actually, the complete advice is separating contra- and co-variant appearances of the same type parameter

---

# 🖼️ `Schedule` in pictures

---

# 📜 `Schedule` in code

```kotlin
typealias Step<Input, Output>
  = (Input) -> Decision<Input, Output>
```

```kotlin
sealed interface Decision<Input, Output> {
  data class Done(val value: Output): ...
  data class Continue(
    val value: Output,
    val delay: Duration,
    val step: Step<Input, Output>
  ): Decision<Input, Output>
}
```

---

# 📜 `Schedule` in code

```kotlin
typealias Step<Input, Output>
  = (Input) -> Decision<Input, Output>
```

🧚 `Step` is a functor if `Decision` is!

## Is `Decision` a functor?

🧚 There is a _recipe_ to build them if:
- We have a sealed hierarchy of data classes
- Generic `A` appears alone or in a functor

---

# 🍳 Recipe for functor

.code60[
```kotlin
fun <A, B> BinaryTree<A>.map(transform: (A) -> B)
  : BinaryTree<B> = when (this) {
    is Leaf -> Leaf(transform(value))
    is Node ->
      Node(left.map(transform), right.map(transform))
  }
```

```kotlin
fun <I, A, B> Decision<I, A>.map(transform: (A) -> B)
  : Decision<I, B> = when (this) {
    is Done -> Done(transform(value))
    is Continue -> Continue(
      transform(value),    // apply on 'A's
      delay,               // leave alone
      step.map(transform)  // map on functors
    )
  }
```
]

---

# 🍳 Recipe for functor

Applying the recipe can be automated

> Zo vader, zo zoon

In Haskell the recipe is built into the compiler

.code70[
```haskell
data BinaryTree a
  = Leaf { value :: a }
  | Node { left, right :: BinaryTree a}
  deriving (Functor)
      
```
]

---

# 🧱 Simplified `Schedule`

`retry` is a loop with matching inside

---

# 🧞 Composing applicatives

`Schedule` has two instances of the pattern

.code60[
```kotlin
// delay only if both delay
fun <I, A, B, C> fun Schedule<I, A>(
  other: Schedule<I, B>, transform: (A, B) -> C
): Schedule<I, C>

// delay only if any of them delay
fun <I, A, B, C> fun Schedule<I, A>(
  other: Schedule<I, B>, transform: (A, B) -> C
): Schedule<I, C>
```
]

Even one more axis for _combining_ delays

---

---

# 🗓️ Composing `Schedule`s

Execute other `Schedule` one the first is done

.code70[
```kotlin
fun <I, A, B> ((I) -> Decision<I, A>).andThen(
  other: (A) -> Step<I, B>
): (I) -> Decision<I, B>
```
]

---

# 🗓️ Composing `Schedule`s

Execute other `Schedule` one the first is done

.code70[
```kotlin
fun <I, A, B> ((I) -> Decision<I, A>).andThen(
  other: (A) -> Step<I, B>
): (I) -> Decision<I, B> =
  { i: Input -> this(i).andThen(other) }

fun <I, A, B> Decision<I, A>.andThen(
  other: (A) -> Step<I, B>
): Decision<I, B> = TODO()
```
]

---

# 🌳 Monad

Yet another pattern over _generic_ types

```kotlin
fun <A, B> Whatever<A>.flatMap(
  transform: (A) -> Whatever<B>
): Whatever<B>
```

The difference with functor is that `transform` generates another `Whatever`

---

# 🌳 Examples of monad

- Nullable types

]

---

# 🌳 Monads

## Monads are **not compositional**

But there is an interesting subset <br />
called _free monads_

- Exactly one "success" or "done" case <br />
  with one field of generic type
- The rest of the cases mention `Whatever<A>` <br />
  but never the generic type alone

---

# 🐳 Free monads

```kotlin
sealed interface Either<E, A> {
  data class Right<A>(val value: A): ...
  data class Left<E>(val error: E): ...
}
```

- `Option` and `Result`
- Nullable types

---

# 🍳 Recipe for free monad

.code70[
```kotlin
fun <A, B> BinaryTree<A>.flatMap(
  transform: (A) -> BinaryTree<B>
): BinaryTree<B> = when (this) {
    is Leaf ->
      transform(value)
    is Node -> Node(
      left.map(transform),
      right.map(transform)
    )
  }
```
]

Our `Decision` is quite similar to this!

---

---

# Until now

## Are there more?

---

# Are there more?

.code70[
```kotlin
fun <Acc, E, R> CollectorI<Acc, E, R>.contraMap(
  transform: `(F) -> E`  // opposite of 'map'
): CollectorI<Acc, F, R>
```
]

* Pointed functors: returns "constants"
* Selective functors: limited choice
* Alternatives: aggregation or disjunction
* Categories: supports composition
* ...

---

# 🎭 Conclusion

Use _compositional_ patterns in your API

- Powerful primitives to build others
- Potentially free implementations

Developers _recognize_ these patterns

📖 _Typeclassopedia_, by Brent Yorgey

---

# 📖 Time for some ads...

## `serranofp.com` > _Books_