×Закрыть

Вывод реализаций интерфейсов в Scala c библиотекой Shapeless

В статье рассмотрим пример превращения данных алгебраического типа в представлении через sealed trait family в обобщенное представление. Покажем техники работы с этим обобщенным представлением на примере структурного сравнения, операции diff. В конце статьи — работающий пример в репозитории на GitHub.

Мотивация

Наверняка многим программистам, которые пишут на статически типизированных языках, часто приходится иметь дело с введением операции сравнения (метод equals, операция == и т. д.). В большинстве языков эта операция вводится непосредственным написанием кода операции. Чаще всего это может выглядеть как-то так:

class Foo {
 private var bar: Int
 private var baz: Double
 private var qux: String

 override def equals(that: Foo): Boolean  = {
   this.bar == that.bar && this.baz == that.baz && this.qux == that.qux
 }
}

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

Еще одна проблема, с которой, возможно, многие читатели могли столкнуться при тестировании — это поиск причины, по которой два объекта не равны, и конкретных полей, которые отличаются. Написание кода, который бы по заданному объекту напрямую отыскивал и перечислял все отличающиеся поля, снова привело бы к написанию большого количества бойлерплейта и сложной инфраструктуры.

Хотелось бы иметь магический метод Compare(a,b), который бы работал для большого количества типов и в то же время был легко настраиваемым.

Решить задачу по написанию этого метода так, чтобы бойлерплейта пришлось писать по минимуму, можно несколькими способами. Во-первых, можно применить рефлексию для выведения механизма сравнения типов данных, но рефлексия славится монструозностью кода. И, что самое главное, рефлексия работает во время исполнения кода, что чревато ошибками времени исполнения, которые, в принципе, можно отловить на этапе компиляции. Во-вторых, можно применить кодогенерацию (шаблоны/макросы), которая бы генерировала весь бойлерплейт, однако, так или иначе, нужно будет усложнять процесс сборки и компиляции и выносить генерирование всего бойлерплейта в отдельный этап. Обычно это осложнено слаборазвитым тулингом для рефлексии времени компиляции и усложняющейся сборкой.

Однако в языке Scala есть решение, которое упрощает подобную кодогенерацию, убирая любую необходимость писать код «сбоку» приложения и как-либо модифицировать сборку и компиляцию проекта. Это решение, библиотека Shapeless, является набором макросов и достаточно хорошего API к ним, которая предоставляет разные абстракции для обобщенного программирования, такие как гетерогенный список, копроизведение, функции с зависимым от типа параметра типом возвращаемого значения и т. д. В частности, эта библиотека предоставляет механизм превращения ограниченных иерархий кейс-классов в гетерогенные списки, который и будет использоваться для решения задачи.

Будем решать эту задачу для семейств запечатанных трейтов, пользуясь их хорошими свойствами.

Семейства запечатанных трейтов в Scala (sealed trait family)

В Scala конструкции, состоящие из некоторого количества «интерфейсов», доступных к расширению в рамках одного файла (sealed trait), и классов, содержащих только неизменяемые данные (case class и case object), их наследующих, называются ограниченной иерархией кейс-классов. Эта конструкция довольно неплохо справляется с моделированием замкнутых ADT (Algebraic Data Type).

Пара примеров:

sealed trait Color

sealed trait PredefColor extends Color
case object Red extends PredefColor
case object Green extends PredefColor
case object Blue extends PredefColor

case class RGB(r: Byte, g: Byte, b: Byte) extends Color
case class RGBA(r: Byte, g: Byte, b: Byte, a: Byte) extends Color
case class HSV(h: Byte, s: Byte, v: Byte) extends Color

Или

case class Id(text: Id)
sealed trait WithId{ def id: Id }
sealed trait UserData{
 def login: String
 def email: String
}
sealed trait AdminPriviledges {def privileges: Set[String]}
sealed trait User
case object Unregistered extends User
case class New(id: Id) extends WithId
case class LoggedUsser(id: Id, login: String, email: String) extends WithId with UserData
case class Admin(id: Id, login: String, email: String, priviledges: Set[String]) extends WithId 
  with UserData with AdminPriviledges

