При слове "полиморфизм" сразу вспоминается объектно-ориентированное программирование, в котором полиморфизм является одним из столпов (Полиморфизм для начинающих). (Причём, по-видимому, более важным, чем другие столпы.) Оказывается, что можно достичь сходного эффекта и другим путём, который в ряде случаев оказывается более предпочтительным. Например, с помощью классов типов можно приписать новые возможности уже существующим типам, у которых нельзя изменить предка, или, используя тип данных с несовместимыми классами, "решить" проблему множественного наследования.

На Хабре уже есть несколько публикаций, дающих представление о классах типов:

1. @IvanGolovach Разработка > "FP на Scala: Что такое функтор?" — 2015.
   Здесь затрагиваются классы типов при рассмотрении функторов. В ходе рассмотрения приводятся несколько примеров классов типов.
2. Михаил Потанин @potan Разработка > "Классы типов на C++" — 2013.
   В этой публикации реализуют классы типов в C++. По-видимому, предполагается, что читатель в какой-то степени уже знаком с type class'ами, поэтому собственно про классы типов сказано не очень много.
3. @VoidEx Разработка > "Классы типов, монады" — 2009.
   Описаны классы типов в Haskell (с примерами реализации на С++).
4. @IvanP Разработка > "Полиморфия и классы в Haskell" — 2013.
   Описан параметрический и ad-hoc полиморфизм, классы типов и несколько стандартных классов. Всё описание сделано для языка Haskell.
5. update: @vuspenskiy Разработка > Type classes в Scala — 2012.
   Коротко описан способ использования классов типов через implicit'ы на примере Comparator[T].

В этом посте хотелось бы отразить взгляд на классы типов как на один из повседневных инструментов программистов. Причём, если в Haskell'е без них вообще не обойтись, то в Sсala можно прекрасно сносно жить, не зная об их существовании. Однако, при ближайшем рассмотрении оказывается, что такой инструмент весьма полезен при написании повторно используемых программ. Кроме того, есть целый ряд универсальных библиотек, которые основаны на этом инструменте, и, чтобы ими пользоваться, также надо понимать классы типов.

Неизменяемые типы данных

В функциональном программировании широкую популярность приобрели неизменяемые типы данных. Так как данные не могут произвольно меняться, то нет причины их скрывать, и вместо сокрытия данных теперь используются открытые типы, где данные — публичны. (Тем самым, среди трёх столпов ООП — полиморфизма, наследования и инкапсуляции, — один оказывается несколько задвинут в сторону.)
Свободно доступные данные позволяют использовать внешние алгоритмы их обработки. Нет необходимости привязывать алгоритмы к самому объекту и преодолевать искусственные барьеры между объектами, если алгоритм обработки использует несколько разнотипных объектов.

Оказывается, что значительная часть множества структур данных может быть смоделирована с использованием всего двух механизмов (Алгебраические типы данных). Во-первых, создание записей или кортежей ("тип-произведение"). Во-вторых, создание альтернативных реализаций одного родительского типа — enum, наследование интерфейсов, sealed trait — "тип-сумма".

Пример:

// тип-сумма следующих альтернативных реализаций:
sealed trait Form
object Form {
  //  тип-произведение String X String
  case class Form1(number: String, title: String) extends Form 
  // тип-произведение UUID X String X Int
  case class Form2(id: UUID, documentation: String, count: Int) extends Form
  // == Unit (тривиальное произведение нулевого количества типов)
  case object BadForm extends Form
}

Как можно видеть, такие алгебраические типы данных не подразумевают сокрытия данных, и наличия каких-либо встроенных методов. Все данные доступны напрямую, а обрабатывать мы можем эти типы внешними алгоритмами, например, такими:

• сформировать HTML-представление для пользователя
• выполнить валидацию по бизнес-правилам
• сериализовать/десериализовать
• рассчитать некоторые метрики
• ...

Все эти виды обработки реализуются обособленно и не обязаны ничего знать друг о друге. В таких алгоритмах основным способом обработки различных подтипов с доступам к реальным данным является pattern-matching. С помощью pattern-matching'а мы одновременно проверяем какого конкретного подтипа объект, и извлекаем значения интересующих нас полей.

Размещение алгоритмов вне конкретных типов обладает следующими преимуществами:

1. Логика алгоритма не размазывается по каждому подтипу, а локализована в отдельном модуле.
2. Логика одного способа обработки не перемешана с другими способами обработки внутри каждого класса данных. Упрощается поддержка разных алгоритмов разными разработчиками.
3. Нет необходимости добавлять зависимость от библиотеки СУБД к модулю, в котором объявляется модель данных.
4. Легко добавить новые методы обработки к существующим типам данных. Они добавляются "ортогонально" в независимых модулях.

Классы типов

