Is it possible to generate an equality function based on the data to be compared?

Question

Two Booleans are equal if the're the same value, two numbers similarly. Two sets are equal if they have the same elements. In case of checking two sets for equality we can use the following scheme/racket function:

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

How would such a function be generated automatically? Can it be generated for arbitrary data type?

The basic properties of an equivalence relation are:

Substitution property: For any quantities a and b and any expression F(x), if a = b, then F(a) = F(b) (if both sides make sense, i.e. are well-formed). Some specific examples of this are:

For any real numbers a, b, and c, if a = b, then a + c = b + c (here F(x) is x + c);

For any real numbers a, b, and c, if a = b, then a − c = b − c (here F(x) is x − c);

For any real numbers a, b, and c, if a = b, then ac = bc (here F(x) is xc);

For any real numbers a, b, and c, if a = b and c is not zero, then a/c = b/c (here F(x) is x/c).

Reflexive property: For any quantity a, a = a. Symmetric property: For any quantities a and b, if a = b, then b = a. Transitive property: For any quantities a, b, and c, if a = b and b = c, then a = c.

Is it possible to generate a function that obeys the above properties? Would that be enough? Could knowing the type of data help?

If you have any ideas on how to improve this question or tag it please comment.

Answer 1

I just want to expand on @Sorawee Porncharoenwase's answer a bit. They mentioned two kinds of equality, referential equality with eq?, and structural equality with equal?.

These different notions of equality should all follow the basic requirements of reflexivity, symmetry, and transitivity. But what sets them apart from each other is the guarantees that they give when they return true or false.

Some useful classes of equality to keep in mind are are reference-equality, structural-equality for all-time, structural-equality for the current time, and domain-specific equivalences.

Reference equality

The eq? function implements reference equality, and it has the strongest guarantees when it returns true, but when it returns false you haven't learned much.

(eq? x y) implies that x and y are literally the same object, and that any operation on x could be replaced with the same on y, including mutation. One thing that helped explain this to me was in the book Realm of Racket, saying that if you shave x, then y will also be shaved because it's the same object.

However, when (eq? x y) returns false that's pretty weak sauce. On the many data structures that involve allocating memory, eq? can return false simply because the pointers are different, even if they're immutable and everything else is the same.

This can be provided automatically by the programming language because it's really not much more than pointer-equality, and it doesn't have to generate any new behavior for new data structures.

Structural Equality for All-Time

This notion of equality is not currently well-supported by base Racket or standard Scheme, although libraries such as Rackjure can provide limited versions of this with functions like egal?. It implements reference equality on mutable data structures, but structural equality on immutable data structures.

This is meant to provide the guarantee that if (egal? x y) returns true now, then it has been true in the past and will continue to be true in the future as long as x and y both exist.

This can be provided automatically by the programming language as long as the language allows you to specify which data structures are immutable vs mutable, and enforces the immutability.

I'm not sure, but chaperone-of? may also be an example of following the ideas of "Structural Equality for All-Time", except that chaperone-of? isn't symmetric (and a naive symmetric-closure would lose transitivity).

Edit: as of Racket v8.6 released 2022-08-10, this is now filled by equal-always?.

If you want to read more, see Types of Equality in Pyret or Equal Rights for Functional Objects.

Structural Equality for the Current Time

The equal? function implements structural equality for the current time. This means two mutable data structures can be equal now if they currently have all equal components, even if they weren't equal in the past or won't be in the future due to mutation.

This can be provided automatically by the programming language as long as it always knows all the sub-parts of data contained within the data-structures.

Domain-specific Equivalences

For example for the domain of numbers and math, you might want the inexact number 2.0 to be equivalent to the exact integer 2. For the domain of string search, you might want case-insensitive equivalence for strings and characters so that A and a are equivalent. For the domain of sets, you might want order to be irrelevant so that (a b) and (b a) are equivalent.

Each domain is different, so this requires more effort on each domain. The programming language can't read your mind.

Answer 2

Yes, it is definitely possible. Some programming languages allow for automatic equality function synthesis. Swift is a such example.

Without automatic synthesis, the developer has to write code for the equality, e.g., consider a struct:

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
  }
}

With Swift 4.1 and higher, this is no longer necessary. The compiler generates the equality function for you:

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's test it:

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

Update:

Even after Swift 4.1, it's possible to override the default implementation with own, custom logic. For example:

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
  }
}

So, the developer is always in control. The equality won't be synthesised automatically, the developer has to add Equatable to the struct declaration. If after that they're not satisfied with the default implementation, or if it couldn't be inferred, there is always an option to override compiler's intention and provide a customized variant.

Answer 3

Two Booleans are equal if the're the same value, two numbers similarly. Two sets are equal if they have the same elements.

These are useful equalities, but they are not the only equalities that you can create. For instance, you can consider two numbers to be equal when their parities (odd/even) are the same. Or you can consider every number to be equal to each other.

How would such a function be generated automatically?

In general, it's not possible, because it depends on your intention. And no one can read your mind.

Is it possible to generate a function that obeys the above properties?

The answer is trivially yes. At the very least, you have (lambda (x y) #t), which says that every object is equal to every other object. It satisfies the equivalence relation properties, though it's totally useless.

For a non-trivial equality that works on all kinds of values, you have referential equality eq? which obeys the equivalence relation property (it could give you a weird result if you are using the unsafe API IIUC, but that's off-topic).

equal? can be used for structural equality on several values such as lists and those that are instances of a default transparent struct, and it also cooperates with custom equality that users provide. This is usually what you want to use in Racket.