В свою очередь, программы на Scala очень часто пишутся с использованием принципа отделения данных от операций над ними, и ADT достаточно хорошо подходит для описания данных в таких программах.

ADT располагает рядом хороших свойств, например, данные иммутабельные и не содержат никаких сложных процедур построения внутреннего состояния. Или же ADT замкнуто (то есть то, что унаследовано от одного sealed trait, находится внутри одного файла), что позволяет делать полный перебор по структуре ADT, будучи уверенным, что все варианты будут перебраны. Кроме этого, все поля внутри конечных кейс-классов — открытые, что вместе с предыдущим фактом делает ADT весьма удобным типом данных с простой и понятной структурой.

Имплиситы и тайпклассы в Scala

Тайпкласс, как гласит Википедия, это конструкт для ad-hoc полиморфизма. Иными словами, способ для выбора конкретной реализации полиморфной функции по типу аргумента.

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

Во-первых, существуют неявные значения, они помечаются ключевым словом implicit, например:

implicit val foo: Int =5
implicit val 

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

def functionWithImplicitParameters( regularParam: String
                                 )(implicit
                                   implicitParam1: String,
                                   implicitParam2: Int
): (String, String, Int)= (regularParam, implicitParam1, implicitParam2)

На места неявных параметров в месте вызова функции компилятор во время компиляции подставляет первые наиболее подходящие параметры. Если же параметров одного типа на место одного неявного параметра претендует больше одного, это вызывает ошибку компиляции diverging implicit expansion.

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

type T1
type T2
type T3

implicit def foo(implicit t1: T1): T2
implicit def bar(implicit t2: T2): T3

implicit val t1: T1 = ???

val res = bar

В данном случае вызов

bar 

развернется до

bar(foo(t1))

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

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

type Bar[T]
def foo[F](implicit b: Bar[F]): Unit

в

def foo[F : Bar]:Unit

При условии, что тип Bar имеет место для одного параметра.

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

Например:

sealed trait Color

sealed trait PredefColor extends Color
case object Red extends PredefColor
case object Green extends PredefColor
case object Blue extends PredefColor

case class RGB(r: Int, g: Int, b: Int) extends Color

implicit class ToRgbOps(val color: PredefColor) extends AnyVal {
 def toRgb: RGB = {
   case Red => RGB(255 byteValue, 0, 0)
   case Green => RGB(0, 255 byteValue, 0)
   case Blue => RGB(0, 0, 255 byteValue )
 }
}

И тогда мы сможем писать Red.toRgb или Green.toRgb.

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

Итак, переходим непосредственно к самим тайпклассам. Каждый тайпкласс состоит условно из 4-х компонентов. Первый — это интерфейс, заявляющий саму функциональность тайпкласса.

Например:

trait Show[A] {
 def show(a: A): String
}

Второй компонент — это companion object этого трейта, который даст возможность использовать определенный синтаксис.

object Show {
 def apply[A](a: A)(implicit show: Show[A]): String = show.show(a)
}

А сам синтаксис использования будет выглядеть так:

Show[A](a)

Третий компонент — это набор реализаций: implicit val showString: Show[String] = {s => s} /* синтаксический сахар для анонимных классов c одним методом был создан, потому что писать new Foo {override def baz} каждый раз слишком громоздко*/

implicit val showString: Show[String] = {s: String => s} /* синтаксический сахар для анонимных классов c одним методом, был создан, потому что писать new Foo {override def baz} каждый раз слишком громоздко*/

implicit val showInt: Show[Int] = {i: Int => i.toString}
implicit def showList[T : Show]: Show[List[T]] = {list: List[T] =>
 list.map{Show[T].apply _}.mkString("List(", ",", ")")
}

