Scala: структура данных в пространстве типов — множество

Система типов Scala 3 позволяет конструировать вторичные структуры данных в пространстве типов. Ярким примером таких структур может выступать HList, впоследствии ставший основой реализации кортежей. Кортежи в Scala 3 стали весьма гибким инструментом, позволяющим захватить в упорядоченном виде сведения о разнородных типах.

В настоящей заметке мы рассмотрим реализацию структуры “множество типов” на основе кортежей с использованием инструментов Scala 3.

Требования

Какие базовые возможности мы хотели бы видеть для такой структуры?

1. Проверка принадлежности (Belongs[Element, Set]≡Element∊Set).
2. Конструирование пустого множества (EmptySet) и множества из одного произвольного типа (Singleton[A]).
3. Операции — объединение (Union[Set1, Set2]), пересечение (Intersection[Set1, Set2]), вычитание (Subtract[Set1, Set2]).
4. Кванторы всеобщности (ForAll) и существования (Exists).
5. Проверка множеств на равенство (Equal[Set1, Set2]), вхождение (SubsetOf[Set1,Set2]).
6. Потенциальные пути реализации отрицания (Not[Set1] ≡ Universum-Set1).
7. Возможность использования множеств типов в пространстве значений.

Реализация на основе кортежей (Tuple)

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

Конструирование пустого множества и синглетона

type Empty        = EmptyTuple
type ∅            = Empty
type Set1[a]      = a *: EmptyTuple
type Singleton[a] = Set1[a]

Проверка принадлежности

Базовая операция для множеств, определённых конструктивно.

type BelongsTo[E, T <: Tuple] <: Boolean =
  T match
    case EmptyTuple  => false
    case `E` *: tail => true
    case _ *: tail   => BelongsTo[E, tail]

Здесь мы рекурсивно разбираем кортеж и проверяем что тип, находящийся в начале кортежа, равен искомому. Если равен — возвращаем тип true. В противном случае, продолжаем рекурсивно разбирать кортеж.

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

infix type ∊[Element, Set <: Tuple] = BelongsTo[Element, Set]

Объединение

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

type Union[a <: Tuple, b <: Tuple] <: Tuple = a match
  case EmptyTuple => b
  case el *: tail =>
    BelongsTo[el, b] match
      case true  => Union[tail, b]
      case false => el *: Union[tail, b]

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

Для красоты вводим сокращённый тип

infix type ∪[A <: Tuple, B <: Tuple] = Union[A, B]

Пересечение

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

type Intersection[a <: Tuple, b <: Tuple] <: Tuple = a match
  case EmptyTuple => EmptyTuple
  case el *: tail =>
    BelongsTo[el, b] match
      case true  => el *: Intersection[tail, b]
      case false => Intersection[tail, b]

infix type ∩[A <: Tuple, B <: Tuple] = Intersection[A, B]

Разность и симметричная разность

Полностью аналогично конструируем разность множеств.

type Difference[a <: Tuple, b <: Tuple] <: Tuple = a match
  case EmptyTuple => EmptyTuple
  case el *: tail =>
    BelongsTo[el, b] match
      case true  => Difference[tail, b]
      case false => el *: Difference[tail, b]

infix type -[a <: Tuple, b <: Tuple] = Difference[a, b]
infix type \[a <: Tuple, b <: Tuple] = Difference[a, b]

Симметричную разность или операцию XOR мы можем построить, пользуясь имеющимися определениями:

infix type ^[a <: Tuple, b <: Tuple]             = (a ∪ b) \ (a ∩ b)
type SymmetricDifference[a <: Tuple, b <: Tuple] = (a ∪ b) \ (a ∩ b)

Кванторы всеобщности и существования

Часто важно проверить какое-то свойство на всех элементах множества. Для этого можно использовать квантор всеобщности:

type ForAll[S <: Tuple, P[_] <: Boolean] <: Boolean = S match
  case EmptyTuple => true
  case el *: tail => P[el] && ForAll[tail, P]
type ∀[S <: Tuple, P[_] <: Boolean] = ForAll[S,P]

Здесь P[_] — функция, определённая в пространстве типов. Принимает на вход один из типов, входящих в множество, и возвращает тип true или false.

В реализации мы используем тип &&, определённый в import scala.compiletime.ops.boolean.&&.

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

type Exists[S <: Tuple, P[_] <: Boolean] =
  ![ForAll[S, [e] =>> ![P[e]]]]
type ∃[S <: Tuple, P[_] <: Boolean] = Exists[S,P]

Здесь мы используем type-lambda [e] =>> ![P[e]]] — функция в пространстве типов, принимающая аргумент, тип e, и возвращающая тип, находящийся справа от стрелки.

Сравнение множеств (равенство, вхождение)

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

