Классические абстракции используемые в ФП

Это продолжение статьи про имплиситы и тайпклассы в Scala (если вы не знакомы с ними, то предлагаю начать с предыдущей статьи). А в этой статье:

• Рассмотрим классические примеры тайпклассов и их свойства
• Увидим, как писать максимально обобщенный код на Scala

---

Начнем с самых простых для понимания абстракций (и поскольку мы будем говорить об абстракциях, важно держать в уме, что мы будем заниматься обобщением кода).

Semigroup

Что общего между этими тремя строками?

1 + 2 + 3
 
"I" + "love" + "fp"
 
List(1, 2, 3) ++ List(4, 5, 6)

Если присмотреться, то во всех трёх случаях у нас есть бинарные операции: складываем числа, склеиваем строки, объединяем списки. Как мы можем обобщить эти операции? Тут к нам на помощь приходят полугруппы. Это такая абстракция, которая позволяет комбинировать объекты одного типа.

trait Semigroup[A] {
	def combine(x: A, y: A): A
}
 
Semigroup[Int].combine(1, 2) // 3

Метод combine так же выражают следующим синтаксисом.

object SemigroupSyntax {  
  implicit class SemigroupOps[A](private val a: A) extends AnyVal {
    def |+|(b: A)(implicit s: Semigroup[A]): A = s.combine(a, b)  
  }  
}

Этот синтаксис позволит писать такой код:

1 |+| 2 |+| 3

Простые примеры инстансов полугруппы для сложения чисел, строк и списков:

implicit val semigroupInt: Semigroup[Int] = new Semigroup[Int] {  
	override def combine(x: Int, y: Int): Int = x + y  
}
  
implicit val semigroupString: Semigroup[String] = new Semigroup[String] {  
	override def combine(x: String, y: String): String = x + y  
}
 
implicit def semigroupList[A]: Semigroup[List[A]] = new Semigroup[List[A]] {  
	override def combine(x: List[A], y: List[A]): List[A] = x ::: y  
}

И примеры использования:

1 |+| 2 |+| 3
// result: 6
 
"Hello" |+| " " |+| "world!"
// result: Hello world!
 
List(1, 2) |+| List(3, 4) |+| Nil
// result: List(1, 2, 3, 4)

Главное свойство полугруппы: операция должна быть ассоциативной. То есть, если у нас есть три элемента, объединять их можно как в порядке (A |+| B) |+| C, так и A |+| (B |+| C), и результат всегда должен быть один и тот же. Это особенно важно для работы с коллекциями и параллельными вычислениями. Если порядок выполнения не важен, можно разбивать задачи на подзадачи и выполнять их независимо, а потом собрать результат. То есть полугруппы помогают формально описать, как объединять элементы так, чтобы результат не зависел от порядка операций.

Но с полугруппами есть одна проблемка, с которой мы столкнемся если попробуем реализовать функцию со следующей сигнатурой, которая комбинирует все элементы списка:

def combineAll[A: Semigroup](list: List[A]): A = {
  list.foldLeft(???)(_ |+| _)
}

Что, если список пустой? Что возвращать в этом случае? У Semigroup нет значения по умолчанию, и это нас подводит к следующей абстракции — Monoid.

---

Monoid

Моноид — это полугруппа с нейтральным элементом. Monoid расширяет Semigroup, добавляя понятие нейтрального элемента - в нашем случае он называется empty. Этот элемент действует как “нулевой” элемент для операции combine.

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

Практическая польза нейтрального элемента выражается в сценариях, когда, например, мы можем попытаться найти сумму значений в списке, который может быть пустым. В этом случае Monoid[A].empty будет служить разумным и безопасным значением по умолчанию.

def combineAll[A: Monoid](list: List[A]): A = {
  list.foldLeft(Monoid[A].empty)(_ |+| _)
}
 
combineAll(List(1, 2, 3))
// result: Int = 6
 
combineAll(List.empty[Int])
// result: Int = 0

Свойства моноида:

• Associativity - (A |+| B) |+| C = A |+| (B |+| C)
• Left identity - Monoid[A].empty |+| x = x
• Right identity - x |+| Monoid[A].empty = x

Свойства identity гарантируют, что нейтральный элемент действительно нейтрален и не вносит никаких изменений в другие элементы моноида при выполнении операции. Это обеспечивает предсказуемость в использовании моноидов для различных вычислительных задач, таких как свёртка коллекций, агрегация данных и т.д.

---

Functor

