Функциональное программирование

Type classes и абстракции для ФП

Naumen

План лекции

Теория категорий
Определение концепции type class
Пример применения type class
Monoid, Functor, Monad и другие абстракции
Примеры использования некоторых из изученных абстакций

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

Теоретическая основа применения универсальных методов для практически любых объектов и структур

Теория категорий для программистов

Type class

Type class представляет собой концепцию, паттерн, который позволяет добавлять поведение для типов без изменения самого типа.

В Scala, использование implicit class обеспечивает дополнительные удобство использования type class'ов.


implicit final class any2stringadd[A](private val self: A) extends AnyVal {
    def +(other: String): String = String.valueOf(self) + other
}

12 + "str"  // 12.+("str") // 12str

Type class

Пример

Создание новой библиотеки для сериализации данных в формат JSON.
Требования:

Базовые типы данных должны сериализоваться "из коробки".
Базовые коллекции (например: списки, массивы) должны также сериализоваться "из коробки".
Пользователи библиотеки должны иметь возможность определять процедуру сериализации для своих собственных типов данных.

Type class

Немного контекста для решаемой задачи

Сериализация – это процесс преобразования объекта или структуры данных в последовательность битов или строку, чтобы его можно было сохранить, передать, и позже возможно восстановить.

JSON - это текстовый формат обмена данными


case class UserData(name: String, age: Int, awards: List[String])
val gena = UserData("Gennady Korotkevich", 29, List("Codechef", "Rockethon", "VK CUP"))

{
    name: "Gennady Korotkevich",
    age: 29,
    awards: ["Codechef", "Rockethon", "VK CUP"]
}

Type class

Возможные варианты реализации

Один из вариантов реализации - создание трейта JsonSerializable с методом toJson. Все пользовательские классы должны наследовать этот трейт и реализовать функцию toJson в соответствии с их специфическими потребностями.


  trait JsonSerializable {
    def toJson: String
  }

  case class UserData(name: String, age: Int) extends JsonSerializable {
    override def toJson: String = ???
  }

  def serialize(value: JsonSerializable): String = value.toJson

Недостатки:

Не работает для базовых типов и коллекций (не можем подмешать trait)

Type class

Возможные варианты реализации

Для всех примитивных типов создать класс-обёртку, который умеет сериализировать данные.


  trait JsonSerializable {
    def toJson: String
  }

  case class StrJsonSerializer(str: String) extends JsonSerializable {
    override def toJson: String = s""""$str""""
  }

  def serialize(value: JsonSerializable): String = value.toJson

  serialize(StrJsonSerializer("Hello!"))

Недостатки:

Неудобно использовать

Type class

Решение с использованием type class

Напишем наш первый type class


  trait JsonSerializer[A] {
    def toJson(value: A): String
  }

Как можно видеть, type class - это параметризированный трейт, в котором описано, какие функции для некоторого типа А мы хотим добавить

Type class

Решение с использованием type class


  trait JsonSerializer[A] {
    def toJson(value: A): String
  }

  object JsonSerializerInstances {
    implicit val stringToJson: JsonSerializer[String] = new JsonSerializer[String] {
      override def toJson(value: String): String = s""""$value""""
    }

    implicit val intToJson: JsonSerializer[Int] = (value: Int) => value.toString

    implicit val booleanToJson: JsonSerializer[Boolean] = (value: Boolean) => value.toString

    implicit def listToJson[A : JsonSerializer]: JsonSerializer[List[A]] =
      (value: List[A]) => value.map(implicitly[JsonSerializer[A]].toJson).mkString("[", ",", "]")
  }

Type class

Решение с использованием type class

Реализация экземпляра JsonSerializer для пользовательского типа


  case class UserData(name: String, age: Int, married: Boolean)
  implicit val userDataToJson: JsonSerializer[UserData] = (value: UserData) => {
    val strToJ  = implicitly[JsonSerializer[String]]
    val intToJ  = implicitly[JsonSerializer[Int]]
    val boolToJ = implicitly[JsonSerializer[Boolean]]
    s"""{"name": ${strToJ.toJson(value.name)},
       "age": ${intToJ.toJson(value.age)},
       "married": ${boolToJ.toJson(value.married)}}"""
  }

Ключевое слово implicitly позволяет получить из implicit scope значение с необходимым типом.


  def implicitly[A](implicit value: A): A = value

Type class