Предположим, мы реализовали некоторый алгоритм вне наших типов данных. Если в этом алгоритме прямо используются наши типы, то мы не сможем его использовать повторно для других похожих данных. Это, с одной стороны, неплохо, так как такой алгоритм проще написать, но, с другой стороны, его общность ограничена. Это значит, в общем случае, что алгоритм будет использоваться реже, и, по-видимому, будет хуже протестирован (при тех же суммарных экономических затратах), либо затраты на поддержку будут выше.

Поэтому хотелось бы иметь механизмы, позволяющие обобщить наш алгоритм на другие типы данных (существующие и перспективные). Это позволит использовать тот же алгоритм во многих случаях и окупит затраты на его разработку и тестирование.

В ООП предлагается выделить общий интерфейс для "похожих" данных и реализовывать алгоритм в терминах этого общего интерфейса. В конкретных классах, наследующих этот интерфейс, нам достаточно реализовать эти общие методы. Тем самым мы получаем до некоторой степени полиморфный алгоритм. Однако эти операции, входящие в интерфейс "похожих" данных, нам необходимо реализовать в самих данных.

Классы типов представляют собой следующий шаг в обособлении кода, играющего разные роли в программе. Операции, которые мы хотим выполнять над данными, перемещаются в отдельный класс, не являющийся предком данных. В алгоритм вместе с данными передаётся экземпляр этого класса для этого типа данных.

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

def compare[T](a: T, b: T): Int

Поместим эту функцию в класс типа Ordering:

trait Ordering[T] {
  def compare(a: T, b: T): Int
}

Теперь пусть наш универсальный алгоритм занимается сортировкой. Он должен принимать тип данных, с которыми он работает:

def sort[T](list: List[T]): List[T]

так как внутри алгоритма производится сравнение элементов, то этому алгоритму необходимо передать экземпляр класса Ordering для нашего типа T:

def sort[T: Ordering](list: List[T]): List[T]

либо, что тоже самое:

def sort[T](list: List[T])(implicit o: Ordering[T]): List[T]

Алгоритм при необходимости вызова операции compare должен получить экземпляр класса типа с помощью implicitly[Ordering[T]].compare(a,b).

Нам остаётся только предоставить экземпляр класса типа для нашего типа данных:

implicit object FormOrdering extends Ordering[Form] { 
  def compare(a: Form, b: Form): Int = (a,b) match {
    case (Form1(numberA, titleA), Form1(numberB, titleB)) => numberA - numberB
    case (BadForm, BadForm) => 0
   ...
    case _ => 0
  }
}

Таким образом, мы достигаем общности алгоритма без загромождения наших данных кусками кода, относящимися к специфическому алгоритму.

Дополнительное удобство

Как сделать методы доступными напрямую у самого типа? Например, мы бы хотели внутри алгоритма сравнивать объекты с помощью метода a compare b, без явного вызова метода класса типа.
Для этого используется обычный в Scala механизм pimp-my-library:

implicit class OrderingOps[T:Ordering](a:T){
  def compare(b:T): Int = implicitly[Ordering[T]].compare(a,b)
}

Тем самым, у всех типов, для которых имеется экземпляр Ordering, появится новый "метод" compare.
Если такое желание возникает всякий раз, то можно использовать библиотеку simulacrum, которая создаёт такой вспомогательный метод со всей необходимой обвязкой с помощью макросов:

import simulacrum.typeclass
@typeclass trait Ordering[T]{ 
  def compare(a: T, b: T): Int
}

Пример: Класс типа для переписывания деревьев (символьное решение уравнений, оптимизация программ)

Рассмотрим пример класса типа для пользовательской структуры данных. Одним из механизмов, используемых для оптимизации программ, является переписывание AST с сохранением семантики. При этом производится обход всех узлов дерева (в глубину или в ширину), и для каждого узла выполняется поиск соответствующего шаблона (pattern matching) и в случае сопоставления шаблона узел переписывается по соответствующему правилу.

Для разных задач (уравнения, программы) типы, составляющие дерево AST, отличаются, шаблоны сопоставления/оптимизации — тоже отличаются. Однако алгоритм обхода — одинаковый.

Этот алгоритм — претендент на абстрагирование с использованием классов типов. К произвольному типу дерева мы должны добавить какие-то операции, используемые в алгоритме обхода дерева.

import simulacrum.typeclass

@typeclass trait RewritableTree[T] {
  def children(node: T): List[T]
  def replaceChildren(node: T, newChildren: List[T]): T
}

object RewritableTree {
  def rewrite[T: RewritableTree](f: PartialFunction[T, T]): T => T = t => {
    rewrite0(f)(t).getOrElse(t)
  }