Мы уже знакомы с такими типами, как Option, List, Either, Seq и другими. У всех них есть метод map, который позволяет применять функцию к значению внутри контейнера, не извлекая его наружу. Например, с Option можно трансформировать значение, если оно есть, а с List — применить функцию ко всем элементам.

Но что, если мы захотим написать обобщенный метод, который работает с любым из этих типов, а не только с конкретным Option или List? Вот тут-то и появляется функтор — абстракция, которая объединяет такие структуры под единый интерфейс.

Вот его простая, но мощная сигнатура:

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

Проще говоря, функтор позволяет нам трансформировать значения, которые находятся внутри некоторого F[_]. Что за F[_], спросите вы? Хороший вопрос!

Higher-Kinded Types

Такие типы как List, Option, Seq. Это примеры контейнеров, которые могут хранить в себе значения с другими типами. В Scala F[_] — это обобщенный тип высшего порядка (Higher-Kinded Type, HKT), который принимает другой тип в качестве параметра.

Примеры:

• List[Int], List[String], List[Double] — это списки с разными типами данных.
• Option[Int], Option[String] — это опциональные значения, которые могут быть Some(value) или None.

F[_] еще обычно называют F с дыркой

Возвращаясь к функтору

Можно сказать, что функтор позволяет нам «заглянуть» внутрь этой коробки и применить функцию A => B к её содержимому, не извлекая его.

Method	From	Given	To
map	F[A]	A => B	F[B]

Посмотрим, как можно писать обобщенный код, используя функтор:

import FunctorInstances._  
import FunctorSyntax._
 
def checkMeaningOfLife(num: Int): String = {  
  if (num == 42) s"$num is meaning of life"
  else s"$num isn't meaning of life"
}
 
// Функция работает с некоторым F[_], который является функтором
def functorUsingExample[F[_]: Functor](numF: F[Int]): F[String] = {  
  numF
    .map(checkMeaningOfLife)
    .map(_.toUpperCase)
    .map(_ + "!")
}
 
// Функция может принимать на вход Option, который является функтором
functorUsingExample(Some(42)) // Some(42 IS MEANING OF LIFE!)  
functorUsingExample(None)     // None  
  
// Или List
functorUsingExample(List(1, 2, 42))  
// List(  
//   "1 ISN'T MEANING OF LIFE!",  
//   "2 ISN'T MEANING OF LIFE!",  
//   "42 IS MEANING OF LIFE!"  
// )

В этом примере мы видим, что F[Int] может быть List, Option или чем-то еще — главное, чтобы оно было функтором! Мы просто последовательно вызываем map, выстраивая цепочку вычислений и трансформируем данные.

Свойства функтора

Свойство identity

identity - это функция, которая возвращает свой единственный аргумент не изменяя его.

def identity[A](a: A): A = a

Смысл свойства в том, что если применить identity, то результат должен остаться тем же:

fa.map(a => a) == fa
// или
fa.map(identity) == fa

Свойство композиции

Два последовательных map должны быть эквивалентны одному map с композицией функций:

fa.map(g(f(_))) == fa.map(f).map(g)

---

Foldable

Представьте, что у нас есть набор данных: список чисел или, может быть, даже что-то более экзотическое. Нам нужно как-то пробежаться по этой структуре и свести её к единственному значению — например, посчитать сумму элементов.

Вот несколько примеров кода, которые вы, скорее всего, уже видели:

Vector(1, 2, 3).foldLeft(0)(_ + _)  
List(1, 2, 3).foldLeft(0)(_ + _)  
Some(1).foldLeft(0)(_ + _)  

Но что, если мы хотим обобщить эту идею и сделать так, чтобы любая структура данных могла “свернуться” предсказуемым образом?

Здесь на сцену выходит абстракция Foldable:

trait Foldable[F[_]] {  
  def foldLeft[A, B](fa: F[A], b: B)(f: (B, A) => B): B  
}

Этот тайпкласс говорит нам: “Дайте мне структуру F[A], стартовое значение B и функцию комбинирования (B, A) => B, и я аккуратно сложу всё в один результат!“.

Вообще у Foldable есть два метода:

• foldLeft пробегается по структуре слева направо, накапливая результат.
• foldRight (который мы здесь подробно не рассматриваем) пробегается справа налево.

Foldable позволяет обрабатывать коллекции, Option, Either и даже более сложные структуры данных единообразным способом.

Чуть выше, когда рассматривали моноид, у нас был пример c функцией combineAll, которая принимала на вход List.

