scalabook

Форк
0
/
type-level-programming-in-scala.md 
2258 строк · 98.7 Кб

Программирование на уровне типов в Scala

В этом разделе приведен перевод статей "Type-Level Programming in Scala" с адаптацией под версию Scala 3.

Часть 1: Рекурсия типов

Исходная статья

Система типов Scala допускает рекурсию, но не бесконечную рекурсию. Следующий код из примера выведет ошибку компиляции:

// определение абстрактного типа и границ
trait Recurse:
type Next <: Recurse
// это определение рекурсивной функции
type X[R <: Recurse] <: Int
// реализация
trait RecurseA extends Recurse:
type Next = RecurseA
// это реализация
type X[R <: Recurse] = R#X[R#Next]
object Recurse:
// ошибка компиляции: бесконечный цикл
type C = RecurseA#X[RecurseA]

Часть 2: implicitly и =:=

Исходная статья

В этой главе кратко представлена полезная техника сравнения типов (показанная Jason Zaugg), которая позже будет использоваться для проверки результатов вычислений на уровне типов.

Она использует метод summon

, определенный в Predef
как:

transparent inline def summon[T](using x: T): x.type = x

Это полезно для перехвата неявного значения, которое находится в области видимости и имеет тип T

. Неявное значение, которое нам нужно в этом случае, это A =:= B
для некоторых типов A
и B
. A =:= B
будет найдено только тогда, когда A
того же типа, что и B
.

Например, этот код компилируется:

summon[Int =:= Int]
// val res0: Int =:= Int = generalized constraint

но следующий - нет:

summon[Int =:= String]
// -- [E172] Type Error: ----------------------------------------------------------
// 1 |summon[Int =:= String]
// | ^
// | Cannot prove that Int =:= String.
// 1 error found

Также доступен <:<

для соответствия типов.

Пример соответствия (<:<

):

summon[Int =:= AnyVal]
// -- [E172] Type Error: ----------------------------------------------------------
// 1 |summon[Int =:= AnyVal]
// | ^
// | Cannot prove that Int =:= AnyVal.
// 1 error found
summon[Int <:< AnyVal]
// val res0: Int =:= Int = generalized constraint

Scala API

Часть 3: Booleans

Исходная статья

Хорошим вводным примером программирования на уровне типов является кодирование логических значений по Черчу. Это не требует ничего особенного, и позже нам понадобятся Boolean-ы при сравнении чисел.

Основные задействованные типы:

sealed trait Bool
sealed trait True extends Bool
sealed trait False extends Bool

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

type Rep[A <: Bool] =
A match
case True => Int
case False => Long
summon[Rep[True] =:= Int]
// val res0: Int =:= Int = generalized constraint
summon[Rep[False] =:= Long]
// val res1: Long =:= Long = generalized constraint

Используя эту технику мы можем определить некоторые дополнительные типы в сопутствующем объекте Bool

:

object Bool:
type &&[A <: Bool, B <: Bool] =
A match
case False => False
case _ => B
type ||[A <: Bool, B <: Bool] =
A match
case True => True
case _ => B
type Not[A <: Bool] =
A match
case True => False
case False => True

Пример использования:

summon[((True && False) || Not[False]) =:= True]
// val res0: True =:= True = generalized constraint
// Аналогичный результат ниже
summon[(True && True) =:= True]
summon[(True && False) =:= False]
summon[(False && True) =:= False]
summon[(False && False) =:= False]
summon[(True || True) =:= True]
summon[(True || False) =:= True]
summon[(False || True) =:= True]
summon[(False || False) =:= False]
summon[Not[True] =:= False]
summon[Not[False] =:= True]

Мы также можем добавить в модуль Bool

метод для преобразования типа Bool
в логическое значение для прямой печати:

object Bool:
class BoolRep[B <: Bool](val value: Boolean)
given BoolRep[False] = new BoolRep(false)
given BoolRep[True] = new BoolRep(true)
def toBoolean[B <: Bool: BoolRep]: Boolean =
summon[BoolRep[B]].value

Пример:

Bool.toBoolean[(True && False) || Not[False]]
// val res0: Boolean = true

Это еще один метод проверки результата вычислений на уровне типов.

Часть 4. Натуральные числа

Часть 4а. Основы чисел Пеано

Исходная статья

Как упоминалось во вступительной главе, мы можем выполнять рекурсию на уровне типов в Scala. Первым применением для этого будет представление чисел в системе типов (числа Пеано). Одним из их применений является безопасное для типов индексирование в HLlists

, что мы сделаем в следующей главе. Основная идея, конечно, не нова, но мы все еще создаем инструменты, которые нам понадобятся для последующих глав.

Базовое представление неотрицательных целых чисел на уровне типа выглядит так:

sealed trait Nat
sealed trait _0 extends Nat
sealed trait Succ[N <: Nat] extends Nat

Мы можем построить другие целые числа с помощью Succ

:

type _1 = Succ[_0]
type _2 = Succ[_1]
type _3 = Succ[_2]
type _4 = Succ[_3]
type _5 = Succ[_4]
...

Сопоставление с шаблоном для типов позволяет нам деконструировать Nat

. Например, мы можем объявить тип, который определяет, равен ли его параметр _0
:

type Is0[A <: Nat] =
A match
case _0 => True
case _ => False

Для _0

результатом деконструирования будет True
, иначе - False
.

Bool.toBoolean[Is0[_0]] // true
Bool.toBoolean[Is0[_2]] // false

Исключительно для развлечения продолжим определение сравнений, сложения, умножения, модуля и возведения в степень.

Часть 4b. Сравнение чисел Пеано

Исходная статья

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

sealed trait Comparison:
type Match[IfLT <: Up, IfEQ <: Up, IfGT <: Up, Up] <: Up
type gt = Match[False, False, True, Bool]
type ge = Match[False, True, True, Bool]
type eq = Match[False, True, False, Bool]
type le = Match[True, True, False, Bool]
type lt = Match[True, False, False, Bool]

Реализации выглядят так:

sealed trait LT extends Comparison:
type Match[IfLT <: Up, IfEQ <: Up, IfGT <: Up, Up] = IfLT
sealed trait EQ extends Comparison:
type Match[IfLT <: Up, IfEQ <: Up, IfGT <: Up, Up] = IfEQ
sealed trait GT extends Comparison:
type Match[IfLT <: Up, IfEQ <: Up, IfGT <: Up, Up] = IfGT

Затем мы можем определить тип Compare

, сравнивающий два Nat
.

infix type Compare[A <: Nat, B <: Nat] <: Comparison =
A match
case _0 =>
B match
case _0 => EQ
case _ => LT
case Succ[a] =>
B match
case _0 => GT
case Succ[b] => Compare[a, b]

Для A

равного _0
результатом Compare
является EQ
если B
равен _0
(A
и B
равны), и LT
(A
меньше) - в противном случае. Если же A
- это Succ[a]
, где a
- переменная типа, предшествующего A
, то проверяем B
. Если он равен _0
, то результатом Compare
является GT
(A
больше). Если же он равен Succ[b]
, то возвращаем результат сравнения предшествующих типов.

Получается потенциально бесконечная рекурсия на уровне типов.

Примеры:

