[Перевод] Сортировка в Scala — пример на кошках08.04.2020 00:18

z2-ktbdcwvurhrsrxafuetdvac4.jpeg?v=1

Привет, Хабр! Выношу на ваш суд русскоязычный перевод моей статьи на Medium: Sorting in Scala — a cat shop example. Статья рассчитана на читателей, знающих синтаксис языка Scala и осведомлённых о базовых инструментах стандартной библиотеки.

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


Первоначальная постановка задачи

Представим, что в нашем распоряжении находится магазин кошек (поскольку кошки — самое популярное животное в Scala-экосистеме). Из-за особенностей получения информации о кошках, доступных к продаже, в некоторых случаях информация поступает не из базы данных и должна быть отсортирована вручную перед отправкой HTTP ответа клиенту или обработкой её каким-либо другим образом. Основным объектом предметной области является, конечно, Cat, который в начале обладает только тремя полями примитивных типов. Задачей является разработать API для сортировки коллекций кошек, удовлетворяющий следующим требованиям:


  • Порядок сортировки может быть определён по каждому из полей
  • Порядок сортировки может быть не определён для любого из полей
  • Сортировка должна быть стабильной для полей с неопределённым порядком сортировки
  • Каждое поле имеет предопределённый приоритет при сортировке (т.е. сортировка по полю age будет всегда приоритетнее сортировки по полю name)


Первая итерация

case class Cat(age: Int,
               name: String,
               available: Boolean)

Поскольку постановка задачи относительно проста, а информация о других частях проекта отсутствует, первоначальное решение лучше сделать простым. К счастью, scala.Ordering уже определяет удобный метод Tuple3, с помощью которого можно создавать экземпляры Ordering для кортежей размерности 3, к которым легко приводится любой объект класса Cat.

Тем не менее, взаимодействовать с Tuple3 напрямую несколько затруднительно, поскольку данный метод требует явного предоставления сортировки при необходимости изменения порядка. Более того, отсутствует возможность удобного исключения полей из сортировки — необходимо либо переключаться между методами Tuple1, Tuple2, Tuple3, либо явно предоставлять для игнорируемых полей тождественный объект Ordering, не меняющий исходного порядка элементов. Всего нужно будет рассмотреть 9 случаев (3 возможных порядка сортировки и 3 поля), поскольку приоритет сортировки предопределён.

Для того, чтобы упростить API и приблизить его к предметной области, введём «порядок сортировки» как сущность. Согласно требованиям, существует всего 3 порядка: по возрастанию (естественный), по убыванию (обратный естественному) и «отсутствующий» (сохраняет исходный порядок). Это естественным образом отображается в следующий алгебраический тип данных (ADT): 

sealed trait SortOrder

object SortOrder {

  case object Keep extends SortOrder

  case object Asc extends SortOrder

  case object Desc extends SortOrder
}

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

import common.OrderingUtil
import iteration1.SortOrder.{Asc, Desc, Keep}

object syntax {

  implicit class OrderSyntax(val order: SortOrder) extends AnyVal {

    def apply[A](ordering: Ordering[A]): Ordering[A] =
      order match {
        case Keep => OrderingUtil.identity
        case Asc => ordering
        case Desc => ordering.reverse
      }
  }
}

OrderingUtil.identity — вспомогательная функция, предоставляющая тождественный порядок сортировки для любого типа A, сохраняющий порядок элементов. Она определена как: Ordering.by(_ => 0).

Теперь, когда основные элементы определены, остаётся только создать непосредственно Ordering[Cat]. С этой целью создан модуль CatOrdering: 

import iteration1.syntax._

object CatOrdering {

  def of(idOrder: SortOrder,
         nameOrder: SortOrder,
         availableOrder: SortOrder): Ordering[Cat] =
    Ordering
      .Tuple3(idOrder(Ordering.Int), nameOrder(Ordering.String), availableOrder(Ordering.Boolean))
      .on[Cat](cat => (cat.age, cat.name, cat.available))
}

