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

Код написан на Scala версии 3.3.1.

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

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

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

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

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

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

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

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

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

• Замыкание: для ∀ x, y ∈ S выполняется x + y ∈ S

• Ассоциативность: для ∀ x, y, z ∈ S выполняется (x + y) + z = x + (y + z)

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

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

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