Можно ли сгенерировать функцию равенства на основе сравниваемых данных?

Question

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

(define (same-set? l1 l2)
  (and (subset? l1 l2) (subset? l2 l1)))

Как такая функция будет сгенерирована автоматически? Может ли оно быть сгенерировано для произвольного типа данных?

Базовые c свойства отношения эквивалентности:

Свойство замещения: Для любых величин a и b и любого выражения F (x), если a = b, то F (a) = F (b) (если обе стороны имеют смысл, т.е. имеют правильную форму). Вот некоторые конкретные примеры c:

Для любых действительных чисел a, b и c, если a = b, то a + c = b + c (здесь F ( x) равен x + c);

Для любых действительных чисел a, b и c, если a = b, то a - c = b - c (здесь F ( x) есть x - c);

Для любых действительных чисел a, b и c, если a = b, то a c = b c (здесь F (x) равен x c);

Для любых действительных чисел a, b и c, если a = b и c не равно нулю, то a / c = b / c (здесь F (x) - это x / c).

Рефлексивное свойство: Для любого количества a, a = a. Свойство Symmetri c: для любых величин a и b, если a = b, то b = a. Переходное свойство: для любых величин a, b и c, если a = b и b = c, то a = c.

Можно ли сгенерировать функцию, которая подчиняется вышеуказанному свойства? Будет ли этого достаточно? Может ли знание типа данных помочь?

Если у вас есть идеи, как улучшить этот вопрос или пометить его, пожалуйста, прокомментируйте.

Answer 1

Два логических значения равны, если вы имеете одинаковое значение, два числа одинаковы. Два набора равны, если они имеют одинаковые элементы.

Это полезные равенства, но они не являются только равенствами, которые вы можете создать. Например, вы можете считать два числа равными, когда их четности (нечетные / четные) одинаковы. Или вы можете считать каждое число равным друг другу.

Как такая функция будет генерироваться автоматически?

В общем, это невозможно, потому что это зависит от вашего намерения. И никто не может читать ваши мысли.

Можно ли сгенерировать функцию, которая подчиняется указанным выше свойствам?

Ответ тривиален - да. По крайней мере, у вас есть (lambda (x y) #t), который говорит, что каждый объект равен любому другому объекту. Он удовлетворяет свойствам отношения эквивалентности, хотя и совершенно бесполезен.

Для нетривиального равенства, которое работает со всеми видами значений, у вас есть ссылочное равенство eq?, которое подчиняется свойству отношения эквивалентности (это может дать вам странный результат, если вы используете небезопасный API IIU C, но это не так c).

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

Answer 2

Я просто хочу немного расширить ответ @Sorawee Porncharoenwase. Они упомянули два вида равенства: ссылочное равенство с eq? и структурное равенство с equal?.

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

Некоторые полезные классы равенства, о которых следует помнить, - это эталонное равенство, структурное равенство для всех времен, структурное равенство для текущего времени и доменные спецификации c эквивалентности.

ссылочное равенство

Функция eq? реализует ссылочное равенство и имеет самые сильные гарантии, когда он возвращает истину, но когда он возвращает ложь, вы многому не научились.

(eq? x y) подразумевает, что x и y являются буквально одним и тем же объектом и что любая операция на x может быть заменено тем же на y, включая мутацию. Одна вещь, которая помогла мне объяснить это, была в книге «Царство ракеток», в которой говорилось, что если вы бреете x, то y также будет побриться, потому что это тот же объект.

Однако, когда (eq? x y) возвращает ложь, это довольно слабый соус. На многих структурах данных, которые включают выделение памяти, eq? может возвращать false просто потому, что указатели разные, даже если они неизменны, а все остальное одинаково.

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

Структурное равенство за все время

Это понятие равенства в настоящее время не поддерживается базовым Racket или стандартной схемой, хотя библиотеки, такие как Rackjure, могут предоставлять ограниченные версии этого с функциями, такими как egal?. Он реализует ссылочное равенство в изменяемых структурах данных, но структурное равенство в неизменяемых структурах данных.

Это должно обеспечить гарантию того, что если (egal? x y) вернет true сейчас, то это было верно в прошлом и будет продолжаться быть верным в будущем, пока существуют x и y.

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

Если вы хотите прочитать больше, см. Типы равенства в Pyret или Равные права для функциональных объектов .

Структурное равенство для текущего времени

Функция equal? реализует структурное равенство для текущего времени. Это означает, что две изменяемые структуры данных теперь могут быть равны, если они в настоящее время имеют все равные компоненты, даже если они не были равны в прошлом или не будут в будущем из-за мутации.

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

Спецификация домена c Эквивалентность

Например, для области числа и математика, вы можете захотеть, чтобы точное число 2.0 было равно точному целому числу 2. Для области поиска строк может потребоваться эквивалентность без учета регистра для строк и символов, чтобы A и a были эквивалентными. Для области наборов может потребоваться, чтобы порядок был неактуальным, чтобы (a b) и (b a) были эквивалентны.

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

Answer 3

Да, это определенно возможно. Некоторые языки программирования допускают автоматический синтез функции равенства c. Swift является таким примером.

Без автоматического синтеза c разработчик должен написать код для равенства, например, рассмотреть структуру:

struct Country: Equatable {
  let name: String
  let capital: String
  var visited: Bool

  static func == (lhs: Country, rhs: Country) -> Bool {
    return lhs.name == rhs.name &&
    lhs.capital == rhs.capital &&
    lhs.visited == rhs.visited
  }
}

С Swift 4.1 и выше это больше не нужно. Компилятор генерирует для вас функцию равенства:

struct Country: Equatable { // It's enough to just declare that the type is `Equatable` and the compiler do the rest
  let name: String
  let capital: String
  var visited: Bool
}

Давайте проверим это:

let france = Country(name: "France", capital: "Paris", visited: true)
let spain = Country(name: "Spain", capital: "Madrid", visited: true)
if france == spain { ... } // false

Обновление:

Даже после Swift 4.1, Реализацию по умолчанию можно переопределить с помощью собственной, пользовательской логики c. Например:

struct Country: Equatable {
  let name: String
  let countryCode: String
  let capital: String
  var visited: Bool

  static func == (lhs: Country, rhs: Country) -> Bool {
    return lhs.countryCode == rhs.countryCode
  }
}

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