  private def rewrite0[T: RewritableTree](f: PartialFunction[T, T])(t: T): Option[T] = {
    import RewritableTree.ops._  // импортируем "методы", сгенерированные simulacrum'ом
      val rt = implicitly[RewritableTree[T]]   - мы могли бы обойтись и без этого "метода"
    val children = t.children // rt.children(t)

    var changed = false // кроме собственно переписывания, нам надо знать, произошло ли изменение, чтобы не переписывать всё дерево без надобности
    val updatedChildren = children.map{child =>
      val res = rewrite0(f)(child)
      changed = changed || res.isDefined
      res.getOrElse(child)
    }
    // альтернативная реализация без локальной изменяемой переменной
    //def rewriteList(lst: List[T], result: mutable.ListBuffer[T], changed: Boolean): (List[T], Boolean) = lst match {
    //  case Nil => (result.toList, changed)
    //  case head :: tail =>
    //    val res = rewrite0(f)(head)
    //    rewriteList(tail, result.append(res.getOrElse(head)), changed || res.isDefined)
    //}
    //val (updatedChildren, changed) = rewriteList(t.children, mutable.ListBuffer(), false)
    val updatedTree =
      if(changed)
        t.replaceChildren(updatedChildren)
      else
        t
    var changed2 = true
    val updatedTree2 = f.applyOrElse(t1, (_:T) =>{changed2 = false; updatedTree})
    if(changed || changed2)
      Some(updatedTree2)
    else
      None
  }
}

Индуктивное определение классов типов для производных типов

Предположим, у нас уже реализован класс типа Ordering[T] для нашего типа T. А мы бы хотели отсортировать список Option[T]. Нельзя ли нам воспользоваться уже реализованным классом типа и просто дополнить недостающую функциональность?

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

implicit def optionOrdering[T:Ordering]: Ordering[Option[T]] = new Ordering[Option[T]] {
  def compare(a: Option[T], b: Option[T]): Int = (a, b) match {
    case (Some(c), Some(d)) => implicitly[Ordering[T]].compare(c,d)
    case (None, None) => 0
    case (_, None) => 1
    case (None, _) => -1
  }
}

Такая реализация автоматически подставляется в алгоритм сортировки для любых типов, для которых есть экземпляр класса типа Ordering[T].

Аналогичным образом можно конструировать классы типов для любых generic-типов, таких как, List[T], Tuple2[A,B], ...

Стандартные классы типов (cats)

Операции, которые объявляются внутри классов типов, могут быть любыми. Для нашего алгоритма мы можем провести границу абстракции достаточно произвольно, например, весь алгоритм поместить в класс типа, либо наоборот, в класс типа поместить непосредственно методы доступа к данным. Оба этих граничных варианта не являются оптимальными с точки зрения повторного использования. Поэтому в классы типов стоит помещать минимальное количество операций, которые несложно реализовать для других типов, и при этом наш алгоритм может быть выражен через эти операции.

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

В стандартной библиотеке Scala имеется несколько классов типов: Ordering[T], Equiv[T], Numeric[T], Integral[T], ...

