Программирование на уровне типов в 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)