type IsSubSetOf[A <: Tuple, B <: Tuple] =
  ForAll[A, [a] =>> BelongsTo[a, B]]

type ⊂[A <: Tuple, B <: Tuple]  = IsSubSetOf[A, B]
type <=[A <: Tuple, B <: Tuple] = IsSubSetOf[A, B]
type >=[A <: Tuple, B <: Tuple] = IsSubSetOf[B, A]

В свою очередь, равенство множеств определяется как вхождение одного в другое и наоборот.

type Equal[A <: Tuple, B <: Tuple] = IsSubSetOf[A, B] && IsSubSetOf[B, A]

Циклы по элементам множества*

Для некоторых операций хотелось бы иметь универсальный инструмент, перебирающий элементы множества. По-видимому, удобным функциональным аналогом цикла является операция fold. Такая операция использует моноид над типами, то есть начальное значение и операцию Combine, объединяющую два элемента. Пользуясь этой парой, мы можем определить foldLeft и foldRight:

type FoldLeft[S <: Tuple, Res, Z <: Res, Combine[_ <: Res, _] <: Res] <: Res = S match
  case EmptyTuple => Z
  case el *: tail =>
    FoldLeft[tail, Res, Combine[Z, el], Combine]

type FoldRight[S <: Tuple, Res, Z <: Res, Combine[_, _ <: Res] <: Res] <: Res = S match
  case EmptyTuple => Z
  case el *: tail =>
    Combine[el, FoldRight[tail, Res, Z, Combine]]

Здесь мы также используем ограничитель типа моноида Res, чтобы на выходе получить предсказуемый тип результата.

Нижняя и верхняя грань*

Пользуясь введёнными операциями свёртки fold мы можем легко посчитать верхнюю и нижнюю грань всех входящих типов:

type Upper[S <: Tuple]  = FoldLeft[S, Any, Nothing, |]
type Bottom[S <: Tuple] = FoldLeft[S, Any, Any, &]

Здесь в качестве начальной верхней грани берём Nothing, а в качестве операции объединения — |. А для нижней грани, начинаем с Any и объединяем с помощью &.

Использование множеств типов в пространстве значений

Нам может быть интересно, что некоторое значение (кортеж) содержит значения всех типов из множества. Либо, дополнительно, что все типы множества имеют какое-то значение в переданном кортеже.

Такие проверки можно выполнить с помощью implicit‘ов, предоставляющих “свидетельства” (evidence) требуемого свойства. Такое свидетельство предоставляется компилятором автоматически, если потребовать Equal[A, B] =:= true.

  trait setEqualsChecker[A <: Tuple]:
    inline def apply[B <: Tuple](b: B)(using ev: Equal[A, B] =:= true): true = true
    inline def to[B <: Tuple](using ev: Equal[A, B] =:= true): true = true
  transparent inline def setEquals[A <: Tuple]: setEqualsChecker[A] = 
    new setEqualsChecker[A] {}

Мы осуществляем такую проверку в два приёма. Вначале конструируем объект, захватывающий тип требуемого множества [A], а затем у этого объекта реализуем метод apply, который уже принимает тип того значения, которое мы передаём. И, конечно же, в этот момент мы запрашиваем свидетельство того, что множества равны.

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

Аналогичным образом можно проверить и свойство IsSubSetOf

  trait setIsASupersetChecker[A <: Tuple]:
    def apply[B <: Tuple](b: B)(using ev: IsSubSetOf[A, B] =:= true): true = true
  transparent inline def setIsASuperset[A <: Tuple]: setIsASupersetChecker[A] = 
    new setIsASupersetChecker[A] {}

Либо можно проверить любое свойство над множествами:

  trait сhecker[A <: Tuple, P[_<: Tuple,_<: Tuple]<:Boolean]:
    def apply[B <: Tuple](b: B)(using P[A, B] =:= true): true = true
  transparent inline def setChecker[A <: Tuple, P[_<: Tuple,_<: Tuple]<:Boolean]: сhecker[A, P] = 
    new сhecker[A, P] {}

Отрицание множества

При использовании других представлений множеств типов, мы можем также определить отрицание множества через Universum:

type Not[Set] = Universum \ Set

Для Tuple‘а, однако, такое определение невозможно, т.к. мы точно знаем все входящие типы, а Universum, содержит неограниченное количество типов.

Заключение

В настоящей заметке рассмотрена реализация инструмента, который может оказаться полезным для некоторых задач, — множества в пространстве типов. В качестве нижележащего представления используется Tuple, а основным инструментом обработки служат match-type’ы.

Библиотека опубликована на github’е.

Сложность большинства алгоритмов оказывается O(N^2). По-видимому, не стоит использовать эту библиотеку для обработки большого количества типов.