Классы типов

Что такое класс типов?

Давайте разберем, что такое класс типов. Обратимся к формальному определению:

Класс типов (type class) — это абстрактный параметризованный тип, который позволяет добавлять новое поведение к любому закрытому типу данных без использования подтипов.

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

Является ли классом типов следующее определение?

trait Something[A, B]:
  def doSomething(x: A): B

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

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

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

Замыкание: для \(\forall a, b \in S\) выполняется \(a + b \in S\)
Ассоциативность: для \(\forall a, b, c \in S\) выполняется \((a + b) + c = a + (b + c)\)

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

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

object Semigroup:
  def isSemigroup[A](x: A, y: A, z: A)(using sm: Semigroup[A]): Boolean =
    import sm.combine
    combine(x, combine(y, z)) == combine(combine(x, y), z)

Конечно, при условии, если бы мы могли запустить эту проверку на всех возможных элементах типа A или хотя бы на достаточно большой выборке. Потому что и для вычитания isSemigroup(x, y, 0) выдаст true для любых x и y, хотя вычитание не ассоциативно.

Например, целые числа с операцией умножения являются полугруппой и удовлетворяют законам полугруппы:

given Semigroup[Int] = (x: Int, y: Int) => x * y
Semigroup[Int].combine(3, 5)
// val res0: Int = 15

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

Итак, класс типов может характеризоваться не только своим определением, но ещё и набором законов.

Зачем нужны законы?

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

Замыкание

Например, какой вывод можно сделать из закона "Замыкание"?

Если мы можем "сложить" два элемента определенного типа и получить в результате элемент того же типа, то это означает, что данную операцию можно проводить несколько раз над результатом предыдущего "сложения"! Т.е. из "сложения" мы можем получить "умножение", из "умножения" - "возведение в степень" и т.д..

И у нас уже есть не только \(3 * 5\), но и \(3^{5}\):

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

  def combineN(x: A, n: Int :| Greater[0]): A =
    @tailrec def loop(b: A, k: Int, acc: A): A =
      if k == 1 then combine(b, acc)
      else
        val x = if (k & 1) == 1 then combine(b, acc) else acc
        loop(combine(b, b), k >>> 1, x)

    if n == 1 then x else loop(x, n - 1, x)

Semigroup[Int].combineN(3, 5)
// val res1: Int = 243

О том, что такое Int :| Greater[0] рассказывается в статье об уточняющих типах.

Ассоциативность

"Ассоциативность" говорит о том, что мы можем складывать элементы в любом порядке. А значит, можем использовать этот факт там, где он полезен - при реализации класса типов!

Например, как свернуть коллекцию из миллиона элементов? Разбить коллекцию пополам, параллельно свернуть каждую половину, а затем - "сложить" результаты?! Для Vector-а - да, но будет ли это эффективно для связанного списка?! Ответы на эти вопросы содержатся во многих книгах, но здесь важно другое - что мы можем выбирать, как "складывать" элементы коллекции, если это "сложение" ассоциативно.

Т.о. законы классов типов помогают наиболее эффективно реализовать эти классы типов.

Расширение подходящих типов

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

given nestedSemigroupInstance[A, B](using asm: Semigroup[A], bsm: Semigroup[B]): Semigroup[(A, B)] =
  (x: (A, B), y: (A, B)) => (asm.combine(x._1, y._1), bsm.combine(x._2, y._2))

Мы получили новую реализацию на основе существующих! Конечно, это возможно не всегда и зависит от класса типов, но все же...

Выводы

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

Итак, вернёмся к началу: является ли классом типов следующее определение?

trait Something[A, B]:
  def doSomething(x: A): B