def combineAll[A: Monoid](list: List[A]): A = {
  list.foldLeft(Monoid[A].empty)(_ |+| _)
}

Мы можем переписать эту функцию, абстрагировавшись от List, оперируя некоторым F[_], который является Foldable:

def combineAll[F[_]: Foldable, A: Monoid](as: F[A]): A = {
  as.foldLeft[A](Monoid[A].empty)(_ |+| _)
}
 
// Обобщенная функция может принимать на вход все, что является Foldable
combineAll(List(1, 2, 3, 4, 5))
combineAll(Vector(1, 2, 3, 4, 5))
combineAll(Option(42))

Теперь, метод combineAll работает с любой структурой данных, которая является Foldable.

---

Applicative

У апликатива есть два метода.

Method	From	To
pure	A	F[A]
product	(F[A], F[B])	F[(A, B)]

Оборачиваем чистые значения

Мы уже знаем, как работать с вычислениями, которые находятся в каком-то контексте F[_]. Но возникает логичный вопрос: а как вообще поместить чистое значение в этот самый контекст?

Посмотрите на привычные нам структуры данных: List, Option, Either. Каждая из них предлагает свой способ “обернуть” чистое значение в свой контекст. Хотелось бы, чтобы существовал общий механизм для этой задачи. И вот тут на сцену выходит Applicative!

Applicative — это тайпкласс, который расширяет Functor и предоставляет нам операцию pure:

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

Метод pure берёт значение и просто помещает его в контекст F[_]. Благодаря этому мы можем работать с “чистыми” значениями внутри контекста, что важно для дальнейших операций.

Давайте посмотрим на pure в деле. Создадим инстансы Applicative для Option и List:

object ApplicativeInstances {  
  implicit val optionApplicative: Applicative[Option] = new Applicative[Option] {  
    override def pure[A](a: A): Option[A] = Some(a)
  }  
  
  implicit val listApplicative: Applicative[List] = new Applicative[List] {  
    override def pure[A](a: A): List[A] = a :: Nil
  }  
}  

Теперь сделаем использование pure удобнее с помощью имплиситного класса:

object ApplicativeSyntax {  
  implicit class ApplicativeOps[A](private val a: A) extends AnyVal {  
    def pure[F[_]](implicit applicative: Applicative[F]): F[A] = applicative.pure(a)  
  }  
}

Теперь можно писать так:

import ApplicativeSyntax._  
import ApplicativeInstances._  
 
42.pure[Option]    // Some(42)
"Hello".pure[List] // List("Hello")

Красиво и лаконично, не так ли?

Как комбинировать независимые вычисления?

product

Когда мы работаем с вычислениями мы можем разделить их на две категории:

• зависимые друг от друга (если одно вычисление зависит от результата другого)
• и независимые

Сейчас нас интересуют независимые вычисления.

Какие вычисления мы можем назвать независимыми? Представьте, что вы готовите завтрак. Пока чайник кипятит воду, вы готовите омлет. Эти два действия происходят независимо, но их результат нужен одновременно — завтрак должен быть готов к определенному моменту.

Точно так же в программировании часто встречаются независимые вычисления. Например, нужно одновременно загрузить профиль пользователя из базы данных и список его друзей из внешнего API. Каждое из этих действий может выполняться отдельно, но в итоге нам нужен результат обоих сразу.

Как комбинировать такие вычисления? Вот тут-то и приходит на помощь product из Applicative!

trait Applicative[F[_]] extends Functor[F] {
  def pure[A](a: A): F[A]
  def product[A, B](fa: F[A], fb: F[B]): F[(A, B)]
}

Applicative расширяет Functor и добавляет возможность работать с независимыми вычислениями. Его метод product позволяет объединять два значения из одного контекста F[_] в один новый контекст, не изменяя сами значения.

Если у нас есть F[Int] и F[String], то скомбинировав с помощью product мы получим F[(Int, String)].

Реализация для Option:

override def product[A, B](fa: Option[A], fb: Option[B]): Option[(A, B)] = {
  (fa, fb) match {  
    case (Some(a), Some(b)) => Some((a, b))  
    case _ => None  
  }
}

Используем его на практике:

// Метод, возвращает температуру по названию города
def getTemperature[F[_]: Applicative](city: String): F[Temperature] = {
  city match {
    case "Moscow"        => Applicative[F].pure(Temperature(-5))
    case "Yekaterinburg" => Applicative[F].pure(Temperature(-10))
    case "Sochi"         => Applicative[F].pure(Temperature(15))
  }
}
 