toBoolean[(_0 Compare _0)#eq] // true
toBoolean[(_0 Compare _0)#lt] // false
toBoolean[(_3 Compare _5)#lt] // true

Когда мы доберемся до бинарного дерева поиска, Compare

позволит использовать Nat
-ы в качестве ключей в дереве. Далее мы определим общий способ рекурсии в Nat
с использованием fold-ов.

Часть 4c. Общая рекурсия по числам Пеано

Исходная статья

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

Часть 4d. Арифметика чисел Пеано

Исходная статья

Будем использовать сравнение типов для определения арифметики натуральных чисел на уровне типов.

Функции уровня типа будут следовать форме функций уровня значения (в большинстве случаев мы просто применяем функцию n

раз и ничего не делаем с текущим значением итерации).

Сложение выглядит так (что равносильно формуле: a + b = (a - 1) + (b + 1)

):

type Add[A <: Nat, B <: Nat] <: Nat =
A match
case _0 => B
case Succ[a] => Add[a, Succ[B]]

Следующие проверки успешно компилируются:

summon[Add[_0, _3] =:= _3]
summon[Add[_3, _0] =:= _3]
summon[Add[_3, _2] =:= _5]

Умножение определяется сложением (a * b = a + a + ... + a

). Вынесем случай _0
в отдельный вариант, чтобы сэкономить время на вычисление.

type Mult[A <: Nat, B <: Nat] <: Nat =
A match
case _0 => _0
case _1 => B
case Succ[a] =>
B match
case _0 => _0
case _ => Add[Mult[a, B], B]
summon[Mult[_0, _3] =:= _0]
summon[Mult[_3, _0] =:= _0]
summon[Mult[_3, _2] =:= _6]

Используя умножение можно определить факториал (a! = a * (a - 1) * ... * 1

):

type Fact[A <: Nat] <: Nat =
A match
case _0 => _1
case Succ[a] => Mult[A, Fact[a]]
summon[Fact[_3] =:= _6]

Возведение в степень с точки зрения умножения (\(a^{b} = a * a * ... * a\)):

type Exp[A <: Nat, B <: Nat] <: Nat =
B match
case _0 => _1
case Succ[b] => Mult[A, Exp[A, b]]
summon[Exp[_3, _0] =:= _1]
summon[Exp[_3, _1] =:= _3]
summon[Exp[_3, _2] =:= _9]

Сравнение по модулю использует Compare

и требует дополнительного объяснения.

Результат A % B = ?

:

  • в первую очередь запрещаем сравнивать по модулю 0
    , добавляя ограничение B <: Succ[?]
  • если A
    меньше B
    , то возвращаем A
  • если они равны, то 0
  • если A
    больше B
    , то оно точно не равняется 0
    и можно сразу вычленить "предыдущее число".
    • для вычисления модуля используем равенство: A % B = (((A - 1) % B) + 1) % B
    • рекурсия всегда заканчивается, потому что мы спускаемся от A
      до B
      , а затем возвращаем результат (A - B) % B
    • и так до тех пор, пока "разница" не станет меньше или равна B
      ...
type Mod[A <: Nat, B <: Succ[?]] <: Nat =
A Compare B match
case LT => A
case EQ => _0
case GT =>
A match
case Succ[a] => Mod[Add[Mod[a, B], _1], B]
summon[Mod[_5, _1] =:= _0]
summon[Mod[_5, _2] =:= _1]
summon[Mod[_5, _3] =:= _2]
summon[Mod[_5, _4] =:= _1]
summon[Mod[_5, _5] =:= _0]
summon[Mod[_5, _6] =:= _5]

Для удобства определим тип сравнения:

type Eq[A <: Nat, B <: Nat] <: Bool =
Compare[A, B] match
case EQ => True
case _ => False

Несколько примеров:

type Sq[N <: Nat] = Exp[N, _2]
toBoolean[Eq[Sq[_9], Add[_1, Mult[_8, _10]]]] // true

Операции с Nat

легко реализовать с помощью сверток, но они плохо работают с достаточно большими числами или более сложными выражениями. Около 10_000
время компиляции сильно увеличивается или переполняется стек. Далее мы рассмотрим представление целых чисел без знака в двоичном виде и (вроде) решим проблему Эйлера № 4.

Часть 5. Двоичные числа уровня типа

Часть 5a. Двоичные числа

Исходная статья

Операции Nat

обычно ограничиваются результатами ниже 10_000
. Время компиляции становится довольно продолжительным или переполняется стек. Альтернативой является использование двоичного представления чисел, названного здесь Dense после реализации в "Чисто функциональных структурах данных" Окасаки. Мы будем использовать это представление для решения упрощенной задачи Project Euler в системе типов в следующей главе.

Здесь показаны только базовая форма и реализации приращения и свертки. См. полный исходный код Add

, Mult
и Exp
.

Во-первых, нам нужен тип Digit

для представления бита. Имеет два подтипа: Один (One
) и Ноль (Zero
). Мы определяем Is0
для проверки на равенство 0
и Compare
для сравнения цифр.

sealed trait Digit
sealed trait Zero extends Digit
sealed trait One extends Digit
type Is0[A <: Digit] =
A match
case Zero => True
case One => False
infix type Compare[A <: Digit, B <: Digit] <: Comparison =
A match
case Zero =>
B match
case Zero => EQ
case One => LT
case One =>
B match
case Zero => GT
case One => EQ

Например:

summon[Is0[Zero] =:= True]
summon[(One Compare Zero) =:= GT]

Далее мы создаем тип Dense

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

sealed trait Dense:
type digit <: Digit
type tail <: Dense
type ShiftR <: Dense
type ShiftL <: Dense
sealed trait DNil extends Dense:
type tail = Nothing
type digit = Nothing
type ShiftR = DNil
type ShiftL = DNil
sealed trait DCons[d <: Digit, T <: Dense] extends Dense:
type digit = d
type tail = T
type ShiftR = tail
type ShiftL = Zero :: DCons[d, T]

Мы видим, что с Dense

сдвиг происходит легче (по сравнению с Nat
). Это просто конец списка (сдвиг вправо) или добавление нуля (сдвиг влево).

Мы можем заранее определить некоторые целые числа (используя псевдоним ::

для DCons
):

type ::[H <: Digit, T <: Dense] = DCons[H, T]
type _0 = DNil
type _1 = One :: DNil
type _2 = Zero :: One :: DNil
type _3 = One :: One :: DNil
type _4 = Zero :: Zero :: One :: DNil
type _5 = One :: Zero :: One :: DNil
...

Как обычно, определяем преобразование в значения:

object Dense:
def toInt[D <: Dense](using drep: DRep[D]): Int = drep.value
final case class DRep[D <: Dense](value: Int)
given DRep[DNil] = DRep[DNil](0)
given dcons0ToRep[D <: Dense](using tailRep: DRep[D]): DRep[DCons[Zero, D]] =
DRep(tailRep.value * 2)
given dcons1ToRep[D <: Dense](using tailRep: DRep[D]): DRep[DCons[One, D]] =
DRep(tailRep.value * 2 + 1)

Пример использования:

toInt[_4] // 4

Следующее и предыдущее двоичное число определяются так:

type Inc[T <: Dense] <: Dense =
T match
case DNil => One :: DNil
case DCons[Zero, t] => One :: t
case DCons[One, t] => Zero :: Inc[t]
type Dec[T <: Dense] <: Dense =
T match
case DNil => Nothing
case DCons[Zero, t] => One :: Dec[t]
case DCons[One, DNil] => DNil
case DCons[One, t] => Zero :: t

Пример:

summon[Inc[_0] =:= _1]
summon[Inc[_1] =:= _2]
summon[Inc[_2] =:= _3]
summon[Dec[_0] =:= Nothing]
summon[Dec[_1] =:= _0]
summon[Dec[_2] =:= _1]

Операции сложения, умножения и возведения в степень определяются так:

infix type Add[A <: Dense, B <: Dense] <: Dense =
A match
case DNil => B
case DCons[Zero, ta] =>
B match
case DNil => A
case DCons[hb, tb] => hb :: Add[ta, tb]
case DCons[One, ta] =>
B match
case DNil => A
case DCons[Zero, tb] => One :: Add[ta, tb]
case DCons[One, tb] => Zero :: Inc[Add[ta, tb]]
infix type Mult[A <: Dense, B <: Dense] <: Dense =
A match
case DNil => DNil
case DCons[One, DNil] => B
case _ =>
B match
case DNil => DNil
case _ => Add[Mult[Dec[A], B], B]
infix type Exp[A <: Dense, B <: Dense] <: Dense =
B match
case DNil => _1
case _ => Mult[A, Exp[A, Dec[B]]]
type Sq[N <: Dense] = Exp[N, _2]

Пример:

toInt[_5 Add _7] // 12
toInt[_12 Mult _8 Mult _13] // 1248
toInt[_4 Exp _15] // 1073741824

В некоторых случаях большие числа обрабатываются лучше, используя Dense

, например, для степеней двойки. В других же эффективнее Nat
(например, для _3#Exp[_8]
).

Позже Dense

послужит хорошим примером ключей в ассоциативном массиве уровня типа. Далее мы решим (намного) уменьшенную версию задачи Project Euler, используя двоичные числа уровня типа. Для этого нам понадобятся функции Reverce
и Compare
, определенные в Dense
:

infix type Compare[A <: Dense, B <: Dense] <: Comparison =
A match
case DNil =>
B match
case DNil => EQ
case _ => LT
case DCons[ha, ta] =>
B match
case DNil => GT
case DCons[hb, tb] =>
Compare[ta, tb] match
case EQ => Digit.Compare[ha, hb]
case LT => LT
case GT => GT
type AddToTheEnd[D <: Digit, T <: Dense] <: Dense =
T match
case DNil => D :: DNil
case DCons[h, t] => h :: AddToTheEnd[D, t]
type Reverse[A <: Dense] <: Dense =
A match
case DNil => DNil
case DCons[h, t] => AddToTheEnd[h, Reverse[t]]

Пример использования:

summon[(_3 Compare _3) =:= EQ]
summon[(_3 Compare _5) =:= LT]
summon[(_5 Compare _3) =:= GT]
summon[Reverse[_4] =:= (One :: Zero :: Zero :: DNil)]
summon[Reverse[_8] =:= (One :: Zero :: Zero :: Zero :: DNil)]
summon[Reverse[_9] =:= _9]

Часть 5b. Project Euler problem 4

Исходная статья

Давайте посмотрим на решение проблемы № 4 Project Euler на уровне типа. Поскольку мы работаем с двоичными числами в системе типов Scala, нам приходится существенно снижать наши ожидания относительно того, что мы можем решить.

Первое упрощение заключается в том, что мы будем рассматривать палиндромы по основанию 2

, поскольку наши числа уже находятся в этом представлении. Кроме того, мы не будем рассматривать большие числа. Мы просто найдем самый большой двоичный палиндром, который является произведением двух двоичных чисел меньше N
. Даже N = 15
требует времени, поэтому мы будем придерживаться 15
.

Я покажу подход, начав с обычного кода Scala, реализующего решение методом перебора:

object E4:
// класс, содержащий числа i,j и их произведение prod = i*j
case class Result(prod: Int, iMax: Int, jMax: Int)
// сравнивает Result-ы на основе произведения
given Ordering[Result] with
def compare(a: Result, b: Result): Int = a.prod compare b.prod
// вычисляет наибольший бинарный палиндром,
// являющийся произведением двух чисел, меньших start
def apply(start: Int): Result =
all(start).max
// итерация по парам (i, j), вычисление произведения и отслеживание палиндромов
def all(start: Int): Iterable[Result] =
for
i <- start to 1 by -1
j <- i to 1 by -1
prod = i * j
if isPalindrome(prod)
yield Result(prod, i, j)
// проверка, что число является полиндромом в бинарном представлении
def isPalindrome(i: Int): Boolean =
i.toBinaryString == i.toBinaryString.reverse

Однако код нелегко перенести непосредственно на программирование на уровне типа. Нам нужно преобразовать его так, чтобы он явно рекурсировал, отслеживал и обновлял максимум, а не использовал промежуточные переменные. Мы также отказались от класса Result

в пользу Tuple3
.

object E4_Explicit:
opaque type Result = (Int, Int, Int)
def apply(start: Int): Result = apply((1, 1, 1), start, start)
def apply(max: Result, i: Int, j: Int): Result =
apply1(max, (i * j, i, j))
def apply1(max: Result, iteration: Result): Result =
if isPalindrome(iteration._1) && iteration._1 > max._1 then
apply2(iteration, iteration)
else apply2(max, iteration)
def apply2(max: Result, iteration: Result): Result =
if iteration._3 == 1 then
if iteration._2 == 1 then max
else apply(max, iteration._2 - 1, iteration._2 - 1)
else apply(max, iteration._2, iteration._3 - 1)
def isPalindrome(i: Int): Boolean =
i.toBinaryString == i.toBinaryString.reverse

Код все еще необходимо преобразовать в программирование на уровне типа. По сути, утверждения и сравнения "if" могут быть проблематичными. См. Expanded

объект в Euler4.scala для обычного кода Scala, наиболее близкого к следующему коду уровня типа.

Что касается кода уровня типа, давайте начнем с проверки бинарных палиндромов:

type isPalindrome[D <: Dense] <: Bool =
Reverse[D] Compare D match
case EQ => True
case _ => False
println(toBoolean[isPalindrome[_3]])
// true
println(toBoolean[isPalindrome[_6]])
// false
println(toBoolean[isPalindrome[_15]])
// true

Затем давайте проверим, является ли число палиндромом и больше текущего максимального палиндрома:

infix type isGreaterThan[D <: Dense, Max <: Dense] <: Bool =
D Compare Max match
case GT => True
case _ => False
type isLargerPalindrome[D <: Dense, Max <: Dense] =
isPalindrome[D] && (D isGreaterThan Max)
println(toBoolean[isLargerPalindrome[_7, _3]])
// true
println(toBoolean[isLargerPalindrome[_3, _5]])
// false
println(toBoolean[isLargerPalindrome[_8, _5]])
// false

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

trait Pali:
type Result = (Dense, Dense, Dense)
type Apply[
max <: Dense,
iMax <: Dense,
jMax <: Dense,
i <: Dense,
j <: Dense,
P <: Pali
]
trait Pali0 extends Pali:
// Точка входа
type App[start <: Dense, P <: Pali] =
P match
case _ => Apply[_1, _1, _1, start, start, P]
// Рекурсия
type Apply[
max <: Dense,
iMax <: Dense,
jMax <: Dense,
i <: Dense,
j <: Dense,
P <: Pali
] =
P match
case _ => Apply1[max, iMax, jMax, i, j, Mult[j, i], P]
type Apply1[
max <: Dense,
iMax <: Dense,
jMax <: Dense,
i <: Dense,
j <: Dense,
prod <: Dense,
P <: Pali
] =
isLargerPalindrome[prod, max] match
case True => Apply2[prod, i, j, i, Dec[j], P]
case False => Apply2[max, iMax, jMax, i, Dec[j], P]
type Apply2[
max <: Dense,
iMax <: Dense,
jMax <: Dense,
i <: Dense,
j <: Dense,
P <: Pali
] =
j match
case _0 => Apply3[max, iMax, jMax, Dec[i], Dec[i], P]
case _ => Apply3[max, iMax, jMax, i, j, P]
type Apply3[
max <: Dense,
iMax <: Dense,
jMax <: Dense,
i <: Dense,
j <: Dense,
P <: Pali
] =
i match
case _0 => (max, iMax, jMax)
case _ => Pali0#Apply[max, iMax, jMax, i, j, P]
end Pali0

Запуск дает следующие результаты:

object Pali1 extends Pali0:
summon[App[_7, Pali1.type] =:= (_21, _7, _3)]
summon[App[_15, Pali1.type] =:= (Mult[_15, _13], _15, _13)]

Часть 6. Разнородные списки

Часть 6a. Основы разнородных списков

Исходная статья

HList

— это кортеж произвольной длины. Мы можем (в некоторой степени) легко перемещаться между длинами, объединяя кортежи или вытаскивая фрагмент из кортежа. Недостатки в том, что мы теряем специальный синтаксис для построения кортежей и типов, таких как (Int, Boolean)
и (3, true)
, иногда сталкиваемся с ограничениями компилятора или языка, а некоторые полезные операции требуют сложных типов.

HList

-ы ранее были продемонстрированы в Scala (и даже в Java). Реализация Scala использовала сочетание членов типа в иерархии HList
и класса типов.

Здесь мы реализуем четыре основные операции, которые позволяют нам реализовать другие операции вне иерархии HList

и без класса типов для каждой операции. Эти основные операции: добавление, свертка влево, свертка вправо и "заевшая молния" (stuck zipper). Под заевшей молнией подразумевается структура, которая указывает на позицию в HList
и предоставляет HList
до и после этой позиции, но не может перемещаться влево или вправо.

С помощью этих четырех операций мы можем определить:

  • Использование сверток: длина, добавление, обращение, обратное добавление, последний элемент
  • Использование "заевшей молнии": at
    (выбрать по индексу), drop
    (пропустить часть элементов), take
    (взять часть элементов), replace
    (заменить), remove
    (удалить), map
    /flatMap
    (преобразование по одному индексу), insert
    (вставить элемент), insert hlist
    (вставить hlist), splitAt
    (разделить по заданному индексу)

С некоторыми дополнительными классами типов мы также определим:

  • zip
    (поэлементное соединение двух списков)
  • разнородный apply
    (применить HList
    функции к входящим HList
    )

Для начала создадим очень простой HList

:

sealed trait HList
case object HNil extends HList:
self =>
def ::[A](v: A): HCons[A, HNil.type] = HCons(v, self)
final case class HCons[H, T <: HList](head: H, tail: T) extends HList:
self =>
def ::[A](v: A): HCons[A, HCons[H, T]] = HCons(v, self)
// алиасы для построения типов HList и для сопоставления с шаблоном
object HList:
type ::[H, T <: HList] = HCons[H, T]
val :: = HCons

Это базовое определение уже полезно. Например, ниже показано типобезопасное построение и извлечение:

// построение HList подобного Tuple3 ("str", true, 1.0)
val x = "str" :: true :: 1.0 :: HNil
// получение компонентов по вызову head/tail
val s: String = x.head
val b: Boolean = x.tail.head
val d: Double = x.tail.tail.head
// ошибка компиляции
// val e = x.tail.tail.tail.head
// или декомпозиция с помощью сопоставления с шаблоном
val f: (String :: Boolean :: Double :: HNil.type) => String =
case "s" :: false :: _ => "test"
case h :: true :: 1.0 :: HNil => h
// ошибка компиляции из-за несовпадения конкретных типов и общей длины кортежа
// case 3 :: "i" :: HNil => "invalid"
case _ => "unknown"

Обратите внимание, что мы используем ::

для HLists
, хотя на практике может быть лучше использовать :+:
или другое имя, чтобы отличить его от ::
, используемого для объединения и сопоставления списков.

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

Часть 6b. Свертка HList

Исходная статья

Теперь, основываясь на базовом определении HList

, реализуем свертки. Они будут отличаться от сверток, предложенных в исходной статье, потому что в Scala 3 нет возможности обращаться к неопределенным типам, как показано ниже:

type Foldr[Value, F <: Fold[Any, Value], I <: Value] =
F#Apply[H, tail.Foldr[Value, F, I]]
// Ошибка компилятора: F - это не конкретный тип, вызывать Apply на нем непозволительно

Fold

Определим трейт Fold

, позволяющий сворачивать не только типы, но и значения:

trait Fold[-Elem, Value]:
type Apply[N <: Elem, Acc <: Value] <: Value
def apply[N <: Elem, Acc <: Value](n: N, acc: Acc): Apply[N, Acc]

Тип Apply

предназначен для сворачивания типов, а метод apply
- для сворачивания значений. Value
— это тип результата и он же обеспечивает границу, позволяющую выполнять рекурсию на уровне типа.

Определим дополнительный трейт FoldAny

для свертки разнородных списков (где Elem
- это Any
):

trait FoldAny[Value] extends Fold[Any, Value]:
type Foldr[H <: HList, I <: Value] <: Value =
H match
case HNil.type => I
case HCons[h, t] => Apply[h, Foldr[t, I]]
def foldr[H <: HList, I <: Value](hlist: H, i: I): Value =
hlist match
case HNil => i
case HCons(head, tail) => apply(head, foldr(tail, i))
type Foldl[H <: HList, I <: Value] <: Value =
H match
case HNil.type => I
case HCons[h, t] => Foldl[t, Apply[h, I]]
def foldl[H <: HList, I <: Value](hlist: H, i: I): Value =
hlist match
case HNil => i
case HCons(head, tail) => foldl(tail, apply(head, i))

I

— тип начального значения. Для пустого списка возвращаем его, а для непустого - разделяем список на головной элемент и остаточный список. В зависимости от направления, в котором происходит свертка, либо сворачиваем головной элемент и результат рекурсии, примененный к остатку, либо вызываем рекурсию для хвоста и свертки головного элемента и начального значения.

Функции, использующие свертки

Мы можем определить функцию расчета длины списка на уровне типа в HList

, используя Inc
:

type Inc = FoldAny[Nat] {
type Apply[N <: Any, Acc <: Nat] = Succ[Acc]
}
type Length[H <: HList] = Inc#Foldr[H, _0]
type LengthViaFoldLeft[H <: HList] = Inc#Foldl[H, _0]
// Проверка
summon[Length[x.type] =:= Nat._3]
summon[LengthViaFoldLeft[x.type] =:= Nat._3]

Используя функцию свертки, которая просто добавляет текущий тип итерации к накопленному типу HList

, можно определить добавление, обращение и обращение с последующим добавлением на уровне типа:

object AppHCons extends FoldAny[HList]:
type Apply[N <: Any, H <: HList] = N :: H
// будет использоваться позднее для реализации на уровне значений
def apply[A, B <: HList](a: A, b: B) = HCons(a, b)
type :::[A <: HList, B <: HList] =
AppHCons.Foldr[A, B]
type Reverse_:::[A <: HList, B <: HList] =
AppHCons.Foldl[A, B]
type Reverse[A <: HList] =
AppHCons.Foldl[A, HNil.type]

Определим методы расширения, позволяющие вычислять значения на уровне типов:

object Length extends FoldAny[Int]:
type Apply[N <: Any, Acc <: Int] = Int
def apply[A, B <: Int](a: A, b: B): Apply[Any, Int] = b + 1
extension [A <: HList](a: A)
def length: Int = Length.foldr(a, 0)
def :::[B <: HList](b: B): HList = AppHCons.foldr(a, b)
def reverse_:::[B <: HList](b: B): HList = AppHCons.foldl(a, b)
def reverse: HList = AppHCons.foldl(a, HNil)

Некоторые примеры использования определенных выше методов:

// построение разнородного списка длины 3
// со следующими типами Int :: String :: List[Char] :: HNil
val a = 3 :: "ai4" :: List('r', 'H') :: HNil
// построение разнородного списка длины 4
// со следующими типами Char :: Int :: Char :: String :: HNil
val b = '3' :: 2 :: 'j' :: "sdfh" :: HNil
// объединение двух HLists
val ab = a ::: b
// проверка значения путем сопоставления с шаблоном
val checkAB = ab match
case 3 :: "ai4" :: List('r', 'H') :: '3' :: 2 :: 'j' :: "sdfh" :: HNil =>
true
case _ => false
require(checkAB)
// проверка длины HList
require(ab.length == 7)
// обратимость
val reversed = b.reverse
// проверка значения путем сопоставления с шаблоном
val checkReversed = reversed match
case "sdfh" :: 'j' :: 2 :: '3' :: HNil => true
case _ => false
require(checkReversed)
// обращение, а затем добавление
val reverseAppend = a reverse_::: b
// проверка значения
val checkReverseAppend = reverseAppend match
case List('r', 'H') :: "ai4" :: 3 :: '3' :: 2 :: 'j' :: "sdfh" :: HNil =>
true
case _ => false
require(checkReverseAppend)

Часть 6c. Индексирование HList

Исходная статья

Далее мы реализуем некоторые операции индексации для HList

-ов. Нам нужно отбросить или взять n
элементов, получить элемент с индексом i
, разделить HList
на два списка HList
по индексу i
и т.д.

Идея состоит в том, чтобы взять HList

и Nat
и создать индексированную zip-структуру. Эта структура предоставляет значение и тип по индексу, заданному Nat
. Также она предоставляет HList
до и после индекса.

Однако Indexed

— это застрявшая "молния". Он не может двигаться влево или вправо, а фиксируется на исходном индексе (к сожалению, даже эта застрявшая молния может стать проблемой для компилятора).

Базовый индексированный интерфейс выглядит так:

sealed trait Indexed:
type Before <: HList
type At
type After <: HList
def withIndex[R](f: (Before, At, After) => R): R

Например, индексированный экземпляр для Nat

равного _2
и HList
равного 3 :: true :: "blue" :: 'h' :: HNil
:

new Indexed:
type Before = Int :: Boolean :: HNil.type
type At = String
type After = Char :: HNil.type
def withIndex[R](f: (Before, At, After) => R): R =
f(3 :: true :: HNil, "blue", 'h' :: HNil)

Прежде чем рассмотреть создание экземпляра Indexed

для произвольных Nat
и HList
, давайте убедимся, что можно реализовать несколько операций индексирования с помощью withIndex
:

// получение элемента по индексу
def at: At = withIndex((_, a, _) => a)
// удаление всех элементов перед заданным индексом
def drop: HCons[At, After] = withIndex((_, a, t) => HCons(a, t))
// получение всех элементов перед заданным индексом
def take: Before = withIndex((b, _, _) => b)
// замена значения текущего индекса на 'a'
def replace[A](a: A): HList = withIndex((b, _, t) => b ::: HCons(a, t))
// удаление значения текущего индекса
def remove: HList = withIndex((b, _, t) => b ::: t)
// применение функции 'f' к текущему значению
def map[B](f: At => B): HList = withIndex((b, a, t) => b ::: HCons(f(a), t))
// применение функции 'f', возвращающей HList, к текущему значению
// и вставка полученного списка на место текущего индекса
def flatMap[B <: HList](f: At => B): HList =
withIndex((b, a, t) => b ::: f(a) ::: t)
// вставка заданного значения
def insert[C](c: C): HList =
withIndex((b, a, t) => b ::: HCons(c, HCons(a, t)))
// вставка заданного списка HList в текущий индекс
def insertH[C <: HList](c: C): HList =
withIndex((b, a, t) => b ::: c ::: HCons(a, t))
// возвращает список HList, лежащий перед текущим индексом, и HList, начинающийся с заданного индекса
def splitAt: (Before, ::[At, After]) =
withIndex((b, a, t) => (b, HCons(a, t)))

Реализация разделена на два случая. Первый — Indexed0

, представляющий местоположение указателя. Он указывает на головной элемент ячейки HCons
. Хвост ячейки — это After
, а Before
пуст.

final case class Indexed0[H, T <: HList](hc: H :: T) extends Indexed:
type Before = HNil.type
type At = H
type After = T
def withIndex[R](f: (Before, At, After) => R): R = f(HNil, hc.head, hc.tail)

IndexedN

создает список Before
HList
. Он добавляет элемент в начало к другому Indexed
Before
и делегирует элементы At
и After
этому Indexed
. В конечном счете, завершающий Indexed
должен быть Indexed0
.

final case class IndexedN[H, I <: Indexed](h: H, iTail: I) extends Indexed:
type Before = H :: iTail.type#Before
type At = iTail.type#At
type After = iTail.type#After
def withIndex[R](f: (Before, At, After) => R): R =
iTail.withIndex((before, at, after) => f(HCons(h, before), at, after))

Теперь нам нужно получить индексированный объект для HList

. Для этого мы определяем тип toI[H <: HList, N <: Nat]
. Этот элемент типа определяет индексированный тип для HList
и Nat
. Затем мы можем использовать неявные выражения для предоставления этого типа.

type toI[H <: HList, N <: Nat] <: Indexed =
H match
case HNil.type => Nothing
case HCons[h, t] =>
// совпадение по N:
// Если он равен _0, тип Indexed должен
// указывать на эту ячейку (то есть это Indexed0)
// в противном случае индекс будет справа,
// поэтому вернитесь к N-1 и верните IndexedN
N match
case _0 => Indexed0[h, t]
case Succ[n] => IndexedN[h, toI[t, n]]

Итак, учитывая HList h

и индекс Nat N
, мы знаем, что нам нужен индексированный тип toI[A, N]
. Нам нужна функция A => toI[A, N]
. Мы можем сделать это с помощью неявных значений следующим образом:

// определено как метод расширения для HList
extension [A <: HList](a: A)
...
def i[N <: Nat](using in: A => toI[A, N]): toI[A, N] = in(a)
object Indexed:
given indexed0[H, T <: HList]: (HCons[H, T] => Indexed0[H, T]) =
hc => new Indexed0[H, T](hc)
given indexedN[H, T <: HList, I <: Indexed](using
iTail: T => I
): (HCons[H, T] => IndexedN[H, I]) =
hc => new IndexedN[H, I](hc.head, iTail(hc.tail))

Примеры:

val x = 3 :: true :: "asfd" :: false :: 'k' :: () :: 13 :: 9.3 :: HNil
// получение булева значения по индексу 3
val b2: Boolean = x.i[_3].at
// false
// удалить все значения перед индексом 3 и затем получить первое значение
val pre: Boolean = x.i[_3].drop.i[_0].at
// false
// замена булева значения по индексу 3 на число 19
val rep = x.i[_3].replace(19)
// 3 :: true :: "asfd" :: 19 :: 'k' :: () :: 13 :: 9.3 :: HNil
// преобразование значения по индексу 4 на `true` если символ в нижнем регистре, иначе - `false`
val mp = x.i[_4].map(_.isLower)
// 3 :: true :: "asfd" :: false :: true :: () :: 13 :: 9.3 :: HNil
// Удаление значения по индексу 5
val rm = x.i[_5].remove
// 3 :: true :: "asfd" :: false :: 'k' :: 13 :: 9.3 :: HNil
// преобразование значения по индексу 2 на HList, созданного на основе значения
val fmp = x.i[_2].flatMap( s => s.charAt(0) :: s.substring(1) :: HNil )
// 3 :: true :: 'a' :: "sfd" :: false :: 'k' :: () :: 13 :: 9.3 :: HNil
// вставка значения в начало HList
val ins0 = x.i[_0].insert(List(3,4))
// List(3, 4) :: 3 :: true :: "asfd" :: false :: 'k' :: () :: 13 :: 9.3 :: HNil
// вставка значения по индексу 7
val ins7 = x.i[_7].insert(-3.0f)
// 3 :: true :: "asfd" :: false :: 'k' :: () :: 13 :: -3.0 :: 9.3 :: HNil
// вставка HList по индексу 3
val insH = rm.i[_3].insertH( 'h' :: b2 :: Some(3) :: None :: HNil )
// 3 :: true :: "asfd" :: 'h' :: false :: Some(3) :: None :: false :: 'k' :: 13 :: 9.3 :: HNil
// разбиение HList по индексу 6
val (aa, bb) = ins7.i[_6].splitAt
// (3 :: true :: "asfd" :: false :: 'k' :: () :: HNil, 13 :: -3.0 :: 9.3 :: HNil)
// аналог удаления справа
val dropRight = x.reverse.i[_3].drop.reverse
// 3 :: true :: "asfd" :: false :: 'k' :: HNil

Далее мы увидим, как определить zip

и unzip
для объединения и разделения HL-списков кортежей.

Часть 6d. HList Zip/Unzip

Исходная статья

Для zip

и unzip
нужно определить некоторые классы типов. Сначала мы определим класс типов HZip
, который принимает два списка HList
и создает сжатый список HList
.

sealed trait HZip[A <: HList, B <: HList, Result <: HList]:
def apply(a: A, b: B): Result

Реализуем класс типов с двумя основными вариантами:

  • HZip[HNil.type, HNil.type, HNil.type]
  • HZip[HA :: TA, HB :: TB, (HA, HB) :: TR]
    .

Сжатие двух HNil

создает HNil
:

given HZip[HNil.type, HNil.type, HNil.type] with
def apply(a: HNil.type, b: HNil.type): HNil.type = HNil

Сжатие двух ячеек HCons

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

given hzipCons[HA, HB, TA <: HList, TB <: HList, TR <: HList](using
hzipTail: HZip[TA, TB, TR]
): HZip[HA :: TA, HB :: TB, (HA, HB) :: TR] with
def apply(a: HA :: TA, b: HB :: TB): (HA, HB) :: TR =
HCons((a.head, b.head), hzipTail(a.tail, b.tail))

Два дополнительных случая, hzipNil1

и hzipNil2
, обрабатывают несовпадающие длины путем простого усечения более длинного списка.

given hzipNil1[H, T <: HList]: HZip[H :: T, HNil.type, HNil.type] with
def apply(a: H :: T, b: HNil.type): HNil.type = HNil
given hzipNil2[H, T <: HList]: HZip[HNil.type, H :: T, HNil.type] with
def apply(a: HNil.type, b: H :: T): HNil.type = HNil

Мы подключаем эти реализации к методам расширения и можем вызывать zip

непосредственно в HList
.

extension [A <: HList](a: A)
infix def zip[B <: HList, R <: HList](b: B)(using hzip: HZip[A, B, R]): R =
hzip(a, b)

Примеры:

// разнородный список длины 3
// с типом Int :: String :: List[Char] :: HNil
val a = 3 :: "ai4" :: List('r', 'H') :: HNil
// разнородный список длины 4
// с типом Char :: Int :: Char :: String :: HNil
val b = '3' :: 2 :: 'j' :: "sdfh" :: HNil
// два свернутых HLists
val c = a zip b
// (3, '3') :: ("ai4", 2) :: (List('r', 'H'), 'j') :: HNil
// ещё одна свертка
val cc = c zip c.tail
// ((3, '3'), ("ai4", 2)) :: (("ai4", 2), (List('r', 'H'), 'j')) :: HNil
// проверка типов
// заметим, что четвертый элемент b удален,
// также как это происходит при свертке однородных списков List
val checkCType: (Int, Char) :: (String, Int) :: (List[Char], Char) :: HNil.type = c
val checkCCType: ((Int, Char), (String, Int)) :: ((String, Int), (List[Char], Char)) :: HNil.type = cc

Далее мы определим класс типов unzip

, который принимает HList
кортежей и разделяет его на два HList
по компонентам:

trait Unzip[H <: HList, R1 <: HList, R2 <: HList]:
infix def unzip(h: H): (R1, R2)

При распаковке HNil

создается HNil
.

object Unzip:
given Unzip[HNil.type, HNil.type, HNil.type] with
def unzip(h: HNil.type) = (HNil, HNil)

Для HCon

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

given unzipCons[H1, H2, T <: HList, TR1 <: HList, TR2 <: HList](using
unzipTail: Unzip[T, TR1, TR2]
): Unzip[(H1, H2) :: T, H1 :: TR1, H2 :: TR2] with
def unzip(h: (H1, H2) :: T): (H1 :: TR1, H2 :: TR2) =
val (t1, t2) = unzipTail.unzip(h.tail)
(HCons(h.head._1, t1), HCons(h.head._2, t2))

Опять же, нам просто нужно подключить добавить метод расширения к HList

.

extension [A <: HList](a: A)
def unzip[R1 <: HList, R2 <: HList](using un: Unzip[A, R1, R2]): (R1, R2) =
un unzip a

Основываясь на примере выше,

// разархивирование свернутых HList-ов
val (cc1, cc2) = cc.unzip
val (ca, cb) = cc1.unzip
// ca = 3 :: "ai4" :: HNil
// cb = '3' :: 2 :: HNil
// проверка типов
val checkCC1: (Int, Char) :: (String, Int) :: HNil.type = cc1
val checkCC2: (String, Int) :: (List[Char], Char) :: HNil.type = cc2
val checkCa: Int :: String :: HNil.type = ca
val checkCb: Char :: Int :: HNil.type = cb

Далее мы рассмотрим применение функций к значениям HList

.

Часть 6e. HList Apply

Исходная статья

Мы продолжим определение happly

, разнородного метода применения функций. Он принимает HList
функций и применяет их к соответствующим значениям во входном HList
, создавая HList
результатов.

Во-первых, пример использования выглядит так:

// два HList с типом Double :: Char :: HNil
val y1 = 9.75 :: 'x' :: HNil
val y2 = -2.125 :: 'X' :: HNil
// Функции применения.
// Тип z: (Double => Double) :: (Char => Boolean) :: HNil
val z = ((_: Double) + .5) :: ((_: Char).isUpper) :: HNil
// применение первого параметра HList z ко второму параметру y1
val z1 = happly(z)(y1)
// проверка типов
val z1Types: Double :: Boolean :: HNil.type = z1
// проверка значения
assertEquals(z1, 10.25 :: false :: HNil)
// применение первого параметра HList z ко второму параметру y2
val z2 = happly(z)(y2)
// проверка типов
val z2Types: Double :: Boolean :: HNil.type = z2
// проверка значения
assertEquals(z2, -1.625 :: true :: HNil)

Мы реализуем Happly

, используя класс типов HApply
, который по сути является Function1
. На самом деле мы не можем использовать Function1
, потому что мешают существующие неявные условия, связанные с Function1
.

sealed trait HApply[-In, +Out]:
def apply(in: In): Out

Идея состоит в том, что, учитывая HList

функций, мы создаем HApply
, который принимает HList
параметров "правильного" типа и выдает HList
результатов. Для функции z
из примера нам нужен HApply
типа:

HApply[(Double :: Char :: HNil), (Double :: Boolean :: HNil)]

Для этого есть два основных случая: HNil

и HCons
. Самый простой случай — это сопоставление HNil
с HNil
:

given HApply[HNil.type, HApply[HNil.type, HNil.type]] with
def apply(h: HNil.type): HApply[HNil.type, HNil.type] =
new HApply[HNil.type, HNil.type]:
def apply(in: HNil.type): HNil.type = HNil

Как обычно, интересен случай с HCons

. Мы принимаем ячейку HCons
с заголовком, являющимся функцией, и создаем HApply
, который будет принимать входную ячейку HCons
требуемого типа. Затем HApply
применяет функцию head
к значению head
и выполняет рекурсию по остатку. HApply
, используемый для рекурсии, предоставляется неявно, и именно поэтому мы требуем, чтобы один HList
был HList
, полностью состоящим из функций, а другой HList
содержал значения правильного типа, которые будут предоставляться в качестве входных данных для этих функций.

given happlyCons[InH, OutH, TF <: HList, TIn <: HList, TOut <: HList](using
applyTail: HApply[TF, HApply[TIn, TOut]]
): HApply[(InH => OutH) :: TF, HApply[InH :: TIn, OutH :: TOut]] with
def apply(h: (InH => OutH) :: TF): HApply[InH :: TIn, OutH :: TOut] =
new HApply[InH :: TIn, OutH :: TOut]:
def apply(in: InH :: TIn): OutH :: TOut =
HCons(h.head(in.head), applyTail(h.tail)(in.tail))

В примере мы имеем:

val y1 = 9.75 :: 'x' :: HNil
val z = ((_: Double) + .5) :: ((_: Char).isUpper) :: HNil

Итак, для happly(z)(y1)

наша неявная конструкция строится с помощью:

happlyCons[Double, Double, Char => Boolean :: HNil, Char :: HNil, Boolean :: HNil](
happlyCons[Char, Boolean, HNil, HNil, HNil](
happlyNil
)
)

Первый метод applyCons

создает HApply
, который использует заголовок z
, функцию типа Double => Double
, для сопоставления HList
с заголовком типа Double
с HList
с заголовком типа Double
. Он использует HApply
из второго happlyCons
для отображения остатка входного HList
.

Этот второй HApply

использует второй элемент z
, функцию типа Char => Boolean
, для сопоставления HList
с заголовком типа Char
с HList
с заголовком типа Boolean
. Поскольку это последний элемент, рекурсия заканчивается отображением happlyNil
HNil
в HNil
.

Наконец, мы определяем точку входа. Учитывая HList

функций и HList
аргументов этих функций, мы используем happly
, чтобы неявно получить HApply
и создать с его помощью результирующий HList
:

def happly[H <: HList, In <: HList, Out <: HList](h: H)(in: In)(using
toApply: HApply[H, HApply[In, Out]]
): Out =
toApply(h)(in)

Часть 6f. Получение экземпляров классов типов с помощью HLists

Исходная статья

Хотя некоторые части этой серии не имеют прямого практического применения (Project Euler problem 4 в системе типов), сами HLists

определенно практичны. Механизм задач в sbt позволяет избежать необходимости использования большого количества шаблонов или использования препроцессора, сохраняя при этом безопасность типов за счет использования HList
-ов (и KList
-ов — гетерогенного списка с конструктором типа, общим для каждой ячейки, который будет обсуждаться в части 8).

Однако в этой главе давайте посмотрим, как мы можем использовать HList

-ы, чтобы уменьшить еще одну категорию шаблонов. Это связано с определением экземпляров классов типов, особенно тех, которые созданы для определенного типа данных. В примерах используется scala.Equiv
. Если вы не знакомы с Equiv
, это класс типов для равенства:

trait Equiv[T]:
def equiv(a: T, b: T): Boolean

Экземпляр для Int

может выглядеть так:

given Equiv[Int] with
def equiv(a: Int, b: Int): Boolean = a == b

Для Tuple2

мы создаем экземпляры Equiv
для его членов:

given pairEquiv[A, B](using a: Equiv[A], b: Equiv[B]): Equiv[(A, B)] with
def equiv(t1: (A, B), t2: (A, B)): Boolean =
a.equiv(t1._1, t2._1) && b.equiv(t1._2, t2._2)

Нам нужно будет повторить это для каждого TupleN

. Это немного раздражает, но не так уж плохо. Однако классы пользователей представляют собой препятствие. В частности, мы будем рассматривать кейс-классы, поскольку Scala фокусируется на создании методов для них. Очевидно, что пользователи могут создавать столько кейс-классов, сколько захотят. Вы не можете заранее написать Equiv
для всех этих классов. Вместо этого для каждого кейс-класса пользователю необходимо сделать что-то вроде:

case class Example[A, B](a: A, b: Seq[B], c: Int)
given exampleEquiv[A, B](using
a: Equiv[A],
b: Equiv[Seq[B]],
c: Equiv[Int]
): Equiv[Example[A, B]] with
def equiv(e1: Example[A, B], e2: Example[A, B]): Boolean =
a.equiv(e1.a, e2.a) && b.equiv(e1.b, e2.b) && c.equiv(e1.c, e2.c)

Это чисто шаблонный подход, поскольку мы не говорим ничего нового. Мы дублируем логику Equiv

для Tuple3
. Класс Example
по сути представляет собой Tuple3[A, Seq[B], Int]
, а HList
-ы способны представлять кортежи произвольной длины. Мы могли бы написать функции для преобразования между HList
-ами и нашими кейс-классами. Если мы затем создадим экземпляры нашего класса типов для HCons
и HNil
, а также для любого кейс-класса, который обеспечивает преобразование в HList
-ы и обратно, то сможем автоматически получить экземпляры класса типа для любого кейс-класса.

Сопутствующий объект кейс-класса содержит неявные преобразования в соответствующий тип HList

и обратно. Для приведенного выше класса Example
это примерно эквивалентно следующему определению, данному вручную:

object Example:
extension [A, B](e: Example[A, B])
def toHList: A :: Seq[B] :: Int :: HNil.type = e.a :: e.b :: e.c :: HNil
def fromHList[A, B](hl: A :: Seq[B] :: Int :: HNil.type): Example[A, B] =
val a :: b :: c :: HNil = hl
Example(a, b, c)

Затем мы реализуем Equiv

для HList
и для всего, что конвертируется в HList
:

object EquivHList:
// HNil === HNil
given Equiv[HNil.type] with
def equiv(a: HNil.type, b: HNil.type) = true
// заданы Equiv для заголовка и остатка,
// (h1 :: t1) === (h2 :: t2) тогда, когда
// (h1 === h2) и (t1 === t2)
given equivHCons[H, T <: HList](using
equivH: Equiv[H],
equivT: Equiv[T]
): Equiv[HCons[H, T]] with
def equiv(a: HCons[H, T], b: HCons[H, T]): Boolean =
equivH.equiv(a.head, b.head) && equivT.equiv(a.tail, b.tail)
// дано:
// - тип T, конвертируемый в HList типа HL
// - экземпляр Equiv для HL
// мы можем создать Equiv[T] приведя T к HL и используя Equiv[HL]
given equivHListable[T, HL <: HList](using
toHList: T => HL,
equivHL: Equiv[HL]
): Equiv[T] with
def equiv(a: T, b: T): Boolean =
equivHL.equiv(toHList(a), toHList(b))

Итак, нам нужно написать что-то вроде EquivHList

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

case class Example[A, B](a: A, b: Seq[B], c: Int)
assert(Example('a', Seq(1, 2, 3), 19) === Example('a', Seq(1, 2, 3), 19))
assert(Example('b', Seq(1, 2, 3), 1) !== Example('a', Seq(1, 2, 3), 1))

В этом примере предполагается, что ===

и !==
предоставляются неявным преобразованием, например:

extension [A](a1: A)
def ===(a2: A): Boolean = Equiv.universal.equiv(a1, a2)
def !==(a2: A): Boolean = !Equiv.universal.equiv(a1, a2)

Predef.conforms

также необходимо скрыть. В противном случае equivHListable
расходится. Было бы хорошо иметь хорошее решение для этого.

И последнее замечание: даже если компилятор автоматически не генерирует преобразования, вручную определить преобразования в HLists

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

В следующем и последнем разделе этой части будет рассказано о некоторых способах упростить работу со списками HList

в Scala.

Часть 6g. Type-indexed HLists

Исходная статья

В 6c мы выполняли различные операции на основе позиции в HList

, выбранной по натуральному числу уровня типа (Nat
). В этом посте мы подбираем позиции по типам.

Подобно 6c, мы берем HList

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

В исходном подходе использовалась функция уровня типа для вычисления необходимого индексированного типа полностью на уровне типа:

type toI[H <: HList, N <: Nat] <: Indexed

Для типа HList

HL
и Nat
N
toI
предоставил индексированный тип для позиции, выбранной номером N
. Затем мы могли бы потребовать неявный индексированный параметр типа HL#toI[N]
и определить неявные значения, которые создают запрошенные индексированные значения.

Однако здесь это не сработает. Мы хотим выбрать позицию в HList

, где тип ячейки H
совпадает с запрошенным типом S
. Мы не можем вычислить индексированный тип, используя решение только на уровне типа, поскольку не существует общей функции равенства на уровне типа. Нам нужно полагаться на неявное доказательство равенства двух типов, используя =:=
. Более конкретно, вы не можете написать:

type TypeEq[A, B] <: Bool

но вы можете потребовать доказательство (как значение) того, что A

и B
равны:

def typeEq[A,B](implicit ev: A =:= B) ...

Помните из 6c, что Indexed

состоит из двух частей: Indexed0
, предоставляющий местоположение указателя в HList
, и IndexedN
, предоставляющий местоположения перед указателем. Чтобы выбрать позицию по типу, мы будем использовать класс-оболочку, которая записывает выбранный тип S
и сопоставление HList
с Indexed
:

sealed trait Tip[S, HL <: HList, Ind <: Indexed]:
def apply(hl: HL): Ind

Таким образом, экземпляр Tip

для HList
HL
и типа S
может предоставить индексированный экземпляр, в котором мы можем вызывать такие методы, как at
, remove
или map
.

Фактическая работа — создание экземпляров Tip

. Существует один случай для Indexed0
и один для IndexedN
. Когда у нас есть доказательства того, что тип заголовка ячейки HCons
совпадает с искомыми типом, то мы предоставляем значение Indexed0
, которое указывает на эту ячейку. Опять же, мы обертываем ее в Tip
, чтобы отметить, что мы выбрали ячейку типа S
, и предоставить функцию, которая сопоставляет ячейку HCons
с индексированным экземпляром, который нам в конечном итоге нужен.

given tindexed0[S, H, T <: HList](using
ev: S =:= H
): Tip[S, H :: T, Indexed0[H, T]] with
def apply(hc: H :: T): Indexed0[H, T] = Indexed0[H, T](hc)

Indexed0

указывает на заголовок выбранной ячейки HCons
и ссылается на ее остаток. Затем нужно создать экземпляры IndexedN
из завершающего Indexed0
, чтобы ссылаться на ячейки перед выбранной. Для ячейки HCons
типа H :: T
мы требуем, чтобы тип S
был найден в хвосте T
. То есть нам нужен экземпляр Tip
для хвостового типа T
, искомый тип S
и некоторый индексированный экземпляр I
. Из этого мы можем предоставить подсказку для текущей ячейки.

given tindexedN[H, T <: HList, I <: Indexed, S](using
iTail: Tip[S, T, I]
): Tip[S, H :: T, IndexedN[H, I]] with
def apply(hc: H :: T): IndexedN[H, I] =
IndexedN[H, I](hc.head, iTail(hc.tail))

Обратите внимание, что это приведет к неоднозначным неявным значениям, если имеется несколько ячеек одного типа.

Чтобы связать вышеизложенное с HList

для запрошенного типа, мы добавляем метод t
в HCons
:

final case class HCons[H, T <: HList](head: H, tail: T) extends HList:
self =>
def t[S]: TipDummy[S, H :: T] = TipDummy[S, H :: T](self)
sealed class TipDummy[S, HL <: HList](val hl: HL)

где H :: T

— тип ячейки HCons
. Затем мы обеспечиваем неявное преобразование из TipDummy
в Indexed
:

object TipDummy:
given fromTipDummy[S, HL <: HList, I <: Indexed](using
tip: Tip[S, HL, I]
): Conversion[TipDummy[S, HL], I] with
def apply(dummy: TipDummy[S, HL]): I =
tip(dummy.hl)

Промежуточный TipDummy

выполняет применение параметра частичного типа. Мы хотим иметь возможность явно указывать тип для выбора без необходимости предоставления типов Indexed
и HList
.

Примеры:

val x = 3 :: true :: "asfd" :: 'k' :: () :: 9.3 :: HNil
// получение значения типа Boolean
val b2: Boolean = x.t[Boolean].toIndexed.at
// true
// удаление значений перед значением типа String
val pre = x.t[String].drop
// "asfd" :: 'k' :: () :: 9.3 :: HNil
// замена значения типа String на число 19
val rep = x.t[String].replace(19)
// 3 :: true :: 19 :: 'k' :: () :: 9.3 :: HNil
// замена символа Char на true если он в нижнем регистре, false - в ином случае
val mp = x.t[Char].map(_.isLower)
// 3 :: true :: "asfd" :: true :: () :: 9.3 :: HNil
// удаление значения типа Unit
val rm = x.t[Unit].remove
// 3 :: true :: "asfd" :: 'k' :: 9.3 :: HNil
// замена значения типа String на HList, построенный на её значениях
val fmp = x.t[String].flatMap(s => s.charAt(0) :: s.substring(1) :: HNil)
// 3 :: true :: 'a' :: "sfd" :: 'k' :: () :: 9.3 :: HNil
// вставка значения перед полем типа Int
val ins0 = x.t[Int].insert(List(3, 4))
// List(3, 4) :: 3 :: true :: "asfd" :: 'k' :: () :: 9.3 :: HNil
// вставка значения перед полем типа Double
val ins7 = x.t[Double].insert(-3.0f)
// 3 :: true :: "asfd" :: 'k' :: () :: -3.0 :: 9.3 :: HNil
// вставка HList перед значением типа String
val insH = x.t[String].insertH('h' :: b2 :: Some(3) :: None :: HNil)
// 3 :: true :: 'h' :: true :: Some(3) :: None :: "asfd" :: 'k' :: () :: 9.3 :: HNil
// разбиение HList перед значением с типом Unit
val (aa, bb) = x.t[Unit].splitAt
// (3 :: true :: "asfd" :: 'k' :: HNil, () :: 9.3 :: HNil)
// аналог операции удаление справа
type R = Double :: Unit :: Char :: String :: Boolean :: Int :: HNil.type
val dropRight = x.reverse.asInstanceOf[R].t[Char].drop.reverse
// 3 :: true :: "asfd" :: 'k' :: HNil

Часть 7. Естественные литералы преобразования

Исходная статья

В исходной статье разбирается проблема определения естественного преобразования?

В версии Scala, используемой в исходной статье, естественные преобразования вызывали проблемы. Например, мы нельзя было определить функцию, которая сопоставляет Option[T]

с List[T]
для каждого T
. Нельзя было определить toList
так, чтобы компилировалось следующее:

val toList = ...
val a: List[Int] = toList(Some(3))
assert(List(3) == a)
val b: List[Boolean] = toList(Some(true))
assert(List(true) == b)

Но в Scala 3 есть полиморфные типы функций позволяющие определить функцию:

val toList: [A] => Option[A] => List[A] =
[A] => (opt: Option[A]) => opt.toList
val a: List[Int] = toList(Some(3))
assert(List(3) == a)
val b: List[Boolean] = toList(Some(true))
assert(List(true) == b)

Часть 8a. Мотивация KList

Исходная статья

В части 8 рассмотрим операции с кортежами произвольной арности над конструктором типа. Это разнородные списки высшего порядка, которые будем называть KList

. Чтобы понять, почему нам может понадобиться такая структура, для простоты начнем с Tuple2
.

Рассмотрим некоторые базовые преобразования элементов Tuple2

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

def map1[A <: C, B <: C, C, D](t: (A, B), f: C => D): (D, D) =
(f(t._1), f(t._2))
map1(("3", true), (_: Any).hashCode)
// (51, 1231)

Или мы можем предоставить две отдельные функции для независимой работы с каждым компонентом:

def map2[A, B, C, D](t: (A, B), f: A => C, g: B => D): (C, D) =
(f(t._1), g(t._2))
map2((1, true), (_: Int) + 1, !(_: Boolean))
// (2, false)

Теперь рассмотрим Tuple2

, в котором типы обоих компонентов создаются одним и тем же конструктором типа, например (List[Int], List[Boolean])
или (Option[String], Option[Double])
.

Одна полезная операция над такой структурой выглядит так:

def transform[F[_], A, B, G[_]](k: (F[A], F[B]), g: [C] => F[C] => G[C]): (G[A], G[B]) =
(g(k._1), g(k._2))

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

, которое мы определили в части 7:

val toList: [A] => Option[A] => List[A] =
[A] => (opt: Option[A]) => opt.toList
// чтобы в качестве типа получать Option[T],
// а не Some[T] или None
def some[T](t: T): Option[T] = Some(t)
def none[T]: Option[T] = None
transform[Option, Int, String, List]((some(3), some("str")), toList),
// (List(3), List("str"))
transform[Option, Boolean, Double, List]((some(true), none[Double]),toList),
// (List(true), List())

В части 6 мы занимались обобщением TupleN

на случай произвольной арности. В части 8 мы обобщим операции преобразования и связанные с ними операции на разнородные списки с помощью конструктора типов.

Часть 8b. Основы KList

Исходная статья

При отсутствии типов ранга 2 может быть полезно иметь разнородный список более высокого порядка, который здесь назовем KList

. KList
определяет конструктор типа M[_]
, который используется для создания типа для всех ячеек в списке. Параметр, передаваемый в конструктор этого типа, может быть разным для каждой ячейки, которая является разнородной частью. Одним из вариантов использования KList
является определение общей функции zipWith
. KList
-ы также используются при реализации механизма задач в sbt. Каждое из этих приложений будет описано в последующих постах.

Начнем с базового определения KList

, которое выглядит так:

sealed trait KList[+M[_], HL <: HList]
final case class KCons[H, T <: HList, +M[_]](head: M[H], tail: KList[M, T])
extends KList[M, H :: T]:
self =>
// добавление в начало
def :^:[N[X] >: M[X], G](g: N[G]): KCons[G, H :: T, N] = KCons(g, self)
sealed class KNil extends KList[Nothing, HNil.type]:
def :^:[M[_], H](h: M[H]): KCons[H, HNil.type, M] = KCons(h, this)
object KNil extends KNil
object KList:
// более удобный псевдоним для сопоставления с образцом
val :^: : KCons.type = KCons

Он похож на HList

, за исключением конструктора типа M
. Мы сохраняем тип head
-а в KCons
двумя частями: конструктор типа M
, общий для всех ячеек в KList
, и параметр типа M
, специфичный для этой ячейки. Полный тип заголовка тогда будет M[H]
.

Пример конструкции:

val m = List(1, 2, 3, 4) :^: List("str1", "str2") :^: KNil

Тип переменной:

KCons[Int, java.lang.String :: HNil, List]

Обратите внимание, что мы можем смешивать совместимые конструкторы типов:

val m = Seq(1, 2, 3, 4) :^: List("str1", "str2") :^: KNil
// KCons[Int, java.lang.String :: HNil, Seq]

Те, которые несовместимы, приводят к сбою компилятора:

final case class MyArray(str: String, str1: String)
val m = Seq(1, 2, 3, 4) :^: MyArray("str1", "str2") :^: KNil
// Found: KListSuite.this.MyArray Required: M[H]

В некоторых случаях невозможно вывести типы, например, когда конструктор типа — Id

, где type Id[X] = X
:

// не скомпилируется
val p = 1 :^: true :^: KNil

Ключевое использование KList

— применение естественного преобразования к своему содержимому. Мы сохранили конструктор типа отдельно от параметров типа, что означает, что мы можем применить естественное преобразование [A] => M[A] => N[A]
к каждому элементу и сохранить базовые параметры типа. В качестве примера рассмотрим наш разнородный список списков:

val m = List(1, 2, 3, 4) :^: List("str1", "str2") :^: KNil

и естественное преобразование, которое принимает List

и вызывает для него headOption
:

val headOption: [A] => List[A] => Option[A] =
[A] => (list: List[A]) => list.headOption

Затем применяем headOption

к m
:

val heads = m transform headOption
// KCons(Some(1), KCons(Some("str1"), KNil))

Мы получаем список опций KList

, сохраняя информацию о том, что первый элемент имеет тип Option[Int]
, а второй — тип Option[String]
.

Метод transform

в KList
реализовать просто:

sealed trait KList[+M[_], HL <: HList]:
infix def transform[N[_]](f: [A] => M[A] => N[A]): KList[N, HL]
final case class KCons[H, T <: HList, +M[_]](head: M[H], tail: KList[M, T])
extends KList[M, H :: T]:
...
infix def transform[N[_]](f: [A] => M[A] => N[A]): KList[N, H :: T] =
KCons(f(head), tail transform f)
sealed class KNil extends KList[Nothing, HNil.type]:
...
infix def transform[N[_]](f: [A] => Nothing => N[A]): KList[N, HNil.type] = KNil

Мы можем добавить еще один метод, который преобразует KList

в базовый HList
. Например, мы могли бы уменьшить каждый список в нашем KList
выше до его головного элемента:

val head: [A] => List[A] => Id[A] =
[A] => (list: List[A]) => list.head
val heads = m down head
// 1 :: "str1" :: HNil

Определение метода down

выглядит так:

sealed trait KList[+M[_], HL <: HList]:
// Для преобразования KList в HList
infix def down(f: [A] => M[A] => Id[A]): HL
final case class KCons[H, T <: HList, +M[_]](head: M[H], tail: KList[M, T])
extends KList[M, H :: T]:
...
infix def down(f: [A] => M[A] => Id[A]) = HCons(f(head), tail down f)
sealed class KNil extends KList[Nothing, HNil.type]:
...
infix def down(f: [A] => Nothing => Id[A]) = HNil

В следующем разделе мы будем использовать down

и transform
, чтобы реализовать zipWith
для произвольной арности.

Часть 8c. KList ZipWith

Исходная статья

Одним из вариантов использования KList

и методов transform
и down
является реализация таких методов, как zipWith
, для кортежей произвольной длины. Начнем с того, что подпись zipWith
для пары потоков, работающих с фиксированной арностью 2
, выглядит так:

def zipWith2[A, B, C](t2: (LazyList[A], LazyList[B]))(
f: (A, B) => C
): LazyList[C] =
t2 match
case (ha #:: ta, hb #:: tb) =>
LazyList.cons(f(ha, hb), zipWith2((ta, tb))(f))
case _ => LazyList.empty

Пример использования:

val nats = LazyList.from(1)
val random = LazyList.continually(math.random)
val seq = zipWith2((nats, random)) { (n, r) => if (r > 0.3) n else -n }
seq.take(10).toList
// List(-1, -2, 3, 4, 5, -6, 7, 8, -9, 10)

Для реализации zipWith2

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

Чтобы обобщить код до произвольной арности, мы будем работать со списком потоков KList

. Поскольку мы хотим абстрагироваться от арности, то используем разнородный список. Мы используем KList
вместо HList
, потому что хотим, чтобы каждый элемент в кортеже был потоком, и нас не волнует, к какому конкретному типу потоков относятся элементы, но мы хотим сохранить эти типы. Когда мы берем элемент head
каждого потока, результирующий список является базовым типом HList
входного KList
. Например, учитывая ввод типа KList[LazyList, A :: B :: HNil]
, когда мы берем заголовок каждого потока в KList
, то получаем HList
типа A :: B :: HNil
. Это похоже на переход от (LazyList[A], LazyList[B])
к (A, B)
.

Итак, если мы в конечном итоге получим базовый тип HList

, функция, которую мы применим к входному KList
, должна быть функцией от этого типа HList
к какому-либо другому типу. В приведенном выше примере тип функции будет относиться A :: B :: HNil => T
к некоторому типу T
, который будет типом выходного потока. Таким образом, у нас есть подпись для обобщенного zipWith
:

def zipWith[HL <: HList, T](kl: KList[LazyList, HL])(f: HL => T): LazyList[T]

Чтобы реализовать эту функцию, мы снова разобьем задачу на две части. Если какой-либо поток пуст, результирующий поток также будет пуст. В противном случае мы получаем все элементы head

LazyList
-ов в виде HList
, применяем к нему функцию ввода и делаем его новым head
. Для остатка получаем все остатки потоков и выполняем рекурсию. Чтобы получить элементы head
, мы используем down
, потому что нам нужно KList[LazyList, HL] => HL
. Для остатков используем transform
, потому что нам нужно отображение KList[LazyList, HL] => KList[LazyList, HL]
. Реализация выглядит так:

def zipWith[HL <: HList, T](
kl: KList[LazyList, HL]
)(f: HL => T): LazyList[T] =
if (anyEmpty(kl))
LazyList.empty
else
LazyList.cons(f(kl down heads), zipWith(kl transform tails)(f))
@tailrec
def anyEmpty(kl: KList[LazyList, _]): Boolean =
kl match
case KCons(head, tail) => head.isEmpty || anyEmpty(tail)
case _ => false
val heads: [A] => LazyList[A] => Id[A] =
[A] => (list: LazyList[A]) => list.head
val tails: [A] => LazyList[A] => LazyList[A] =
[A] => (list: LazyList[A]) => list.tail

В zipWith

мы можем вызвать метод isEmpty
для элементов списка, но мы не получим конкретный тип, если, например, вызовем head
. "Заголовки" и "остатки" — это естественные преобразования, которые сопоставляют LazyList[T]
с его началом типа T
и остатком типа LazyList[T]
соответственно.

Исходный пример, переведенный для использования обобщенного zipWith

, выглядит так:

val nats = LazyList.from(1)
val random = LazyList.continually(math.random)
val seq = ZipWith.zipWith(nats :^: random :^: KNil) { case n :: r :: HNil =>
if (r > 0.3) n else -n
}
seq.take(10).toList
// List(1, 2, 3, 4, 5, 6, 7, 8, -9, 10)

Мы можем реализовать соответствующую функцию zip

в терминах zipWith
.

def zipped[HL <: HList](kl: KList[LazyList, HL]): LazyList[HL] =
zipWith(kl)(x => x)

Или мы могли бы реализовать zipWith

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

def foreach[HL <: HList, T](kl: KList[LazyList, HL])(f: HL => T): Unit =
zipped(kl).foreach(f)
def collect[HL <: HList, T](kl: KList[LazyList, HL])(f: HL => Option[T): LazyList[T] =
zipped(kl).collect { case hl if f(hl).isDefined => f(hl).get }
def flatMap[HL <: HList, T](kl: KList[LazyList, HL])(f: HL => LazyList[T]): LazyList[T] =
zipped(kl).flatMap(f)
def forall[HL <: HList](kl: KList[LazyList, HL])(f: HL => Boolean): Boolean =
zipped(kl).forall(f)
def exists[HL <: HList](kl: KList[LazyList, HL])(f: HL => Boolean): Boolean =
zipped(kl).exists(f)

Пример использования foreach

:

val a = LazyList(1, 2, 5, 3, 9, 10, 101)
val b = LazyList("one", "two", "three", "four")
val c = LazyList(true, false, false, true, true)
ZipWith.zipped(a :^: b :^: c :^: KNil) foreach { case n :: s :: b :: HNil =>
println(s * (if (b) 1 else n))
}
// one
// twotwo
// threethreethreethreethree
// four

Ссылки:

Использование cookies

Мы используем файлы cookie в соответствии с Политикой конфиденциальности и Политикой использования cookies.

Нажимая кнопку «Принимаю», Вы даете АО «СберТех» согласие на обработку Ваших персональных данных в целях совершенствования нашего веб-сайта и Сервиса GitVerse, а также повышения удобства их использования.

Запретить использование cookies Вы можете самостоятельно в настройках Вашего браузера.