Четвертый, не обязательный, но крайне желательный компонент — это «синтаксис» тайпкласса, который позволит вызывать этот метод через точку:

implicit class ShowSyntax[T](val t: T) extends AnyVal {
 def show(implicit instance: Show[T]): String = instance.show(t)
}

А вызов будет выглядеть вот так:

println(List(1,2,3,4,5,6).show)

Деконструкция sealed trait family

Теперь мы попробуем построить sealed trait family из набора «примитивных» типов. Для этого нам потребуются следующие компоненты: набор идентификаторов Id, набор примитивных типов PT и несколько операций. Строить будем некоторое множество типов T. Во-первых, любой примитивный тип является и типом Т. Нам понадобится операция связывания идентификатора с типом, будем обозначать ее символом @. То есть, если id — идентификатор и t — тип, то lt := t @ id — тип с идентификатором. Далее, введем операцию конструирования на типах с идентификаторами: если t1, …, tn — типы из Т и id1, …, idn — идентификаторы, то t := (t1 @ id1, t2 @ id2, …, tn @ idn) — тип из Т. Далее, вводим операцию «или» на типах: если t1, …, tn — типы из Т, то t := t1 | t2 | … | tn — тип из Т. Такая модель упрощенно показывает структуру ADT.

В нашем случае примитивными типами выступают, собственно, встроенные типы данных из разряда Int, Byte, Long, String, Double, Boolean и, кроме этого, различные типы, которые не являются частью ADT, такие как, например, java.time.Instant.

Операция конструирования моделирует введение нового типа при помощи кейс-классов или кейс-обджектов, например, из типов Int, String, String, идентификаторов foo, bar, baz мы можем построить новый тип Qux case class Qux(foo: Int, bar: String, baz: String), который в нашей модели будет представлен как Qux := (Int @ foo, String @ bar, String @ baz).

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

Операция «или» моделирует sealed trait. Ограниченность sealed trait рамками одного файла позволяет гарантировать, что перечень типов, которые наследуются от данного sealed trait, полон и известен на этапе компиляции.

sealed trait PredefColor
case object Red extends PredefColor
case object Green extends PredefColor
case object Blue extends PredefColor

То есть в этом случае мы можем смоделировать PredefColor := Red|Green|Blue.

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

Остается вопрос о параметрических типах вроде List[T] и т. д., но пока на этом останавливаться и вводить дополнительный формализм не будем: большинство вопросов, связанных с высшими каиндами, уже решено в механизме поиска имплиситов в компиляторе Scala.

На нашей модели вполне можно строить алгоритм структурного сравнения. Итак, нам нужно сравнить две структуры одинакового типа, но потенциально разного значения, и вывести список различных полей. Различные сложности сравнения неупорядоченных и упорядоченных коллекций, с которыми мы можем столкнуться, пока оставим за кадром и будем выводить наиболее простое решение.

Допустим, у нас есть некоторый набор операций сравнения для примитивных типов, тогда нам остается определить операцию сравнения для операции конструирования и для операции «или».

Для операции конструирования мы будем определять сравнение как объединение различия для всех элементов.

Для операции «или», с учетом объектов ob1, ob2,...,obn типов t1|...|tn, понятно, что настоящие типы этих объектов будут t_i и t_j для некоторых i,j из 1,...,n. Тогда если i == j, мы возвращаем результат сравнения внутренностей объектов, а если i != j, возвращаем несовпадение действительных типов.

Инструментарий

Нам понадобятся абстракции для представления операций @, (_,...,_) и “|”. К счастью, библиотека Shapeless предоставляет таковые.

Для операции @ существует отдельный тип FieldType[Identifier, T], который представляет абстракцию для поля класса, названного некоторым именем. О его использовании — ниже.

Для моделирования операции конструирования Shapeless представляет гетерогенный список HList. Отличие гетерогенного списка от обычного состоит в том, что этот список хранит информацию о типе каждого элемента в типе самого списка.

