# Kleisli category ## for Bartosz M. fans --- ## What is a category (recap) ---- **Category** is a collection of "objects" that are linked by "arrows". A category has two basic properties: * the ability to compose the arrows **associatively**; * the existence of an **identity arrow** for each object. ```graphviz digraph g{ compound=true rankdir=LR graph [ fontname="Source Sans Pro", fontsize=20 ]; a->a[label=id] b->b[label=id] c->c[label=id] d->d[label=id] a->b[label=f,fontsize=30] b->c[label=g,fontsize=30] c->d[label=h,fontsize=30] a->c[label="g.f",fontsize=30,color=green] } ``` ---- ### Example: financial processing * `get_account_state: A -> B` * `apply_tax_reductions: B -> C` * `apply_taxes: C -> D` * `process: A -> D` ```graphviz digraph g{ rankdir=LR graph [ fontname="Source Sans Pro", fontsize=20 ]; A->B[label=get_account_state] B->C[label=apply_tax_reductions] C->D[label=apply_taxes] A->D[label="process",color=green] } ``` Note: Ok, what if we want to get a bit more information about process? How are things going? --- ## Embelishment `f: A -> B` `f*: A -> (B, log) = B*` Note: Lets add a bit more information to our functions. Let them return some textual log. ---- ### Embelished finanical system * `get_account_state*: A -> B*` * `apply_tax_reductions*: B -> C*` * `apply_taxes*: C -> D*` * `process*: ???` ---- ### Embelished finanical system * `get_account_state*: A -> B*` * `apply_tax_reductions*: B -> C*` * `apply_taxes*: C -> D*` * `process*: ???` ```graphviz digraph g{ rankdir=LR graph [ fontname="Source Sans Pro", fontsize=20 ]; A, B, C mb[label="B*",shape=doublecircle] mc[label="C*",shape=doublecircle] md[label="D*",shape=doublecircle] A->mb[label="get_account_state*"] B->mc[label="apply_tax_reductions*"] C->md[label="apply_taxes*"] mb->B[style=dotted] mc->C[style=dotted] md->D[style=dotted] A->D[style=dashed,color=green,label="process*?"] } ``` Note: How to compose these functions? --- ## How do we compose embelished functons? ---- ``` f*: A -> B* = A -> (B, log) g*: B -> C* = B -> (C, log) compose: (A -> B*) -> (B -> C*) -> (A -> C*) ``` ---- ``` f*: A -> B* = A -> (B, log) g*: B -> C* = B -> (C, log) compose: (A -> B*) -> (B -> C*) -> (A -> C*) ``` ``` compose(f, g)(a) { (b, b_log) = f(a) (c, c_log) = g(b) return (c, b_log ++ c_log) } ``` ---- ### Embelished finanical system * `get_account_state*: A -> B*` * `apply_tax_reductions*: B -> C*` * `apply_taxes*: C -> D*` * `process*: A -> D*` ```graphviz digraph g{ rankdir=LR graph [ fontname="Source Sans Pro", fontsize=20 ]; node [shape=circle] A node [shape=doublecircle] B, C, D A->B[style=circle,label="get_account_state*"] B->C[label="apply_tax_reductions*"] C->D[label="apply_taxes*"] A->D[color=green,label="process*"] } ``` --- ## Embelished category Can we make a category? We need **identity arrows** We need **assossiatively composobale** arrows. ```graphviz digraph g{ rankdir=LR graph [ fontname="Source Sans Pro", fontsize=20 ]; node [shape=circle] A node [shape=doublecircle] B, C, D A->B[style=circle,label="f*"] B->C[label="g*"] C->D[label="h*"] } ``` ---- `id . f = f . id` ---- `id . f = f . id` ``` compose: (A -> B*) -> (B -> C*) -> (A -> C*) ``` ---- `id . f = f . id` ``` compose: (A -> B*) -> (B -> C*) -> (A -> C*) ``` `id: A -> A*` --- ### Embellished identity `id . f = f . id` ``` compose: (A -> B*) -> (B -> C*) -> (A -> C*) ``` `id: A -> A*` `id* (a) = (a, "")` --- ### Assossiative composability Easy to prove that new arrows are still assossiatively composable ``` compose(f*, compose(g*, h*)) == compose(compose(f*, g*), h*) ``` ```graphviz digraph g{ rankdir=LR graph [ fontname="Source Sans Pro", fontsize=20 ]; A->B[label="f*"] B->C[label="g*"] C->D[label="h*"] B->D[label="hg*", color=red, style=dashed] A->C[label="gf*", color=blue, style=dashed] A->D[label="hgf*", color=green, style=dashed] } ``` --- ## Kleisli category ```graphviz digraph g{ rankdir=LR graph [ fontname="Source Sans Pro", fontsize=20 ]; A->B[label="f*"] B->C[label="g*"] C->D[label="h*"] B->D[label="hg*", color=red, style=dashed] A->C[label="gf*", color=blue, style=dashed] A->D[label="hgf*", color=green, style=dashed] A->A[label="id*"] B->B[label="id*"] C->C[label="id*"] D->D[label="id*"] } ``` ---- How do we create Kleisli category: * Use the same objects * Morphisms are **Kleisli arrows**: `f: A -> B*`, where `B*` is *embelished* `B` * Identity is `id*` * Composition of morphisms are defined by *embelishment*. --- ### What is embelishment? ---- *Embelishment* defines the derived type with *additional* information. ---- Additional information can be evaluated later. For example, *side-effects*. ---- Different emeblishment defines different Kleisli category. --- ### M-word *Embelishment* is a **Monad**. ---- Our example uses `Writer` monad but there are many others: `Option/Maybe`, `Future`, `Try`, `List`, etc. ---- Kleisli category is defined by a monad that defines *identity* and *composition*. ---- #### Bonus We can define a monad that does **nothing** ``` f*: A -> B f == f* ``` It defines Kleisli category for our first example: ```graphviz digraph g{ rankdir=LR graph [ fontname="Source Sans Pro", fontsize=20 ]; A->B[label=get_account_state] B->C[label=apply_tax_reductions] C->D[label=apply_taxes] A->D[label="process",color=green] } ``` --- ## Show me the code! ---- ### Writer monad ---- What interface do monad have? ---- Monad should be able to take an embelished function and apply on inner value. ---- ```scala final case class Writer[A](value: A, s: String) { def flatMap[B](f: A => Writer[B]): Writer[B] = { val b = f(value) Writer(b.value, s ++ b.s) } } ``` --- ### Composition ```scala def compose[A, B, C](f: A ⇒ Writer[B], g: B ⇒ Writer[C]): A ⇒ Writer[C] = a ⇒ f(a).flatMap(g) ``` --- ## Thank you! Interesting reading: * [From design patterns to category theory](https://blog.ploeh.dk/2017/10/04/from-design-patterns-to-category-theory/) * [Monads Made Hard](http://www.stephendiehl.com/posts/monads.html)