Решение с использованием type class


  object JsonSerializer { // interface object
    def toJson[A](value: A)(implicit toJson: JsonSerializer[A]): String = toJson.toJson(value)
  }

  import JsonSerializerInstances._

  JsonSerializer.toJson("Hello")         // "Hello"
  JsonSerializer.toJson(List(1, 2, 3))   // [1,2,3]
  JsonSerializer.toJson(UserData("Max", 23, false))


  object JsonSerializerSyntax { // interface syntax
    implicit class JsonSerializerOps[A](value: A) {
      def asJson(implicit toJ: JsonSerializer[A]): String = toJ.toJson(value)
    }
  }

  import JsonSerializerInstances._
  import JsonSerializerSyntax._

  "Hello!".asJson
  false.asJson
  UserData("Max", 23, false).asJson

Type class

Собираем всё вместе


  trait JsonSerializer[A] { // type class
    def toJson(value: A): String
  }

  object JsonSerializerInstances { // type class instances
    implicit val intToJson: JsonSerializer[Int] = (value: Int) => value.toString

    implicit def listToJson[A: JsonSerializer]: JsonSerializer[List[A]] =
      (value: List[A]) => value.map(implicitly[JsonSerializer[A]].toJson).mkString("[", ",", "]")

    // и т.д.
  }

  object JsonSerializer { // interface object
    def toJson[A](value: A)(implicit toJson: JsonSerializer[A]): String = toJson.toJson(value)
  }

  object JsonSerializerSyntax { // interface syntax
    implicit class JsonSerializerOps[A](value: A) {
      def asJson(implicit toJ: JsonSerializer[A]): String = toJ.toJson(value)
    }
  }

  JsonSerializer.toJson(UserData("Max", 23, false))
  UserData("Max", 23, false).asJson

Type class

Type class для Higher kinded types


  trait Searchable[F[_]] {
    def findValue[A](fa: F[A])(f: A => Boolean): F[A]
  }

  implicit val listInstance: Searchable[List] = new Searchable[List] {
    override def findValue[A](fa: List[A])(f: A => Boolean): List[A] =
      fa.find(f).toList
  }

  implicit class ListOps[A](val self: List[A]) {
    def findValue(f: A => Boolean)(implicit se: Searchable[List]): List[A] =
      se.findValue(self)(f)
  }

  List(1, 2, 3, 4).findValue(_ == 3)  // List(3)
  implicitly[Searchable[List]].findValue(List(1, 2, 3))(_ == 3)  // List(3)

абстракции

Дисклеймер

Дальнейшие определения и названия type class взяты из cats

Cats - это библиотека предоставляющая абстракции для ФП

Semigroup (полугруппа)

Математика: множество с заданной на нём ассоциативной бинарной операцией

Для нас важно: Описывает возможность комбинации элементов одного типа


    trait Semigroup[A] {
        def combine(x: A, y: A): A
    }

Для операции в combine необходимо выполнение ассоциативности


def associativeLaw[A](x: A, y: A, z: A)(implicit m: Monoid[A]): Boolean = {
    m.combine(x, m.combine(y, z)) == m.combine(m.combine(x, y), z)
}

Monoid (моноид)

Математика: полугруппа с нейтральным элементом

Для нас важно: возможность обобщить ещё больше алгоритмов


trait Monoid[A] extends Semigroup[A] {
    def empty: A
}

Свойство нейтрального элемента


def identityLaw[A](x: A)(implicit m: Monoid[A]): Boolean = {
    (m.combine(x, m.empty) == x) && (m.combine(m.empty, x) == x)
}

Monoid (моноид)

Зададим несколько моноидов


  implicit val intMonoid: Monoid[Int] = new Monoid[Int] {
    override def empty: Int = 0
    override def combine(x: Int, y: Int): Int = x + y
  }

  implicit val doubleMonoid: Monoid[Double] = new Monoid[Double] {
    override def empty: Double = 1
    override def combine(x: Double, y: Double): Double = x * y
  }

  implicit val booleanMonoid: Monoid[Boolean] = new Monoid[Boolean] {
    override def empty: Boolean = false
    override def combine(x: Boolean, y: Boolean): Boolean = x || y
  }

Для одного типа данных может множество вариантов моноида

Functor (функтор)

Математика: особый морфизм между категориями, сохраняющий структуру

Для нас важно: возможность единообразно описывать изменения


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

