Система типов Scala 3 позволяет конструировать вторичные структуры данных в пространстве типов. Ярким примером таких структур может выступать HList, впоследствии ставший основой реализации кортежей. Кортежи в Scala 3 стали весьма гибким инструментом, позволяющим захватить в упорядоченном виде сведения о разнородных типах.
В настоящей заметке мы рассмотрим реализацию структуры "множество типов" на основе кортежей с использованием инструментов Scala 3.
Требования
Какие базовые возможности мы хотели бы видеть для такой структуры?
- Проверка принадлежности (
Belongs[Element, Set]≡Element∊Set). - Конструирование пустого множества (
EmptySet) и множества из одного произвольного типа (Singleton[A]). - Операции — объединение (
Union[Set1, Set2]), пересечение (Intersection[Set1, Set2]), вычитание (Subtract[Set1, Set2]). - Кванторы всеобщности (
ForAll) и существования (Exists). - Проверка множеств на равенство (
Equal[Set1, Set2]), вхождение (SubsetOf[Set1,Set2]). - Потенциальные пути реализации отрицания (
Not[Set1] ≡ Universum-Set1). - Возможность использования множеств типов в пространстве значений.
Реализация на основе кортежей (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). По-видимому, не стоит использовать эту библиотеку для обработки большого количества типов.
