Сортировка в Scala — пример на кошках

Предложенное вами решение мне очень нравится из-за возможности применения к любому типу, а не только Cat. Большое спасибо вам за идею! В конце, вроде бы, можно воспользоваться foldLeft(initial)(_ orElse _).

Касательно Keep — он был нужен только в первых двух случаях, в третьей итерации он отсутствует.

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

Сортировка в Scala — пример на кошках

Ах, верно, я в самом деле не доглядел. Да, в таком случае она дополнится функцией nullsFirst и итог будет симметричен функционалу ADT, вы абсолютно правы.

По поводу же перебора, я имею в виду, что, поскольку вы получаете поля явно (без использования аналога CatField), то конечная реализация, соответветствующая требованиям третьей итерации, будет выглядеть приблизительно так (scastie):

import scala.math.Ordering

object CatOrdering {

  case class Cat(breed: String,
                 /*...*/
                 owner: Option[String],
                 /*...*/)

  type FieldName = String

  // 1 bool: order -> asc - true, desc - false
  // 2 bool: empty values first -> asc - true, desc - false
  def byFields(fields: Seq[(FieldName, Option[(Boolean, Boolean)])]): Ordering[Cat] = {
    val breedOrder = get("breed", fields)
    val breedOrdering = "breed" -> breedOrder.map { case (order, _) => field(_.breed, order) }

    // ...

    val ownerOrder = get("owner", fields)
    val ownerOrdering = "owner" -> ownerOrder.map { case (order, emptyRule) => field(_.owner, order, emptyRule) } 

    // ...

    val orderings: Map[FieldName, Ordering[Cat]] = Map(
      breedOrdering, 
      /*...*/
      ownerOrdering, 
      /*...*/
    ).collect { case (key, Some(ordering)) => key -> ordering }

    if (fields.isEmpty)
      Ordering.by(_ => 0)
    else {
      val h = orderings(fields.head._1)
      fields.tail.foldLeft(h) { case (acc, (key, _)) => acc.orElse(orderings(key)) }
    }
  }

  private def get(fieldName: FieldName, seq: Seq[(FieldName, Option[(Boolean, Boolean)])]): Option[(Boolean, Boolean)] = ???

  private def field[T: Ordering](f: Cat => T, asc: Boolean): Ordering[Cat] = ???

  private def field[T: Ordering](f: Cat => Option[T], asc: Boolean, emptyValuesFirst: Boolean): Ordering[Cat] = ???
}

Если же вы имеете в виду только SortOrder, то без его аналога реализация так или иначе будет вынуждена использовать (Boolean, Boolean). Насколько это хорошо — вопрос дискуссионный, но я придерживаюсь мнения, что в данном случае ADT сделает код более читаемым и, следовательно, поддерживаемым.

К слову, касательно именно Boolean существует мнение, что их нужно выражать через функции, а не ADT — Destroy All Ifs — A Perspective from Functional Programming.

Сортировка в Scala — пример на кошках

Запись действительно очень лаконичная, спасибо за идею. Только, кажется, в конце должно быть nullsLast(cats(_.owner))

Тем не менее, при подобном подходе вижу следующие ограничения:

• Чтобы определить порядок сортировки по тому или иному полю, придётся перебирать каждое поле в отдельности.
• Изменение приоритета полей тоже будет осуществляться с помощью перебора.
• Добавление/удаление поля потребует изменения кода, связанного с сортировкой.

Иными словами, попробуйте представить, имея условный запрос от пользователя на сортировку данных, как предполагается этот запрос реализовывать в вашем подходе?

Сказ о полукольцах

Для Option не происходит удаление вложенных None, поэтому формула всё-таки остаётся верной. Вот все значения, которые может принимать такой тип:
Option[Option[A]] = None, Some(None), Some(Some(A)). Кардинальное число: |A| + 1 + 1.

По поводу функций — дельное замечание, мне, наверное, стоило об этом упомянуть. Речь, естественно, идёт не о функциях Scala как таковых, а о морфизмах. Потому что даже чистых детерминированных функций Boolean => Boolean можно набрать бесконечное число, так как True можно представить как True && True, True && True && True и т.д. Cardinality.of[A => B] — это количество возможных вариантов перевести элементы A в элементы B простым сопоставлением/таблицей.

Сказ о полукольцах

Я так понимаю, что вы пытаетесь рассматривать сумму типов как объединение множеств значений этих типов, но эти операции не совпадают.

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

Пример с Either[A, B] наиболее иллюстративен, так как Left[Int, Int](1) != Right[Int, Int](1), потому что различаются "обёртки"

Сказ о полукольцах

Не понял нотацию — поясните, что вы имеете в виду.

Сказ о полукольцах

Да, A => B — тип функции. Интуитивно понятно, что, если бы мы просто перемножили кардинальные числа, то получили бы результат, аналогичный произведению типов. Но количество функций из A в B в общем случае с количеством пар (A, B) не совпадает.

Откуда же берётся формула B^A? Рассмотрим произвольный элемент типа A. Функция A => B может переводить его в любой элемент типа B, значит, всего |B| вариантов. Рассмотрим следующий элемент типа A. Для него ситуация аналогичная — |B| вариантов. Это будет выполняться для любого представителя A. Соответственно, чтобы получить общее количество вариантов по превращению A в B, перемножим количество вариантов для отдельных представителей: |B| * |B| * |B| * |B| ... (всего |A| раз). Отсюда и следует |B => A| = |B|^|A|.

Аналогичным образом мы можем подумать о функции B => A как о представителе произведения типов (B, B, B, ..., B) (всего |A| раз). Элементами этого произведения можно однозначно задать любую функцию, а как вычислять кардинальное число такого типа уже известно.

Сказ о полукольцах

Нет, с `eitherCardinality` всё верно. В Scala `Either[A, B]` представлен двумя объектами: `Left[A, B]`, содержащим объекты типа `A`, и `Right[A, B]`, содержащим объекты типа `B`. `Left` с `Right` никак не пересекается, поэтому получаем строгую сумму.

Говоря о сумме типов вообще, можно провести аналогию, что сумма типов — это контейнер с ячейками, каждую из которых может занимать какой-либо тип, но всего может быть занята ровно одна ячейка. Соответственно, значения суммы типов — это «контейнер с заполненной ячейкой 1», «контейнер с заполненной ячейкой 2» и т.д. Таким образом, опять получаем строгую сумму, даже если типы в ячейках совпадают.

Сказ о полукольцах

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