Теперь любой необходимый порядок сортировки (Ordering[Cat]) может быть создан при помощи функции CatOrdering.of: 

CatOrdering.of(SortOrder.Asc, SortOrder.Keep, SortOrder.Desc)

Поскольку число тестовых случаев относительно велико, для проверки корректности реализации можно использовать комбинацию ScalaTest и ScalaCheck с целью написания property-based тестов. Это позволит автоматически генерировать коллекции, для которых можно проверить корректность заданного порядка сортировки. Набор тестов для первой итерации доступен по ссылке.


Вторая итерация

С момента первой итерации магазин вырос и в классе Cat появилось новое опциональное поле.

case class Cat(age: Int,
               name: String,
               available: Boolean,
               owner: Option[String])

Основное отличие от примитивных типов в том, что появился особый случай — пустое значение (не имеет ничего общего с null!), которое, в зависимости от предпочтений, может считаться либо максимальным значением, либо минимальным. Это означает, что существует 4 возможных порядка сортировки по этому полю:


  1. По возрастанию, пустые значения в начале (естественный)
  2. По возрастанию, пустые значения в конце
  3. По убыванию, пустые значения в начале
  4. По убыванию, пустые значения в конце (обратный естественному)

В то время как два из них (1 и 4) можно получить при помощи scala.Ordering.Option, оставшиеся 2 должны быть заданы явно. Поскольку SortOrder теперь ответственен за работу с пустыми значениями, он явно определяет их приоритет: 

sealed trait SortOrder

object SortOrder {

  case class Asc(emptyFirst: Boolean) extends SortOrder

  case class Desc(emptyFirst: Boolean) extends SortOrder

  case object Keep extends SortOrder

  object Asc {
    def emptyFirst: Asc = Asc(emptyFirst = true)

    def emptyLast: Asc = Asc(emptyFirst = false)
  }

  object Desc {
    def emptyFirst: Desc = Desc(emptyFirst = true)

    def emptyLast: Desc = Desc(emptyFirst = false)
  }
}

Соответствующие изменения произведены и для синтаксического расширения SortOrder. Метод optional предоставляет Ordering[Option[A]] для любого A, вместе с тем применяя правило для пустых значений, определённое в SortOrder. Стоит отметить, что, хотя Ordering[Option[A]] можно также создать и с помощью метода apply, для этого необходимо явно предоставить Ordering[Option[A]], что исключает возможность сделать это случайно. Данное небольшое противоречие можно устранить предоставлением доказательства, что A в apply не является наследником Option. Для изучения инструментов возможной реализации можно ознакомиться с документацией класса <:<, и данным вопросом на StackOverflow (в Dotty Not доступен как часть стандартной библиотеки).

import common.OrderingUtil
import iteration2.sort_order.SortOrder._

object syntax {

  private object OptionOrdering {

    def apply[A](rootOrdering: Ordering[A],
                 emptyFirst: Boolean): Ordering[Option[A]] =
      if (emptyFirst)
        OptionOrdering.emptyFirst(rootOrdering)
      else
        OptionOrdering.emptyLast(rootOrdering)

    def emptyFirst[A](rootOrdering: Ordering[A]): Ordering[Option[A]] =
      (x: Option[A], y: Option[A]) => (x, y) match {
        case (None, None) => 0
        case (None, _) => -1
        case (_, None) => 1
        case (Some(a), Some(b)) => rootOrdering.compare(a, b)
      }

    def emptyLast[A](rootOrdering: Ordering[A]): Ordering[Option[A]] =
      (x: Option[A], y: Option[A]) => (x, y) match {
        case (None, None) => 0
        case (None, _) => 1
        case (_, None) => -1
        case (Some(a), Some(b)) => rootOrdering.compare(a, b)
      }
  }