Для функтора должны выполняться два закона:


    fa.map(x => x) == fa                       // Identity

    fa.map(x => g(f(x))) == fa.map(f).map(g)   // Composition

В Scala функторы это: Seq, Option, Future, Either...

Applicative functor (аппликативный функтор)

Для нас важно: теперь мы можем любое значение занести в F[...]


    trait Applicative[F[_]] extends Functor[F] {
        def pure[A](value: A): F[A]
    }

Так же аппликативный функтор позволяет к F[A] применить функцию F[A => B] и получить F[B]


    trait Applicative[F[_]] extends Functor[F] {
        def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]
    }

В Scala аппликативные функторы это: Seq, Option, Future, Either...

Пример

Map-Reduce с помощью Functor и Monoid

Модель MapReduce используется в распределённых вычислениях при параллельных вычислениях над большим количеством данных.

Решает задачу: преобразовать входные данные, к преобразованным данным применить некую функцию-свёртку, дающую искомый ответ. Как пример, посчитать количество одинаковых слов в тексте. Разбить текст на отдельные слова - шаг map. Посчитать количество слов - шаг reduce.

Процесс вычисления:

На вход поступает набор данных
Разделяем этот набор на батчи (количество батчей - количество вычисляющих устройств)
В параллель для каждого батча запускаем обработку данных (шаг map)
Параллельно запускаем функцию-свёртку на всех батчах (шаг reduce)
Запускаем функцию-свёртку над результатами из батчей
PROFIT!

Пример

Map-Reduce с помощью Functor и Monoid

Для начала напишем функцию, которая принимает батч данных и функцию-обработчик.

Функция-свёртка определяется моноидом.

Функция mapFold должна возвращать результат применения функции свёртки на все преобразованные элементы из изначального набора данных.


import cats._
import cats.implicits._

object MapReduce extends App {
    def mapFold[A, B : Monoid](values: Vector[A])(f: A => B): B =
    values.foldLeft(implicitly[Monoid[B]].empty) { (acc, elem) => acc |+| f(elem) }
}

Пример

Map-Reduce с помощью Functor и Monoid

Теперь напишем функцию mapReduce, которая для набора данных будет запускать параллельные вычисления


import cats._
import cats.implicits._
import scala.concurrent.{Await, Future}
import scala.concurrent.ExecutionContext.Implicits.global
import scala.concurrent.duration.DurationInt

object MapReduce extends App {
  def mapFold[A, B : Monoid](values: Vector[A])(f: A => B): B =
    values.foldLeft(Monoid[B].empty) { (acc, elem) => acc |+| f(elem) }

  def mapReduce[A, B: Monoid](values: Vector[A])(func: A => B): Future[B] = {
    val corsCount = Runtime.getRuntime.availableProcessors
    val batches = values.grouped((1.0 * values.size / corsCount).ceil.toInt).toVector
    val computedBatches: Vector[Future[B]] = batches.map(batch => Future(mapFold(batch)(func)))
    Future.sequence(computedBatches).map(results => mapFold(results)(identity))
  }

  println(Await.result(mapReduce(Range(1, 10000).toVector)(identity), 1.seconds))
}

Пример

Map-Reduce с помощью Functor и Monoid

А что если обобщить еще?


import cats._
import cats.implicits._
import scala.concurrent.{Await, Future}
import scala.concurrent.ExecutionContext.Implicits.global
import scala.concurrent.duration.DurationInt

object MapReduce extends App {
  def mapReduce[A, B: Monoid](values: Vector[A])(func: A => B): Future[B] = {
    val numCores = Runtime.getRuntime.availableProcessors
    val groupSize = (1.0 * values.size / numCores).ceil.toInt
    values
      .grouped(groupSize)
      .toVector
      .traverse { group => // traverse идёт из type class Traverse
        Future(group.foldMap(func)) // foldMap идёт из type class Foldable
      }
      .map(_.combineAll) // combineAll так же идёт из Foldable
  }

  Await.result(mapReduce((1 to 1000).toVector)(identity), 1.second)
}

Monad (монада)

Для нас важно: map, flatMap и pure позволяют удобно работать с for comprehension,

возможность практически любые вычисления представить как композицию функций


    trait Monad[F[_]] extends Applicative[F] {
        def flatMap[A, B](value: F[A])(f: A => F[B]): F[B]
    }

    trait Monad[F[_]] {
        def pure[A](value: A): F[A]
        def flatMap[A, B](value: F[A])(f: A => F[B]): F[B]
        def map[A, B](fa: F[A])(f: A => B): F[B] =
            flatMap(fa)(x => pure(f(x)))
    }

