Cпецификация волшебного мира 3: Setoid

Перевод статьи Tom Harding: Fantas, Eel, and Specification 3: Setoid. Опубликовано с разрешения автора.

Поздравляю! Вы освоили основы daggy, закрепили введение в описание типов и готовы начать ваше путешествие через Fantasy Land. Первая остановка: сетоид.

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

Это может показаться странным, но как мы можем достоверно знать, были ли две функции эквивалентны? В то время как наш компилятор будет уверенно говорят нам, что 100 * 10 эквивалентно 1000, он не будет достаточно храбрым, чтобы сказать x => x * x эквивалентно x => Math.pow(x, 2); это действительно не тривиальная вещь для решения!*

Тип, являющийся Fantasy Land-совместимым сетоидом, должен иметь метод equals со следующим описанием:

equals :: Setoid a => a ~> a -> Boolean

Не страшно, я надеюсь? Просто способ выяснить, является ли одна вещь равной другой. Давайте напишем экземпляр типа Setoid для типов из нашей первой статьи:

// Проверить, что каждая точка соответствует
// equals :: Coord ~> Coord -> Bool
Coord.prototype.equals = function (that) {
  return this.x === that.x
      && this.y === that.y
      && this.z === that.z
}
// Проверить каждую Coord с Coord.equals
// equals :: Line ~> Line -> Bool
Line.prototype.equals = function (that) {
  return this.from.equals(that.from)
      && this.to.equals(that.to)
}
// Эта «правильность» должна совпадать с этой!
// equals :: Bool ~> Bool -> Bool
Bool.prototype.equals = function (that) {
  return this instanceof Bool.True
    === that instanceof Bool.True
}
// Проверить головы списков, потом их хвосты
// equals :: Setoid a => [a] ~> [a] -> Bool
List.prototype.equals = function (that) {
  return this.cata({
    // Обратите внимание на использование двух разных Setoid:
    Cons: (head, tail) =>
      head.equals(that.head) // a
        && tail.equals(that.tail), // [a]
    Nil: () => that instanceof List.Nil
  })
}

Вы поняли, да? Если у нас есть несколько конструкторов, мы проверяем по этим конструкторам. Если конструкторы принимают аргументы, тогда мы, вероятно, проверяем их тоже. Конечно, если мы это сделаем, аргументы должны быть сетоидами; как еще мы можем проверить, что они эквивалентны?

По сути, это требование из-за того что у нас есть ограничение типа List на реализации метода equals: нам нужно иметь возможность сравнивать всю структуру, внутренности - всё!

К сожалению, гадкий побочный эффект использования JavaScript приводит нас к смешиванию === и .equals, в зависимости от того, с чем мы работаем: примитивными типами или нет. Это позор; в других языках мы можем переписать поведение === для собственных стилей, но не в JavaScript. Вы можете добавить .equalsк прототипам примитивных значений, но это, как правило, считается плохой идеей. Лучше не возиться со стандартными прототипами.

Тем не менее, эта реализация .equals весьма неплоха, правда?

Все эти структуры Fantasy Land с законами, которые должны соблюдаться для реализации, чтобы быть правильными и Setoid не исключение. Для того, чтобы убедиться, что ваш тип работает при использовании с другими библиотеками и алгоритмами, есть всего три вещи, которые мы должны помнить. Во всех случаях:

• a.equals(a) === true,что мы называем рефлексивность.
• a.equals(b) === b.equals(a). Это симметрия или коммутативность — вы можете передавать значения в обратном порядке. Помните, что такие операции, как вычитание не коммутативны, и есть еще другие не коммутативные примеры, что может удивить вас!
• Если a.equals(b) и b.equals(c), значит a.equals(c) всегда верно: закон транзитивности.

Мы с легкостью можем увидеть, что всё это будет работать для реализации .equals, до тех пор пока мы придерживаемся описания типа!