  implicit class OrderSyntax(val order: SortOrder) extends AnyVal {

    def optional[A](ordering: Ordering[A]): Ordering[Option[A]] =
      order match {
        case Keep => OrderingUtil.identity
        case Asc(emptyFirst) => OptionOrdering(ordering, emptyFirst)
        case Desc(emptyFirst) => OptionOrdering(ordering.reverse, emptyFirst)
      }

    def apply[A](ordering: Ordering[A]): Ordering[A] =
      order match {
        case Keep => OrderingUtil.identity
        case Asc(_) => ordering
        case Desc(_) => ordering.reverse
      }
  }
}
import iteration2.sort_order.SortOrder
import iteration2.sort_order.syntax._

import scala.Ordering.{Boolean => BooleanO, Int => IntO, String => StringO}

object CatOrdering {

  def toOrdering(idOrder: SortOrder,
                 nameOrder: SortOrder,
                 availableOrder: SortOrder,
                 ownerOrder: SortOrder): Ordering[Cat] = {
    Ordering
      .Tuple4(idOrder(IntO), nameOrder(StringO), availableOrder(BooleanO), ownerOrder.optional(StringO))
      .on[Cat](cat => (cat.age, cat.name, cat.available, cat.owner))
  }
}

Пример создания Ordering[Cat] приведён ниже. Необходимо заметить, что для обязательных полей всё равно необходимо предоставлять правило сортировки пустых значений. 

CatOrdering.toOrdering(
  SortOrder.Asc.emptyFirst, 
  SortOrder.Asc.emptyFirst, 
  SortOrder.Asc.emptyFirst,
  SortOrder.Asc.emptyFirst
)

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


Третья итерация

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


  1. Приоритет полей при сортировке заранее определён.
  2. Если для каких-либо полей порядок сортировки не задан, его всё ещё необходимо предоставить с помощью SortOrder.Keep.
  3. Количество полей класса Cat ограничено 9. После этого не существует метода Tuple10 и реализация должна существенно поменяться.

Новые бизнес-требования в этот раз относятся к последнему пункту. Теперь магазин предоставляет так много информации о кошках, что у класса Cat в наличии уже 10 полей. С учётом столь большого их числа, очевидно, что только лишь некоторые из них будут использоваться при сортировке. Более того, стало сложнее предопределить осмысленный приоритет полей, а явное определение SortOrder для каждого из них сделает код слишком многословным. В этот раз изменения будут более значительными.

Основная идея заключается в том, чтобы не только предоставить порядок сортировки определённых полей, но и сами поля. Набор полей и связанных с ними порядков сортировки затем трансформируется в порядок сортировки для Cat. Упорядоченная коллекция таких пар естественным образом задаёт необходимый приоритет сортировки (ограничение №1) и требуемые для сортировки поля (ограничение №2), а добавление в класс нового поля потребует лишь незначительных изменений и не повлияет на основную реализацию (ограничение №3). Реализация этой идеи приведена ниже (SortOrder и его синтаксическое расширение не приводятся ввиду отсутствия существенных изменений): 

import java.time.LocalDate

case class Cat(age: Int,
               name: String,
               available: Boolean,
               owner: Option[String],
               breed: String,
               furColor: String,
               eyeColor: String,
               registrationId: String,
               lastHealthCheck: Option[LocalDate],
               urgentSell: Boolean)
import java.time.LocalDate

import iteration3.sort_order.SortOrder
import iteration3.sort_order.syntax._

import scala.Ordering._

sealed trait CatField {
  def toOrdering(sortOrder: SortOrder): Ordering[Cat]
}

object CatField {

  case object Age extends CatField {
    override def toOrdering(sortOrder: SortOrder): Ordering[Cat] =
      sortOrder(Ordering.Int).on(_.age)
  }

  case object Name extends CatField {
    override def toOrdering(sortOrder: SortOrder): Ordering[Cat] =
      sortOrder(Ordering.String).on(_.name)
  }