Дело в том, что сам тип HList — это надтип для очень широкого семейства типов, но конструктора у конкретных типов всего два: HNil — пустой список и ::[+Head, +Tail <: HList]. Благодаря синтаксическому сахару для типов с двумя параметрами конструкции вроде ::[String, ::[Int, HNil]] выглядят как String :: Int :: HNil.

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

Нам же пригодится только возможность рекурсивно проходить по элементам этого списка.

Далее, операцию «или» представляет тип Coproduct. Он подобен HList в том, что имеет структуру, похожую на цепь, но на этот раз у него есть несколько конструкторов. Общий тип Coproduct населен типами T1 :+: T2 :+: … :+: TN :+: CNil, для N= 1,2,3,.... Каждый тип для фиксированного N= N0 состоит из элементов Inl(t1: T1), Inr(Inl(t2: T2), … , Inr(Inr(,, Inl(tn0: TN0))). Где в H :+: T при T <: Coproduct Inr обозначает, что конкретный объект типа H, а Inl обозначает, что тип конкретного объекта находится в T. Тип CNil существует для терминирования последовательности CNil, и ни для чего более.

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

Теперь нам необходимо связующее звено, которое выведет тип представления конкретного объекта через описанные выше три типа данных и предоставит механизм для превращения из конкретного объекта в обобщенное представление. В Shapeless существует тайпкласс LabelledGeneric, экземпляры которого генерируются неявным макросом (как и большинство экземпляров тайпклассов в этой библиотеке, так что открытие портала в измерение неявных макросов и призыв реализаций — это вполне обыкновенный способ взаимодействия с ней) на этапе компиляции. Чтобы «призвать» LabelledGeneric для типа T в скоупе, в котором объявлен, достаточно написать:

import shapeless._
val v = LabelledGeneric[T]

Для того чтобы призвать экземпляр тайпкласса для параметра типа T, необходимо потребовать implicit параметр lgen: LabelledGeneric.Aux[T, Repr], и ввести дополнительный параметр, который будет нести тип представления Repr.

Из чего будет состоять тип Repr? Этот тип будет действовать именно по описанной выше модели. Для кейс-классов он будет выдавать HList из FieldType[FieldName, TypeName], тегированный специальным образом, для sealed trait — coproduct.

Следует отметить, что у IDE возникают определенные сложности с определением типов репрезентации labelled generic. Например, для класса

case class Foo(s: String, i: Int, b: Boolean)

...мы получим тип LabelledGeneric[Foo], который, естественно, соответствовать настоящему не будет, но даст нам некоторое представление о том, как это выглядит в реальности.

LabelledGeneric.Aux[
 Foo,
 FieldType[String with KeyTag[Symbol with Tagged[{type s}], String], String] ::
 FieldType[Int with KeyTag[Symbol with Tagged[{type i}], Int], Int] ::
 FieldType[Boolean with KeyTag[Symbol with Tagged[{type b}], Boolean], Boolean] ::
 HNil
]

Здесь страшные типы вроде String with KeyTag[Symbol with Tagged[{type s}], String] — это способ библиотеки Shapeless генерировать уникальные теги на уровне типов для полей классов.

Для иерархии

sealed trait All
case class Foo(s: String, i: Int, b: Boolean) extends All
case class Bar(l: Long, f: Foo) extends All
case class Baz(foos: List[Foo], bars: List[Bar]) extends All

Мы получим выражение:

LabelledGeneric.Aux[
   All,
   Bar with KeyTag[Symbol with Tagged[Symbol with Tagged[{type Bar}]], Bar] :+:
   Baz with KeyTag[Symbol with Tagged[Symbol with Tagged[{type Baz}]], Baz] :+:
   Foo with KeyTag[Symbol with Tagged[Symbol with Tagged[{type Foo}]], Foo] :+:
   CNil
 ]

И снова, приписки with KeyTag[_, _] относятся к техническому аспекту shapeless выдавать уникальные типы на каждый класс. (Подробнее — Singleton types)

Естественно, работать с этими типами вручную не нужно — с ними нужно работать при помощи рекурсии, и это мы рассмотрим чуть ниже.

Решение

Итак, объявим интерфейс и несколько вспомогательных классов. ComparisonResult для результата сравнения в виде Success и Failure. FailEntry[T] для представления различий. Path для определения местонахождения сравниваемого элемента.

package object genericComparators {

 sealed trait ComparisonResult {
   def append(fe: FailEntry[_]): ComparisonResult

   def &&(that: ComparisonResult): ComparisonResult

   def fails: Chain[FailEntry[_]]

 }

 object ComparisonResult {

   case object Success extends ComparisonResult {
     override def append(fe: FailEntry[_]): ComparisonResult = Failure(Chain(fe))

     override def &&(that: ComparisonResult): ComparisonResult = that

     override def fails: Chain[FailEntry[_]] = Chain.empty[FailEntry[_]]

   }

   case class Failure(fails: Chain[FailEntry[_]]) extends ComparisonResult {
     override def append(fe: FailEntry[_]): ComparisonResult = Failure(fails :+ fe)

     override def &&(that: ComparisonResult): ComparisonResult = Failure(this.fails ++ that.fails)

   }

 }

 case class FailEntry[T](path: AdtPath, left: T, right: T)

 object AdtPath {
   val root = AdtPath(Chain.empty[PathElement])
 }

 sealed trait PathElement

 case object Root extends PathElement

 case class DownGeneric(generic: String) extends PathElement
 case class DownField(field: Symbol) extends PathElement
 case class DownCoproductElement(coproductType: Symbol) extends PathElement
 case class Primitive(field: String) extends PathElement
 case class DownIterable(index: Long) extends PathElement
 case class DownManual(tag: String) extends PathElement

 case class AdtPath(steps: Chain[PathElement], last: PathElement = Root) {
   def downHlist(fieldName: Symbol): AdtPath =
     last match {
       case DownField(_) => AdtPath(steps, DownField(fieldName))
       case Primitive(_) => throw new RuntimeException(s"should not never happen")
       case _ => AdtPath(steps :+ last, DownField(fieldName))
     }

   def downCoproduct(element: Symbol): AdtPath =
     last match {
       case DownCoproductElement(_) => AdtPath(steps, DownCoproductElement(element))
       case Primitive(_) => throw new RuntimeException(s"should not never happen")
       case _ => AdtPath(steps :+ last, DownCoproductElement(element))
     }

   def downGeneric(className: String): AdtPath =
     last match {
       case Primitive(_) => throw new RuntimeException(s"should not never happen")
       case _ => AdtPath(steps :+ last, DownGeneric(className))
     }

   def downIterable(index: Long): AdtPath = last match {
     case DownIterable(_) => AdtPath(steps, DownIterable(index))
     case Primitive(_) =>throw new RuntimeException(s"should not never happen")
     case _ => AdtPath(steps :+ last, DownIterable(index))
   }

   def downManual(manual: String): AdtPath = AdtPath( steps :+ last, DownManual(manual))

   def primitive(primitiveTag: String): AdtPath = AdtPath( steps :+ last, Primitive(primitiveTag))
 }
}

Далее, определяем интерфейс нашего тайпкласса и несколько простых реализаций:

object GenericComparer {
 def compare[T](first: T, second: T)(implicit
                                     compare: GenericComparer[T]
 ): ComparisonResult =
   compare.apply(first, second)(AdtPath.root, ComparisonResult.Success)

 def instance[U](f: (U, U) => Boolean)(tag: String = ""): GenericComparer[U] = new GenericComparer[U] {
   override def apply(t1: U, t2: U)(implicit path: AdtPath, result: ComparisonResult): ComparisonResult =
     if (f(t1, t2)) result
     else result.append(FailEntry(path, t1, t2))
 }
}

trait GenericComparer[T] {
 def apply(t1: T, t2: T)(implicit path: AdtPath, result: ComparisonResult): ComparisonResult
}

Неявный параметр path нужен для возможности «записывать» пройденный путь по структуре класса при рекурсивном применении этой функции. Неявный параметр result является аккумулятором в рекурсии.

В компанион обджекте создан метод def compare[T](first: T, second: T)(implicit compare: GenericComparer[T]): ComparisonResult, который предоставляет интерфейс для использования тайпкласса как GenericComparer.compare(a,b).

Там же функция для создания реализации из функции сравнения instance.

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

implicit val scompare: GenericComparer[String] = GenericComparer.instance[String] { _ == _ } {"string"}
implicit val icompare: GenericComparer[Int] = GenericComparer.instance[Int] { _ == _ } {"int"}
implicit val lcompare: GenericComparer[Long] = GenericComparer.instance[Long] { _ == _ } {"long"}
implicit val bcompare: GenericComparer[Byte] = GenericComparer.instance[Byte] { _ == _ } {"byte"}
implicit val boolcompare: GenericComparer[Boolean] = GenericComparer.instance[Boolean] { _ == _ } {"bool"}
implicit val ccompare: GenericComparer[Char] = GenericComparer.instance[Char] { _ == _ } {"char"}
implicit val shortcompare: GenericComparer[Short] = GenericComparer.instance[Short] { _ == _ } {"short"}
implicit val bicompare: GenericComparer[BigInt] = GenericComparer.instance[BigInt] { _ == _ } {"bigInt"}
implicit val dcompare: GenericComparer[Double] = GenericComparer.instance[Double] { _ == _ } {"double"}

Далее, приступим к созданию операции для композитного объекта, который представим в виде LabeledGeneric.

//decompose sealed trait family
implicit def lgenCompare[T, Repr](
 implicit
 ctag: ClassTag[T],
 lgen: LabelledGeneric.Aux[T, Repr],
 reprCompare: Lazy[GenericComparer[Repr]]): GenericComparer[T] = new GenericComparer[T] {
 override def apply(t1: T, t2: T)(implicit path: AdtPath, result: ComparisonResult): ComparisonResult = {
   reprCompare.value.apply(
     lgen.to(t1),
     lgen.to(t2))(
     path.downGeneric(ctag.runtimeClass.getSimpleName),
     result
   )
 }
}

Эта реализация функции тайпкласса пытается «призвать» LabelledGeneric с каким-либо типом представления и вывести реализацию для обобщенного представления. Но сама по себе эта реализация бесполезна без реализаций для примитивов, случая с HList и Coproduct. Обратите внимание на то, что операция сравнения для обобщенного представления Repr обернута в Lazy, для того чтобы избежать ошибки diverging implicit expansion.

Итак, сначала случай HList.

Терминальная точка для рекурсии:

implicit val hnilCompare: GenericComparer[HNil] =
 GenericComparer.instance[HNil] { (_, _) => true }{"hnil"}

И сама рекурсия, метод который выводит операцию сравнения для непустого списка Head :: Tail:

implicit def hconsCompareKeyed[Key <: Symbol, Head, Tail <: HList](
 implicit key: Witness.Aux[Key],
 compareHeads: GenericComparer[Head],
 compareTails: Lazy[GenericComparer[Tail]]
): GenericComparer[FieldType[Key, Head] :: Tail] =
 new GenericComparer[FieldType[Key, Head] :: Tail] {
   override def apply(
     t1: FieldType[Key, Head] :: Tail,
     t2: FieldType[Key, Head] :: Tail)(
     implicit path: AdtPath, result: ComparisonResult
   ): ComparisonResult = {
     val newPath = path.downHlist(key.value)

     compareHeads.apply(t1.head, t2.head)(newPath, result) &&
       compareTails.value.apply(t1.tail, t2.tail)(newPath, result)
   }
 }

Откуда такой набор типов и такая сигнатура? Во-первых, нам необходимо имя поля, его достаем при помощи типа Key, который является символом. Для «вызова» значения имени поля используем неявный параметр key: Witness.Aux[Key], который и вызовет то значение, которое кодируют страшные типы из главы выше. Это и есть тот обещанный способ не работать напрямую с типом тега, который тегирует конкретное поле в классе — введя его как параметр функции, компилятор попытается его вывести автоматически.

Далее, Head — это тип тегируемого при помощи Key поля в классе, нам необходимо иметь для него операцию сравнения, поэтому мы заявляем это как еще один неявный параметр — compareHeads: GenericComparer[Head].

И наконец, чтобы сделать рекурсивный вызов, мы вводим параметр типа хвоста списка Tail, который снова должен быть гетерогенным списком, и просим вывести для хвоста реализацию при помощи заявления еще одного неявного параметра: compareTails: Lazy[GenericComparer[Tail]].

Почему это будет рекурсивным вызовом? Потому что под тип GenericComparer[Tail] подпадает эта же реализация, или же терминальная точка рекурсии hnilCompare. При этом мы избавились от необходимости рассматривать все типы списка сразу, а рассматриваем их только по одному за вызов, что позволяет обрабатывать списки произвольной длины.

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

Теперь рассмотрим случай Coproduct. Терминирование рекурсии будем производить при помощи:

implicit val cnilCompare: GenericComparer[CNil] =
 GenericComparer.instance[CNil] { (a, b) => a.impossible
}{"neverhappen"}

Этот метод никогда не будет вызван, но необходим, чтобы остановить поиск неявных параметров. Теперь непосредственно реализация для непустого произведения, подобная той, что мы привели для HList.

implicit def cconsCompareKeyed[Key <: Symbol, Head, Tail <: Coproduct](
 implicit key: Witness.Aux[Key],
 compareHeads: GenericComparer[Head],
 compareTails: Lazy[GenericComparer[Tail]]
): GenericComparer[FieldType[Key, Head] :+: Tail] =
 new GenericComparer[FieldType[Key, Head] :+: Tail] {
   override def apply(
     t1: FieldType[Key, Head] :+: Tail,
     t2: FieldType[Key, Head] :+: Tail)(
     implicit path: AdtPath, result: ComparisonResult): ComparisonResult = {
     val newPath = path.downCoproduct(key.value)
     (t1, t2) match {
       case (Inl(a), Inl(b)) =>
         compareHeads.apply(a, b)(newPath, result)
       case (Inl(_), Inr(_)) | (Inr(_), Inl(_)) =>
         result.append(FailEntry(newPath, Coproduct.unsafeGet(t1), Coproduct.unsafeGet(t2)))
       case (Inr(tail1), Inr(tail2)) =>
         compareTails.value.apply(tail1, tail2)
     }
   }
 }

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

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

def compareIterables[T: GenericComparer]: GenericComparer[Iterable[T]] =
 new GenericComparer[Iterable[T]] {
   override def apply(t1: Iterable[T], t2: Iterable[T])(implicit path: AdtPath, result: ComparisonResult)
   : ComparisonResult = {
     if (t1.size == t2.size) {
       (t1 zip t2).foldLeft((result, 0)) { case ((res, i), (el1, el2)) =>
         (implicitly[GenericComparer[T]].apply(el1, el2)(path.downIterable(i), res), i + 1)
       }._1
     }
     else result.append(FailEntry(path.downIterable(-1), t1, t2))
   }
 }

Объединение

Теперь необходимо соединить все в единую структуру, пригодную к использованию. Нам бы хотелось при всем том, что умеет эта библиотека, уметь заменять генерацию операции своей реализацией, иначе бы от такой библиотеки пользы было мало. Достичь этого можно при помощи механизма затенения неявных значений (implicit shadowing). Для этого нужно положить реализацию для Labelled generic, HList и Coproduct в трейт GenericComparatorsLowestPriority. Затем от него наследовать трейт AllComparators со всеми реализациями для примитивов. Далее — в любой точке применения наследовать AllComparators своим классом/обджектом/трейтом.

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

Готовый результат можно посмотреть в репозитории на GitHub.

Наиболее простой способ запустить этот код локально — установить intellij IDEA Community edition и Scala plugin к ней, далее просто открыть проект и импортировать — плагин и IDE сделают все сами.

Преимущества и недостатки

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

Основным недостатком текущей реализации является то, что выяснение причины, по которой компилятор не может вывести операцию сравнения для чего-нибудь, может занимать определенное время, но опция компилятора «-Xlog-implicits» станет хорошим подспорьем — пройдясь по сообщениям, можно понять, чего именно не хватает. Единственное утешение — вы всегда узнаете об этом до запуска программы.

Второй недостаток — не самая хорошая работа со множествами и коллекциями, но это как раз дело поправимое.

Послесловие

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

LinkedIn

11 комментариев

Подписаться на комментарииОтписаться от комментариев Комментарии могут оставлять только пользователи с подтвержденными аккаунтами.

Неужели еще остались люди, которые еще не перешли со Scala на Go после эпичного фейла dou.ua/forums/topic/16012 ?

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

Описанное в статье это не «эпичный фейл», это скорее последствия «я уже всё выучил и учить больше ничего не буду, а технология которая заставляет меня что-то учить — плохая». Конечно, если писать на скале как на джаве и/или на го, ничего хорошего не получится.

Но если почитать как надо(books.underscore.io/...​-cats/scala-with-cats.pdf, typelevel.org/...​-effect/datatypes/io.html или если приспичило doc.akka.io/...​/current/typed/index.html), и ещё почитать откуда у всего этого растут ноги (github.com/...​hmemcpy/milewski-ctfp-pdf), то язык вмиг станет простым и понятным, и заиграет новыми фичами, например, которая описана в статье.

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

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

Хотелось бы увидеть несколько примеров про «язык-грабли».

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

Признаюсь, я ниасилил статью из-за ее размеров и объемов матана, как и большинство посетителей. Сразу видно — очень простой и понятный способ решения задачи, которая имеет близкое к нулю практическое значение :)

