Scala: структура данных в пространстве типов — множество
Система типов 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). По-видимому, не стоит использовать эту библиотеку для обработки большого количества типов.