Отметим, что любая монада автоматически является и функтором

Монадические законы

Монада должна удовлетворять трём законам:


    pure(a).flatMap(f) == f(a) // Left identity

    m.flatMap(pure) == m // Right identity

    m.flatMap(f).flatMap(g) == m.flatMap(x => f(x).flatMap(g)) // Associativity

Использование монад

Отметим, что Option, Either, List и ещё целый ряд базовых коллекций являются монадами.


  Option(12).flatMap(x => Some(x + 12)) // Some(24)

  Right(12).flatMap(x => Right(x + 12)) // Right(24)

  List(1, 2, 3).flatMap(x => List(x, 12)) // List(1, 12, 2, 12, 3, 12)

Использование монад

Существует множество разных монад, каждая из которых призвана решать свою задачу.

Например, монада Writer[W, A] используется для логирования. Тип W - логи, A - результат вычислений


  type Logged[A] = Writer[List[String], A]

  val res = for {
    v1 <- 12.pure[Logged]
    _ <- List("Obtain the first value").tell
    v2 <- 21.writer(List("Obtain the second value"))
    _ <- List("Got both").tell
  } yield v1 + v2

  print(res.run)
  // (List(Obtain the first value, Obtain the second value, Got both),33)

Использование монад

Ещё один пример, это монада State[S, A]. Она позволяет нести в своём контексте состояние.

Подобное поведение позволяет сымитировать мутабельное состояние без использования действительных мутаций


  val p: State[Int, (Int, Int, Int)] = for {
    a <- get[Int]
    _ <- set[Int](a + 1)
    b <- get[Int]
    _ <- modify[Int](_ + 4)
    c <- inspect[Int, Int](_ * 100)
  } yield (a, b, c)

  println(p.run(1).value)
  // (6,(1,2,600))

Использование монад

Отдельно остановимся на монаде IO[A]. Эта монада позволяет описывать сайд эффекты как

чистые значения, которые способны выражать как синхронные, так и асинхронные вычисления.

В функциональных библиотеках (ZIO, monix) есть аналог этой монады.

По своей сути IO является только описанием тех вычислений, которые должны произойти.


    val sideEffect = IO { println("side effect!") } // в консоль ничего не выводится

    val program: IO[Unit] = for {
         _ <- sideEffect
         _ <- sideEffect
      } yield () // и тут ничего в консоль не выводится

    program.unsafeRunSync() // чтобы описание программы начало выполняться, необходимо напрямую его запустить

И ещё пара type classов

Foldable


  trait Foldable[F[_]] extends UnorderedFoldable[F] with FoldableNFunctions[F] {
    def foldLeft[A, B](fa: F[A], b: B)(f: (B, A) => B): B
    def foldRight[A, B](fa: F[A], lb: Eval[B])(f: (A, Eval[B]) => Eval[B]): Eval[B]
  }

Foldable это List, Option, Map.

Foldable автоматически предоставляет ещё ряд полезных функций:


  def find[A](fa: F[A])(f: A => Boolean): Option[A]
  def exists[A](fa: F[A])(p: A => Boolean): Boolean
  def maximumOption[A](fa: F[A])(implicit A: Order[A]): Option[A]
  def maximumByOption[A, B: Order](fa: F[A])(f: A => B): Option[A]
  def foldMap[A, B](fa: F[A])(f: A => B)(implicit B: Monoid[B]): B
  def toList[A](fa: F[A]): List[A]

И ещё пара type classов

Traverse


  trait Traverse[F[_]] extends Functor[F] with Foldable[F] with UnorderedTraverse[F] {
    def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]
  }

Traverse позволяет поменять контексты местами или обернуть контекст в дополнительный контекст


  val example: List[Option[Int]] = Option(1).traverse(x => List(x))

  val listOfFuture: List[Future[Int]] = List(Future.successful(1), Future.successful(2))
  val futureOfLists: Future[List[Int]]= Future.sequence(listOfFuture)
  val futureOfLists2: Future[List[Int]]= listOfFuture.sequence
  val futureOfLists3: Future[List[Int]]= listOfFuture.traverse(identity)

А сколько вообще type class'ов?

Полезные ссылки

Type classes
Higher-kinded types
Scala with cats 2
IO monad for cats
Cats Effect