Monads and Applicatives

Предния път – Type classes

моделират типове
предоставят общ интерфейс и аксиоми за цяло множество от типове
или още – общ език, чрез който да мислим и боравим с тези типове
позволяват ad hoc полиморфизъм
наблягат на композитността и декларативността
добавят се ретроактивно към типовете и в Scala могат да бъдат контекстно-зависими

Днес - Монади и Апликативи

Ефекти

Option[A] – частичност
Try[A] – успех/грешка с изключение
Either[E, A] – успех/грешки
Validated[E, A] – валидация с множествено грешки
List[A] – недетерминизъм, множественост
Future[A] – (eager) асинхронност
IO[A] – (lazy) асихронност
State[S, A] – състояние

Нека да генерализираме познатите ни от тях операции в type class-ове

Предния път постигнахме подобна генерализация за обикновени типове, нека сега се опитаме да го направим и за ефекти.

Ще започнем от една различна гледна точка

Композиция на функции

Нека имаме функции f: A => B и g: B => C

Тогава h(x) = g(f(x)) е функция от тип A => C

h = g ∘ f

Композитност на функции – аксиоми

асоциативност – нека f: A => B, g: B => C и h: C => D. Тогава:
```
(h ∘ g) ∘ f = h ∘ (g ∘ f)
```
неутрален елемент – нека identity = x => x. Тогава ∀ f
```
identity ∘ f = f ∘ identity = f
```

Композитност на функции

h ∘ g ∘ f

Ефектни функции

Функция, връщаща стойност, затворена в ефект

A => Option[B]
A => Future[B]
A => Validated[E, B]

Наричат се още Kleisli arrows

Композитност на ефектни функции?

Нека
f: A => Option[B],
g: B => Option[C],
h: C => Option[D]

h ∘ g ∘ f?

За всеки ефект имплементацията е различна

Option, ако нямаме `flatMap`

def compose[A, B, C, D](f: A => Option[B],
                        g: B => Option[C],
                        h: C => Option[D]): A => Option[D] = a =>
  val fOption = f(a)
  if fOption != None then
    val gOption = g(fOption.get)
    if (gOption != None) then
      h(gOption.get)
    else
      None
  else
    None

Често срещано при работа с някои езикови елементи (null, callback hell код, …)

Type class за композиране

Монада

trait Monad[F[_]]:
  def compose[A, B, C](f: A => F[B], g: B => F[C]): A => F[C]
  def unit[A](a: A): F[A]

Тук F е конструктор на тип, а не тип

Пример: List е конструктор на тип, List[Int] е тип

F е higher-kinded type (тип от по-висок ред)

higher-kinded polymorphism

Monads are like burritos

Монада – аксиоми

асоциативност:

compose(compose(f, g), h) == compose(f, compose(g, h))

неутрален елемент, за който имаме left identity & right identity
```
compose(unit, f) == compose(f, unit) == f
```
Много приличат на аксиомите за моноид, но с функции

A monad is just a monoid in the category of endofunctors, what’s the problem? - A Brief, Incomplete, and Mostly Wrong History of Programming Languages

Монада за Option

trait Monad[F[_]]
  def compose[A, B, C](f: A => F[B], g: B => F[C]): A => F[C]
  def unit[A](a: A): F[A]

val optionMonad = new Monad[Option]:
  def compose[A, B, C](f: A => Option[B], g: B => Option[C]) =
    (a: A) => f(a) match
      case Some(b) => g(b)
      case _ => None

  def unit[A](a: A): Option[A] = Some(a)

Алтернативна дефиниция
чрез `flatMap`

trait Monad[F[_]]:
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
  def unit[A](a: => A): F[A]

  def compose[A, B, C](f: A => F[B], g: B => F[C]): A => F[C]

compose се изразява чрез flatMap като:

def compose[A, B, C](f: A => F[B], g: B => F[C]): A => F[C] =
  a => flatMap(f(a))(g)

flatMap може да се изрази чрез compose като:

compose((_: Unit) => fa, f)(())

Аксиомите чрез `flatMap`

асоциативност:

Нека m: F[A] и f: A => F[B], g: B => F[C]. Тогава
```
m.flatMap(f).flatMap(g) == m.flatMap(a => f(a).flatMap(g))
```
ляв идентитет:

∀a: A и f: A => F[B] е изпълнено: unit(a).flatMap(f) == f(a)
десен идентитет:

∀m: F[A] е изпълнено: m.flatMap(unit) == m

Нека имплементираме още няколко допълнителни операции към монадата - exercises/effects/Monad.scala

Maybe

Наша имплементация на Option - ще използваме името Maybe за да избегнем колизия с името от стандартната библиотека

unit, map и flatten (aka join) са трети възможен набор от основни операции

Но какво точно е Монада?

По-ясна дефиниция от предната:

Монадата ни позволява да опишем последователни изчисления върху ефекти

Или още казано - да композираме ефектни изчисления едно след друго

Видяхме, че има няколко възможни набори от основни операции
- unit и flatMap
- unit и compose
- unit, map, и flatten
Освен това имаме 2 закона, които могат да бъдат формулирани по няколко начина - за асоциативност и идентитет
Всъщност се разбират много по-добре в даден контекст - с примери

Id монада

effects/id/Id.scala

State монада

effects/state/State.scala

Генерализация на монадите – функтори

trait Functor[F[_]]:
  def map[A, B](fa: F[A])(f: A => B): F[B]

trait Monad[F[_]] extends Functor[F]:
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
  def unit[A](a: A): F[A]

  def map[A, B](fa: F[A])(f: A => B): F[B] =
    flatMap(fa)(a => unit(f(a)))

Аксиоми

Идентитет

x.map(a => a) == x

асоциативност

x.map(f).map(g) == x.map(f andThen g)

Грешни състояния на монади

Някои монади си имат и грешни състояния, които биха прекъснали цялата композиция

Примери:

Option - None
Either - Left(error)
Try - Failure(throwable)

Грешни състояния на монади

Композицията става по-трудна ако работим с библиотеки, които ползват различни монади за връщане на грешките

def readFile(): Try[String] = ???

def toJson(str: String): Either[Throwable, Json] = ???

for
  fileContent <- readFile()
  parsedFile <- toJson(fileContent)  //does not compile
yield parsedFile

Това също може да се генерализира като използваме MonadError[F[_], E], но няма да го разглеждаме подробно.

Валидиране и натрупване на грешки

Нека разгледаме примера от домашното и се опитаме да използваме монада за Validated
Можем да получим друга абстракция ако използваме unit & map2 за основни операции

Applicative

trait Applicative[F[_]] extends Functor[F]:

  // primitive
  def map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C]
  def unit[A](a: => A): F[A]

  // derived
  def map[A, B](fa: F[A])(f: A => B): F[B] = map2(fa, unit(()))((a, _) => f(a))
  def zip[A,B](fa: F[A], fb: F[B]): F[(A,B)] = map2(fa, fb)((_,_))

Алтернативни базови операции са map, zip, unit

Разликите между Monad и Applicative

Applicative

val F: Applicative[Option] = ???

val depts: Map[String, String] = ???
val salaries: Map[String, Double] = ???

// two independent lookups
val o: Option[String] =
  F.map2(depts.get("Alice"), salaries.get("Alice"))(
    (dept, salary) => s"Alice in $dept makes $salary per year"
  )

Разликите между Monad и Applicative

Monad

val F: Monad[Option] = ???

val idsByName: Map[String, Int] = ???
val depts: Map[Int, String] = ???
val salaries: Map[Int, Double] = ???

// the results of one lookup affect what lookup we do next
val o: Option[String] =
  idsByName.get("Bob").flatMap { id =>
    F.map2(depts.get(id), salaries.get(id))(
      (dept, salary) => s"Bob in $dept makes $salary per year"
    )
  }

Разликите между Monad и Applicative