которая имеет близкое к нулю практическое значение

 ну, как бы практическое значение тут не нулевое — (де)сериализация в любой формат, трансформация классов без бойлерплейта, а-ля ORM, ETLное дополнение данных,у подобных вещей очень много применений.

Є простий і зрозумілий спосіб вирішення таких задач github.com/...​d/src/main/scala/eq.scala

Спасибо за замечание, но конкретно этому способу решения — достаточно много лет, и во время его создания магнолия не была на слуху.

Це було зауваження не вам, а більше панові Aliaksandr )
На shapeless з цим корисно розібратись хоча би для того, щоб розібратись із implicit’ами.
В підсумку як shapeless, так і magnolia зникнуть з релізом scala 3

Те, що Shapeless зникне з появою Scala 3 — занадто сильне припущення :)
Shapeless — це не тільки deriving тайпкласів, це ще й купа написаних тайпкласів для роботи з HList’ами, Poly тощо (тобто не тільки для дерайвінга тайпкласів для типів даних, але й трансформації типів даних). Чому вони мають зникнути? Можливо, їх частково перенесуть в стандартну бібліотеку, але повністю — малоймовірно. Наразі бранч Shapeless для Скали 3 активно розробляється
github.com/...​hapeless/tree/shapeless-3
github.com/...​-build/community-projects

Ну це так, припущення) Принаймні хотілося б, щоб це все потрапило в стандартну бібліотеку і зникло

У Магнолії є обмеження порівняно з Shapeless.

Если же параметров одного типа на место одного неявного параметра претендует больше одного, это вызывает ошибку компиляции diverging implicit expansion.

«diverging implicit expansion» — это другая ошибка. Когда подходит больше одного имплисита, то это ошибка «ambiguous implicit values».

Подписаться на комментарии