Блог Scala Функ. программирование Классы типов Алгоритмы Библиотеки Упражнения Ресурсы

Ошибки при наследовании

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

Рассмотрим развитие построения архитектуры на примере моноидальной группы из теории категорий.

Возьмем для примера полугруппу и моноид, детально рассмотренные на соответствующих страницах.

Напомню определение полугруппы:

(S, +) является полугруппой (semigroup) для множества S и операции +, если удовлетворяет следующим свойствам для любых x, y, z ∈ S:

  • Closure (замыкание): x + y ∈ S
  • Associativity (ассоциативность): (x + y) + z = x + (y + z)

Также говорится, что S образует полугруппу относительно +.

И определение моноида:

Моноид (monoid) — это полугруппа с единичным элементом.

Более формально: (M, +) является моноидом для заданного множества M и операции +, если удовлетворяет следующим свойствам для любых x, y, z ∈ M:

  • Closure (замыкание): x + y ∈ M
  • Associativity (ассоциативность): (x + y) + z = x + (y + z)
  • Identity (тождественность): существует единичный элемент e ∈ M такой, что e + x = x + e = x

Давайте посмотрим, как это выглядит в Scala.

Полугруппа

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

Тогда определение полугруппы будет выглядеть так:

trait Semigroup[A]:
  extension (x: A)
    def |+|(y: A): A

Как видно, тут автоматически выполняется закон "Замыкание" исходя из определения метода - результирующий тип тот же самый, что и тип параметров.

Проверку ассоциативности надо же добавлять - сделаем это в сопутствующем объекте:

object Semigroup:
  def doTheSemigroupLawsHold[A: Semigroup](x: A, y: A, z: A): Boolean =
    val s = summon[Semigroup[A]]
    import s.|+|
    ((x |+| y) |+| z) == (x |+| (y |+| z))

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

Например, интуитивно понятно, что множество целых чисел относительно умножения образуют полугруппу:

Проверим это с помощью scalacheck на произвольной выборке:

property("Множество чисел образует полугруппу относительно умножения") {
  given Semigroup[Int] with
    extension (x: Int) override def |+|(y: Int): Int = x * y

  forAll(smallNumber, smallNumber, smallNumber) { (x: Int, y: Int, z: Int) =>
    assert(doTheSemigroupLawsHold(x, y, z))
  }
}

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

Замечание о переполнении: чтобы не думать о переполнении при умножении трех Int, выборка осуществлялась на маленьких числах от -100 до 100.

А например, множество целых чисел относительно вычитания полугруппу не образуют, потому что вычитание - не ассоциативная операция (((1 - 2) - 3) != (1 - (2 - 3)) <=> -4 != 2):

Это тоже можно проверить с помощью тестов:

property("Множество чисел НЕ образует полугруппу относительно вычитания") {
  given Semigroup[Int] with
    extension (x: Int) override def |+|(y: Int): Int = x - y

  exists(smallNumbers) { (x, y, z) =>
    assertEquals(doTheSemigroupLawsHold(x, y, z), false)
  }
}

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

Например, моноидальные законы используются для эффективного сворачивания последовательностей, в том числе с помощью распараллеливания. См. подробности в книге Scala with cats.

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

Исходный код

Тесты

Моноид

Теперь перейдем к Моноиду. Моноид - это полугруппа с единичным элементом. И здесь естественным образом напрашивается наследование:

trait Monoid[A] extends Semigroup[A]:
  def e: A

По сравнению с полугруппой добавляется закон "Тождественность", который необходимо проверить дополнительно к законам полугруппы:

object Monoid:
  def doTheMonoidLawsHold[A: Monoid](x: A, y: A, z: A): Boolean =
    val s = summon[Monoid[A]]
    import s.*
    Semigroup.doTheSemigroupLawsHold[A](x, y, z) &&
    ((e |+| x) == x) && ((x |+| e) == x)

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

Например, множество чисел относительно умножения с единичным элементом равным 1 является моноидом, а вот то же множество с той же операцией, но единичным элементом равным 0 - не моноид, потому что единичный элемент не удовлетворяет закону "Тождественность" (0 * x != x для всех x != 0).

Исходный код

Тесты

Проблемы архитектуры

Итак, какие могут быть проблемы с такой достаточно простой архитектурой: Monoid ---> Semigroup?

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

Представим, что Monoid был "изобретен" раньше и он у нас уже есть:

trait WrongMonoid[A]:
  def e: A
  extension (x: A) def |+|(y: A): A

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

Как для такой структуры определить Моноид?

given WrongMonoid[NonEmptyList[Int]] with
  override def e: NonEmptyList[Int] = ???
  extension (x: NonEmptyList[Int])
    override def |+|(y: NonEmptyList[Int]): NonEmptyList[Int] =
      x ++ y

Semigroup равен Monoid

Самым ужасным решением в этой ситуации было бы выдавать исключение при попытке получить единичный элемент для Monoid[NonEmptyList[A]]. Тем не менее такое встречается.

given WrongMonoid[NonEmptyList[Int]] with
  override def e: NonEmptyList[Int] =
    throw new IllegalArgumentException("NonEmptyList does not have an empty element")
  ...

Логика понятна: если у непустого списка нет единичного элемента, то мы запрещаем его использовать в каких бы то ни было ситуациях. Но по большому счету здесь получился самообман: вспомним моноидальные законы: если множество не удовлетворяет всем законам моноида, то это не моноид. И здесь видна попытка объединить полугруппу и моноид в одну структуру. Либо это делается по привычке: к моноиду все привыкли, а тут появляется какая-то новая структура. Либо это делается из-за "экономии" места.

Но оба варианта ошибочны:

Новая структура создана и она "живет своей жизнью", просто это принудительно "глушится" в коде.

Semigroup наследуется от Monoid

Ещё одним "решением" проблемы может стать оборачивание единичного элемента в Option:

trait WrongMonoid[A]:
  def maybeE: Option[A]
  extension (x: A) def |+|(y: A): A

В этом случае можно явно указать, что есть "моноиды" без единичного элемента:

trait WrongSemigroup[A] extends WrongMonoid[A]:
  override def maybeE: Option[A] = None

Этот подход по сути говорит правду: все "полугруппы" - это "моноиды" без единичного элемента. Но делает это с точности до наоборот: здесь вместо Monoid ---> Semigroup утверждается Semigroup ---> Monoid: что это полугруппа наследуется от моноида.

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

Заключение

Одно и тоже поведение можно реализовать многими способами, но есть несколько идей которым желательно следовать при построении архитектуры: