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

Ефекти

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

Операции върху ефекти

val a = 42 // независими
val b = 4  // изчисления

val c = a + b // операция
val d = (a + b) * 10 // композиция на операции
val e = f(g(a)) // композиция на функции

Пренесохме възможността за тези операции върху ефекта Future
(и стойността в него)

• map – трансформация на единична стойност (напр. val c = -a)
• map2 (или zipMap) – трансформация на две независими стойности (val c = a + b). Резултатът c зависи от тях
• map3, zipMap3…; mapN дефинира зависимости
• flatMap – ефектна трансформация на единична стойност

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

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

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

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

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

h = g ∘ f

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

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

h ∘ g ∘ f

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

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

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

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

Нека
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) {
    val gOption = g(fOption.get)
    if (gOption != None){
      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

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

Монада за Option

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] =
    a => flatMap(f(a))(g)
}

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

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

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

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

  Нека m: F[A] и f: A => B, g: B => C. Тогава

  m.flatMap(f).flatMap(g) == m.flatMap(a => f(a).flatMap(g))

• ляв идентитет:

  ∀a: A и f: A => B е изпълнено: unit(a).flatMap(f) == f(a)

• десен идентитет:

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

for в Scala е монадна композиция

for {
  b <- f(a)
  c <- g(b * 2)
  d <- h(b + c)
} yield a * b * d

преобразува се до:

f(a).flatMap(b =>
  g(b * 2).flatMap(c =>
    h(b + c).map(d => a * b * d))
}

State монада

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

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

Еквиваленти в Cats

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

val listOfOptions = List(Some(1), None, Some(2))
Functor[List].compose[Option].map(listOfOptions)(_ + 1)

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

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

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

Нули на монади

mZero: F[A] наричаме нула за монадата F, ако:

MonadFilter

trait MonadFilter[F[_]] extends Monad[F] {
  def mzero[A]: F[A]
  def filter[A](m: F[A])(f: A => Boolean): F[A] =
    flatMap(m) { x => if (f(x)) unit(x) else mzero }
}

Functional Programming in Scala

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