Монадата добавя допълнителни възможности над Applicative - join или flatMap
С апликатива може да комбинираме независими стойности, докато с монадата моделираме зависимост между такива.
С апликатива структурата на програмата е фиксирана, а с монадата резултатите от предните изчисления могат да повлияят кои изчисления да се изпълняват по-нататък.
Монадата е sequential, докато апликатива ни дава възможност за независимост и паралелизъм
Нека отново разгледаме примера с Validated

map3, 4 … N

Бихме могли да дефинираме и повече от map2

def map3[A,B,C,D](fa: F[A], fb: F[B], fc: F[C])(f: (A, B, C) => D): F[D] =
  val product = zip(zip(fa, fb), fc)
  map(product) {
    case ((a, b), c) => f(a, b, c)
  }

def map4[A,B,C,D,E](fa: F[A],
                    fb: F[B],
                    fc: F[C],
                    fd: F[D])(f: (A, B, C, D) => E): F[E]

sequence & traverse

Когато не знаем колко е N

  def sequence[A](lfa: List[F[A]]): F[List[A]] =
    traverse(lfa)(fa => fa)

  def traverse[A,B](as: List[A])(f: A => F[B]): F[List[B]] =
    as.foldRight(unit(List[B]()))((a, mbs) => map2(f(a), mbs)(_ :: _))

sequence & traverse

Примери: effects/ApplicativeSequenceDemo & effects/ApplicativeTraverseDemo

Traversable

В дефиницията на sequence & traverse виждаме конкретен тип, който може да бъде генерализиран
Това е List - нека се абстрахираме от него

Traversable

trait Traversable[F[_]] extends Functor[F]:
  def traverse[G[_] : Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]
  
  def sequence[G[_] : Applicative, A](fga: F[G[A]]): G[F[A]] =
    traverse(fga)(ga => ga)

traverse също може да се изрази чрез sequence

map може да се изрази чрез traverse

Композитност на функтори, монади и апликативи

Функторите могат да бъдат композирани:

import cats.Functor
import cats.implicits.*

val listOption = List(Some(1), None, Some(2))
// listOption: List[Option[Int]] = List(Some(1), None, Some(2))

// Through Functor#compose
Functor[List].compose[Option].map(listOption)(_ + 1)
// res1: List[Option[Int]] = List(Some(2), None, Some(3))

Апликативите също

import cats.data.Nested
import cats.implicits.*
import scala.concurrent.Future
import scala.concurrent.ExecutionContext.Implicits.global

val x: Future[Option[Int]] = Future.successful(Some(5))
val y: Future[Option[Char]] = Future.successful(Some('a'))

val composed = Applicative[Future].compose[Option].map2(x, y)(_ + _)
// composed: Future[Option[Int]] = Future(Success(Some(102)))

В общия случай монадите не могат да се композират. Но много могат

Това води до нуждата от специфични монадни трансформатори

Например OptionT за монади от Option
(тоест M[Option[_]], където M е монада)

Functional Programming in Scala

Monads and Applicatives

Предния път – Type classes

Днес - Монади и Апликативи

Ефекти

Композиция на функции

Композитност на функции – аксиоми

Композитност на функции

Ефектни функции

Композитност на ефектни функции?

Option, ако нямаме flatMap

Type class за композиране

Монада

Монада – аксиоми

Монада за Option

Алтернативна дефинициячрез flatMap

Аксиомите чрез flatMap

Maybe

Но какво точно е Монада?

Id монада

State монада

Генерализация на монадите – функтори

Аксиоми

Грешни състояния на монади

Грешни състояния на монади

Валидиране и натрупване на грешки

Applicative

Разликите между Monad и Applicative

Разликите между Monad и Applicative

Разликите между Monad и Applicative

map3, 4 … N

sequence & traverse

sequence & traverse

Traversable

Traversable

Композитност на функтори, монади и апликативи

Functional Programming in Scala

Теория на категориите

Option, ако нямаме `flatMap`

Алтернативна дефиниция
чрез `flatMap`

Аксиомите чрез `flatMap`