  case object Available extends CatField {
    override def toOrdering(sortOrder: SortOrder): Ordering[Cat] =
      sortOrder(Ordering.Boolean).on(_.available)
  }

  case object Owner extends CatField {
    override def toOrdering(sortOrder: SortOrder): Ordering[Cat] =
      sortOrder.optional(Ordering.String).on(_.owner)
  }

  case object Breed extends CatField {
    override def toOrdering(sortOrder: SortOrder): Ordering[Cat] =
      sortOrder(Ordering.String).on(_.breed)
  }

  case object FurColor extends CatField {
    override def toOrdering(sortOrder: SortOrder): Ordering[Cat] =
      sortOrder(Ordering.String).on(_.furColor)
  }

  case object EyeColor extends CatField {
    override def toOrdering(sortOrder: SortOrder): Ordering[Cat] =
      sortOrder(Ordering.String).on(_.eyeColor)
  }

  case object RegistrationId extends CatField {
    override def toOrdering(sortOrder: SortOrder): Ordering[Cat] =
      sortOrder(Ordering.String).on(_.registrationId)
  }

  case object LastHealthCheck extends CatField {
    override def toOrdering(sortOrder: SortOrder): Ordering[Cat] =
      sortOrder.optional(Ordering.by[LocalDate, Long](_.toEpochDay)).on(_.lastHealthCheck)
  }

  case object UrgentSell extends CatField {
    override def toOrdering(sortOrder: SortOrder): Ordering[Cat] =
      sortOrder(Ordering.Boolean).on(_.urgentSell)
  }
}
import common.OrderingUtil
import iteration3.sort_order.SortOrder

object CatOrdering {

  def byFields(fields: Seq[(CatField, SortOrder)]): Ordering[Cat] =
    if (fields.isEmpty) OrderingUtil.identity[Cat]
    else {
      val (head, headOrder) = fields.head
      val (res, _) = fields.tail.foldLeft[(Ordering[Cat], Set[CatField])]((head.toOrdering(headOrder), Set())) {
        case (acc@(_, presentFields), (field, _)) if presentFields.contains(field) =>
          acc

        case ((ordering, presentFields), (field, order)) =>
          (ordering.orElse(field.toOrdering(order)), presentFields + field)
      }
      res
    }
}

Реализация в основном полагается на метод orElse, применяющий другой порядок сортировки, если согласно уже имеющемуся порядку сравниваемые объекты эквивалентны. Он во многом идентичен методу thenComparing класса Comparator в языке Java. Данный метод доступен также и для Ordering, поскольку он является расширением Comparator в целях совместимости. Тем не менее, orElse гораздо лучше работает с классами языка Scala, а также обладает удобной альтернативой orElseBy.

Необходимо отметить, что, поскольку функция byFields применяется к произвольной упорядоченной коллекции без ограничений на уникальность её элементов, повторные вхождения обрабатываются вручную. Также, чтобы избежать излишних сравнений в OrderingUtil.identity, случай непустой коллекции обрабатывается отдельно. Данные особенности несут исключительно оптимизационный характер и не влекут функциональных отличий от реализации «в лоб», использующей foldLeft, поскольку повторные вхождения не влияют на результат.

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

Недостатком такого подхода является более многословная модель. Вероятно, подобного рода перечисление полей так или иначе понадобилось бы для вышеупомянутого отображения запросов, но определения полей выглядят скорее шаблонным кодом, чем полноценной частью логики. Четвёртая итерация могла бы определять макрос компилятора (с поддержкой аннотаций для нетривиальных сортировок) для автоматической генерации объектов полей, но представляется сомнительным, что реальные проекты дойдут до этого этапа. Текущий подход, тем не менее, позволяет легко добавлять и удалять поля, поскольку код, связанный с заданием порядка сортировки, никак не изменится.

Набор тестов для третьей итерации доступен по ссылке.


Заключение

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

Все примеры кода доступны в данном github репозитории

© Habrahabr.ru