В библиотеке typelevel/cats (как и в библиотеке scalaz) объявлено несколько дополнительных классов для простых типов с часто используемыми операциями (http://typelevel.org/cats/typeclasses.html):

1. Полугруппа (Semigroup) — одна операция combine.
2. Моноид — полугруппа с пустым ("нулевым") элементом — empty.

Например, для чисел можно определить операцию combine как сумму чисел, в этом случае нулевым элементом будет обычный ноль. Мы получим аддитивный моноид. Также можно использовать мультипликативный моноид, если в качестве операции combine взять умножение, а empty — единицу. Список чисел также можно рассматривать как моноид. В роли операции combine будет выступать склейка списков, а нулевым элементом — пустой список.

Пример:
Можно использовать моноид для реализации накопления. Создаём состояние с начальным значением, равным empty из моноида. Далее при поступлении данных на вход мы можем их объединить combine с теми, что уже находятся в состоянии. Например, можем взять тип Int с операцией "сумма". В этом случае в одном значении будет накапливаться сумма поступающих данных. Или взять моноид для List[T]. В этом случае все данные будут доступны в этом списке (на входе должны быть списки, либо каждое число надо будет обернуть в список). Алгоритм накопления в обоих случая является идентичным — вызвать метод combine для существующих данных и вновь поступивших. И алгоритм не зависит от конкретного типа, с которым он работает.

Также, если про какой-то тип нам известно, что он моноид (т.е. имеется экземпляр класса моноид для этого типа), то мы можем использовать foldLeft — свёртку для коллекции этих элементов (нам не надо её заново реализовывать).

Типы высших порядков

Кроме простых базовых типов классы типов могут использоваться для работы с типами, которые сами по себе имеют параметры. (Тем самым, класс типа требует поддержки типов высших порядков в языке.) Типы высших порядков характеризуются kind'ом — "типом типа":

• простой тип имеет kind * (например, Int, String);
• тип, принимающий один аргумент — * -> * (например, List[T], Option[T], Future[T]);
• тип, принимающий два аргумента — * -> * -> * (например, функция Function1[A,B]). (Обратите внимание, что сама функция на уровне значений содержит одну стрелку A => B, а на уровне типов — A => B => (A=>B) — две стрелки (третья стрелочка — уже внутри самого типа).)

В библиотеке cats кроме классов типов, работающих с базовыми типами, есть классы типов, используемые при работе с конструкторами типов. В частности, для типов * -> *:

1. Функтор — класс типа, содержащий одну операцию — map. Операция принимает объект, например, типа List[Int]и применяет указанную функцию к каждому элементу. Для List'а и для Option, эта операция, вообще говоря, уже реализована в самом типе данных, и можно было бы не создавать класс типа. Однако, если мы хотим реализовывать универсальные алгоритмы с использованием операции map, то такой класс типа необходим.

   
   
2. Монада — функтор, содержащий операцию flatMap, или bind, или >>= (а также flatten, map, pure). Этот класс типа, по-видимому, самый знаменитый. Его польза обусловлена тем фактом, что flatMap (bind) является достаточно универсальным способом склейки последовательных вычислений. На операции flatMap даже основан "сахар" в Scala — for-comprehension.

Пример:

• Обработка списков. Собрать всех детей для коллекции объектов — val allChildren = objects.flatMap(_.children)
• Обработка отсутствующих значений: val street = personOpt.flatMap(_.addressOpt).flatMap(_.streetOpt)
• Отложенное исполнение запросов. Пусть результат некоторого запроса из БД может быть представлен типом DataTable[T]. С помощью flatMap мы можем определить подзапрос, извлекающий данные из результатов этого запроса. Такой запрос можно приклеить к исходному запросу, не выполняя первого запроса и не работая с коллекцией результатов. Склеенный запрос мы можем скомпилировать в SQL и отправить в БД для исполнения на стороне СУБД. Такой подход реализуется, например, в библиотеке Slick.

Для типов * -> * -> * в библиотеке cats тоже есть класс типа:

1. Категория — операция compose + "нулевой" элемент — identity. Тип, для которого определён класс типа "категория", называется "стрелкой" (Arrow). Стрелки похожи на функции. В частности, для обычных функций операция compose соответствует методу andThen, а операция identity — функции identity.

Примеры категорий:

1. Обычные функции.
2. Модельные функции (в модельном языке).
3. Линзы (свойства объектов, отделённые от классов) (см. библиотеку monocle).
4. Направленный граф в Functional Reactive Programming (например, SynapseGrid).

Пример:
Для категорий ключевой возможностью является compose. Т.е. если наш алгоритм удаётся выразить в терминах compose, то мы можем этот алгоритм применить для любых категорий.

Пусть мы моделируем цепочку преобразований данных с помощью собственного DSL. Допустим, что каждое преобразование может быть представлено некоторым типом Transform[A,B].

После того, как пользователь описал свою задачу с использованием этого DSL, мы можем конвертировать наши условные преобразования в реальные действия с данными, представленные уже обычными функциями над реальными типами. Конвертация одной категории (модельных функций) в другую категорию (реальных функций) называется "естественным преобразованием".

Законы для классов типов

Классы типов, реализованные в библиотеке cats, моделируют понятия теории категорий. Поэтому методы этих классов типов должны удовлетворять определённым свойствам (которые описаны в теории). Например, для моноида:

1. a combine empty = a = empty combine a — определение пустого элемента
2. (a combine b) combine c = a combine (b combine c) — ассоциативность операции combine

Все свойства, которые требуются теорией категорий для класса типа, реализованы в виде "законов" — наборов "свойств" библиотеки ScalaCheck. И можно для любого экземпляра класса типа выполнить проверку, удовлетворяет ли этот экземпляр требованиям, предъявляемым к этому классу типа. Многие алгоритмы опираются на эти свойства, поэтому при реализации классов типов для своих данных, следует эти законы проверять в unit test'ах.

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

Преимущества классов типов

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

• можно реализовать класс для недоступного типа;
• можно объявить операции, работающие с нулевым количеством экземпляров данного типа. В частности, метод empty: T, или метод parse: String => T;
• можно индуктивным образом определить экземпляр составного типа, если есть экземпляры для базовых типов. Например, для Option[T] или для A \/ B.

Этими преимуществами можно воспользоваться самостоятельно в любой программе. Достаточно по-другому взглянуть на структуру своего кода.

В библиотеке cats (а также в библиотеке scalaz) имеется хорошо организованный и протестированный набор классов типов (из теории категорий), которые применяются во многих алгоритмах и библиотеках. При использовании этой библиотеки можно получить весьма универсальный программый код, который, к тому же будет хорошо протестирован уже написанными тестами и в некоторой степени валидирован с помощью проработанной математической теории.