Если ни один из этих законов особо не удивил вас, то это отлично! Это означает, что у вас хорошая интуиция и вы понимаете что такое Setoid. Позже в этой серии, мы доберемся до более сложных конструкций и интуиция будет очень ценной для понимания как использовать их.

Если вы в отчаянии от примера, почему бы не написать реализацию .equals для существующего типа Array, чтобы сделать из него Setoid? Добавьте его к Array.prototype - я никому не скажу - и будьте уверены, что ваша реализация подчиняется вышеуказанным законам.

Если вы хотите, вы также можете получить функцию называемую notEquals используя метод .equals от типа Setoid:

// notEquals :: Setoid a => a -> a -> Bool
const notEquals = x => y => ...

Если вы не в отчаянии от упражнения, (или вы смогли насытить своё горящее желание наконец-то), мы перейдём к тому, из-за чего вся эта суета? Если у нас есть официальные определения таких понятий, как Setoid (каким бы простым оно не было), мы можем определить разумные интерфейсы для работы со всеми типами данных. Рассмотрим эту функцию:

nub :: Setoid a => [a] -> [a]

Я думаю, nub может быть мое любимое имя любой функции. На практике, nub возвращает копию полученного массива с удалением дубликатов в нём. Вот и всё! Возможно, вы также слышали его называют uniq. На первый взгляд, его легко написать в JavaScript:

const nub = xs => xs.filter(
  (x, i) => xs.indexOf(x) === i)

Это нормально, но у нас появляется проблема: для сложных структур, это работает только если эквивалент значения всегда занимает одинаковое место в памяти. Однако это не всегда так: если мы попытаемся [[]].indexOf([]), мы получим -1, хотя мы можем ясно видеть [] в массиве! Как мы можем это исправить? Setoid нам в помощь!

// indexOf :: Setoid a => [a] -> a -> Int
const indexOf = xs => x => {
  for (let i = 0; i < xs.length; i++)
    if (xs[i].equals(x)) return i
  return -1
}
// nub_ :: Setoid a => [a] -> [a]
const nub_ = xs => xs.filter(
  (x, i) => indexOf(xs)(x) === i
)

Теперь у нас есть функция, которая будет работать для любого массива типа Setoid. Если мы знаем, что наша функция будет использоваться ответственно (это когда только с массивами типа Setoid), мы могли бы даже добавить исключение, чтобы заставить её работать с примитивами - также как эквивалентность в Ramda работает! Господи, вы посмотрите на весь этот полиморфизм.

Я думаю, что я чаще всего вижу упоминание о Setoid (и Eq, как они называют это в мире Haskell) между функциями List и Array, которые дают массу возможностей для упражнений для закрепления понимания:

• Написать функцию, для определения когда список значений формирует палиндром (например, список эквивалентен себе перевёрнутому). Нам понадобиться Setoid для внутреннего типа, чтобы убедиться, что правильный и обычный. Как небольшая подсказка, вы можете написать наивное решение с функцией zipWith, которую мы упоминали раньше…
• Используйте daggy для создания типа Set, который хранит набор уникальных значений; вы даже можете повторно использоавть nub_! Вам потребуются методы добавления и удаления элементов, и понадобится проверить, существует ли элемент уже во внутреннем хранилище (возможно массиве).

Setoid, без сомнения, простейшая структура из всей спецификации Fantasy Land, но это делает её хорошим примером для начала. Для большинства, интуиция поможет понимать всё совершенно естественно, и ни один из законов не должен шокировать.

Не расслабляйтесь, впрочем! В следующий раз, мы перейдем к гораздо более странным и удивительным структурам: semigroup. Оу.

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

Берегите себя ♥

* Важным моментом здесь является то, что эквивалентность гораздо глубже, чем равенство. Просто попробуйте ввести (x => x) === (x => x) в Node REPL.

Слушайте наш подкаст в iTunes и SoundCloud, читайте нас на Medium, контрибьютьте на GitHub, общайтесь в группе Telegram, следите в Twitter и канале Telegram, рекомендуйте в VK и Facebook.

Статья на Github