// Комбинируем два независимых вычисления с Option
Applicative[Option].product(
  getTemperature[Option]("Moscow"),
  getTemperature[Option]("Sochi")
)
// Результат: Some((Temperature(-5.0),Temperature(15.0)))
 
 
// Комбинируем два независимых вычисления с Try
Applicative[Try].product(
  getTemperature[Try]("Moscow"),
  getTemperature[Try]("Sochi")
)
// Результат: Success((Temperature(-5.0),Temperature(15.0)))

В некоторых реализациях product может работать параллельно! Например, если мы загружаем данные из двух разных сервисов, product может запустить оба запроса одновременно и собрать их результаты.

mapN

Метод product отлично справляется с объединением двух независимых вычислений. Но что, если нам нужно объединить три или больше? Например, получить температуру в трех городах одновременно?

Конечно, можно было бы цепочкой применять product:

val combined = Applicative[Option].product(
  getTemperature[Option]("Moscow"),
  Applicative[Option].product(
    getTemperature[Option]("Sochi"),
    getTemperature[Option]("Yekaterinburg")
  )
)

Но такой код становится неудобным и плохо читаемым. Нам нужно обобщенное решение.

Вместо того чтобы вручную комбинировать результаты, можно воспользоваться mapN, который под капотом выражается через product. Он принимает произвольное количество аргументов и применяет к ним функцию:

import cats.syntax.apply._
 
val result = (
  getTemperature[Option]("Moscow"),
  getTemperature[Option]("Sochi"),
  getTemperature[Option]("Yekaterinburg")
).mapN { (t1, t2, t3) =>
  (t1.value + t2.value + t3.value) / 3 // Средняя температура
}

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

Таким образом, product и mapN позволяют нам элегантно комбинировать независимые вычисления.

Свойства Аппликатива

Свойство	Выражение
Associativity	fa.product(fb).product(fc) ~ fa.product(fb.product(fc))
Right identity	fa.product(().pure) ~ fa
Left identity	().pure.product(fa) ~ fa

---

Traverse

Мы уже знаем, как аппликативно комбинировать фиксированный набор независимых вычислений:

• product комбинирует два вычисления.
• mapN позволяет комбинировать произвольный набор вычислений, но он должен быть известен на этапе компиляции.

А что, если нам нужно скомбинировать список вычислений и размер этого списка известен только в рантайме? Допустим, у нас есть список городов и для каждого из них нужно получить температуру:

val cities = List("Moscow", "Sochi", "Yekaterinburg")

Мы могли бы использовать map:

val temperatures: List[Option[Temperature]] = cities.map(getTemperature[Option])

Но тогда получим список опшинов, то есть обобщая получим список вычислений List[F[Temperature]], тогда как нужен список температур к некотором контексте F[List[Temperature]] чтобы дальше с ним что-то делать (например, вычислить среднюю температуру).

Тайпкласс Traverse позволяет работать с коллекцией независимых вычислений, сохраняя их порядок и объединяя их в один контейнер.

trait Traverse[F[_]] {  
  def traverse[F[_]: Applicative, G[_]: Traverse, A, B](ga: G[A])(f: A => F[B]): F[G[B]]
}

Что здесь происходит?

• G[A] — это коллекция элементов (например, List[String]).
• F[B] — это асинхронный или обернутый результат (например, Option[Temperature]).
• traverse применяет функцию f: A => F[B] к каждому элементу, объединяя все результаты в один F[G[B]].

Пример использования:

import cats.Applicative
import cats.syntax.applicative._
import cats.syntax.traverse._
 
val cities = List("Moscow", "Sochi", "Yekaterinburg")
 
val temperatures: Option[List[Temperature]] = cities.traverse(city => getTemperature[Option](city))
 
println(temperatures) // Some(List(Temperature(-5.0), Temperature(15.0), Temperature(-10.0)))

Здесь traverse:

1. Проходит по List[String].
2. Вызывает getTemperature[Option] для каждого города.
3. Объединяет результаты в Option[List[Temperature]].

То есть traverse — это некоторое обобщение mapN, позволяющее работать со списком независимых вычислений, не зная их размер заранее.

---

ApplicativeError

Мы уже знаем, как:

• Комбинировать вычисления (map, product, mapN, traverse).
• Оборачивать чистые значения в контекст (pure).

Но что, если в наших вычислениях что-то пойдет не так? Например, операция деления может завершиться с ошибкой. В императивном коде мы бы использовали try-catch, но в функциональном программировании есть специальные типы, которые позволяют безопасно работать с ошибками, например Either и Try.

Either — это распространенный способ представления ошибок. Он имеет две части:

• Left[E] — ошибка (E).
• Right[A] — успешный результат (A).

def parseIntEither(s: String): Either[String, Int] =  
  if (s.matches("-?\\d+")) Right(s.toInt)  
  else Left(s"Invalid number: $s")  
 
println(parseIntEither("42"))  // Right(42)  
println(parseIntEither("abc")) // Left("Invalid number: abc")  

Другой вариант — Try, который оборачивает результат в Success или Failure:

import scala.util.{Try, Success, Failure}
 
def parseIntTry(s: String): Try[Int] = Try(s.toInt)
 
println(parseIntTry("42"))  // Success(42)  
println(parseIntTry("abc")) // Failure(java.lang.NumberFormatException)

Но у нас ведь обобщенный код, который должен работать с разными типами высшего порядка. Как выразить обработку ошибок абстрактно?

Вот тут появляется ApplicativeError — тайпкласс, который расширяет Applicative работой с ошибками:

trait ApplicativeError[F[_], E] extends Applicative[F] {  
 
  def raiseError[A](e: E): F[A]  // Вернуть ошибку
  
  def handleErrorWith[A](fa: F[A])(f: E => F[A]): F[A]  // Обработать ошибку  
}

Пример инстанса ApplicativeError для Either

implicit def eitherApplicativeError[E]: ApplicativeError[Either[E, *], E] = new ApplicativeError[Either[E, *], E] {
  override def raiseError[A](e: E): Either[E, A] = Left(e)
  override def handleErrorWith[A](fa: Either[E, A])(f: E => Either[E, A]): Either[E, A] = fa match {
    case Left(error) => f(error)
    case success     => success
  }
  // ...
}

Пример инстанса ApplicativeError для Try

implicit val tryApplicativeError: ApplicativeError[Try, Throwable] = new ApplicativeError[Try, Throwable] {
  override def raiseError[A](e: Throwable): Try[A] = Failure(e)
  override def handleErrorWith[A](fa: Try[A])(f: Throwable => Try[A]): Try[A] = {
    fa match {
      case Failure(exception) => f(exception)
      case success            => success
    }
  }
  // ...
}

Рассмотрим уже знакомую нам функцию getTemperature, которая возвращает температуру для заданного города. Тут мы используем ApplicativeError, чтобы вернуть ошибку, если город не найден.

def getTemperature[F[_]](city: String)(implicit ae: ApplicativeError[F, Throwable]): F[Temperature] = {
  city match {
    case "Moscow"        => Temperature(-5).pure[F]
    case "Yekaterinburg" => Temperature(-10).pure[F]
    case "Sochi"         => Temperature(15).pure[F]
    case unknown         => ApplicativeError[F, Throwable].raiseError(new Throwable(s"City $unknown wasn't found"))
  }
}

Наш код не завязан на Try или Either — он работает с любым типом, который является ApplicativeError.

// Either examples
type EitherTh[A] = Either[Throwable, A]
 
val moscowEither: EitherTh[Temperature] = getTemperature[EitherTh]("Moscow")
println(moscowEither) // Right(Temperature(-5.0))
 
val kaliningradEither: EitherTh[Temperature] = getTemperature[EitherTh]("Kaliningrad")
println(kaliningradEither) // Left(java.lang.Throwable: City Kaliningrad wasn't found)
 
// Пример обработки ошибки
kaliningradEither.handleErrorWith {
  error: Throwable =>
    println(s"Error: $error") // например, залогировали
    Temperature(0).pure[Try]  // и вернули что-то по-умолчанию
}

Таким образом, ApplicativeError позволяет выбрасывать и обрабатывать ошибки в обобщенном коде, абстрагируясь от конкретных реализаций, таких как Try, Either и других типов, делая код гибче и удобнее.

---

Заключение

В этом посте мы рассмотрели основные строительные блоки функционального программирования: полугруппы, моноиды, функторы, foldable, аппликативы, traverse и ApplicativeError. Эти абстракции позволяют писать функциональный код, абстрагируясь от конкретных типов, что делает код гибким.

Все эти типы и абстракции можно найти в библиотеке cats. Так же, советую почитать книгу Scala with Cats. Это отличное введение, чтобы понять базовые концепции ФП и научиться писать чистый и функциональный код.