5 ms·

Multiple forms of equality: I think there should be just one "equality": the obvious structural one, which can be inferred by a compiler. What examples are ther

• mcbits 10y ago
  new Rational(2, 3) == new Rational(4, 6) You could implement Rationals to be structurally equal by simplifying them immediately on construction, but that may be a lot of unnecessary computation in some cases.
  • jstimpfle 10y ago
    With more context we could probably agree that it's not unnecessary computation if you want to do anything useful with the data.
    • hota_mazi 10y ago
      Indeed. And you only have to do it once, you can then store the result (you should probably make that calculation lazily, though).
      • jstimpfle 10y ago
        Lazily or not, that would be a global design decision (use a lazy language or not)
    • mcbits 10y ago
      In a formula with multiple Rationals, it wouldn't always be necessary to simplify them before using them. You could just simplify the result if/when it's compared to another result. Also, the UI may need to display the unsimplified fraction. If you simplified them immediately, you'd have to store a factor somewhere to reconstruct the original (and not in the Rational class because that would ruin structural equality). In other words, "equal" for I/O purposes and "equal" for mathematical purposes could be different.
      • jstimpfle 10y ago
        How'd you compare the unsimplified number then? How would it be obvious at the calling site what happens? Better explicitly compare only the simplified part (again, structurally).
        • mcbits 10y ago
          The most straightforward way would be to simplify during the equivalence check and maybe cache the value. Or maybe there is some trick to compare them without simplifying. Point is that you can have a notion of "equal but not identical". No doubt it's also possible to represent rationals with only structural equality, but I'd have to see two competing implementations to judge which is more intuitive to use.
          • dllthomas 10y ago
            > Or maybe there is some trick to compare them without simplifying. a / b == c / d is equivalent to a * d = c * b, although whether that's a good approach depends on a lot of things.
  • smnplk 10y ago
    Clojure supports rational type and it does simplify them. (def a (/ 1 2)) (def b (/ 8 16)) (= a b) true
• Retra 10y ago
  "Has the same hash value" is a very important set of equality relations which can depend on many factors.
  • jstimpfle 10y ago
    IMO comparing hashes instead of just comparing would only make sense if it's semantical, i.e. explicit at the call site. Why not call equals explicitly on the hash values? Can you make a case for keeping it implicit?
    • Retra 10y ago
      I don't know why implicit equality is relevant here. The idea is that you'd explicitly recognize that there are multiple forms of equality, and that the one you want depends almost entirely on the problem domain. So you shouldn't have any 'implicit' or 'preferred' equality. You'd always let the call site dictate which equality relation it needs. You asked for a non-structural equality relation, and I gave you a whole class of them. There are many more. There isn't even one kind of 'structural equality': are two things equal if they have the same memory layout? The same AST representation? What if the layout depends on the allocator? What if they are identical but must be treated differently through aliases?
      • jstimpfle 10y ago
        You agree it should be explicit. But notice that explicit hash equality is just hashing followed by structural equality. Considering different abstraction levels like AST or memory layout: This is moving up and down the levels of abstraction. It's conventional wisdom that you shouldn't do this in a single context (like a function, module, or even a programming language). But it's a good point - powerful languages like C present all these levels at once. In other words, there is often an impedance mismatch. Structural equality might be not quite the same to the compiler and to the programmer.
        • Retra 10y ago
          And structural equality is just a special (also arbitrary) kind of hash equality. You still have to specify what kind of structure you're comparing. The "structural equality" that you are referring to is vague not uniquely determined.
• louthy 10y ago
  "ABC" == "abc" Depending on the context, case insensitive equality checking may be required. Also precision on floating point value comparisons. An interesting approach to this in C# (and other languages) is to use ad-hoc polymorphism: public interface Eq<A> { bool AreEqual(A x, A y); } public struct EqInt : Eq<int> { public bool AreEqual(int x, int y) => x == y; } public struct EqDbl : Eq<double> { public bool AreEqual(double x, double y) => Math.Abs(x - y) < 0.00001; } public struct EqStringExact : Eq<string> { public bool AreEqual(string x, string y) => x == y; } public struct EqStringIgnoreCase : Eq<String> { public bool AreEqual(string x, string y) => String.Equals(x, y, StringComparison.CurrentCultureIgnoreCase); } public static class GenericCode { public static A UseFirstIfEqual<EQ, A>(A fst, A snd) where EQ : struct, Eq<A> => default(EQ).AreEqual(fst, snd) ? fst : snd; } GenericCode.UseFirstIfEqual<EqInt, int>(10, 10); // 10 GenericCode.UseFirstIfEqual<EqInt, int>(10, 20); // 20 GenericCode.UseFirstIfEqual<EqDbl, int>(10.0, 10.0); // 10.0 GenericCode.UseFirstIfEqual<EqDbl, int>(10.0, 20.0); // 20.0 GenericCode.UseFirstIfEqual<EqStringExact, string>("ABC", "abc"); // "abc" GenericCode.UseFirstIfEqual<EqStringIgnoreCase, string>("ABC", "abc"); // "ABC" It's slightly more novel than the interface approach, and allows for retrospective equality behaviours to be authored for a sealed type, and importantly, for the selection of the most appropriate equality operation for any particular context. I don't have a compiler to hand, so apologies for any errors!
• jstimpfle 10y ago
  Found a use case: performance optimizations. If there are functional dependencies that the compiler doesn't know, some fields don't need to be compared.
• tel 10y ago
  Quotients are often used to describe new behavior. You could reasonably say that this ought to define a new type, but it's still an example of a meaningful coarsening of equality. For example, to define rational numbers using only integers you take a rational to be a pair (n, d) but with a new equality such that (1, 2) and (2, 4) are equated.
• Coincoin 10y ago
  Is the angle -90 equal to 270? Is the quotient 1/2 equal to 3/6 Is the string "Bébé" equal to "Bebe"? Is the float 0.555555559 equal to 0.6? Is the color RGB(1,1,1) equal to Lab(100,0,0)? Is the equation y=3x+2 equal to y-2=3x? Is the function x=>2+x equal to y=>2+y?
  • jstimpfle 10y ago
    > Is the angle -90 equal to 270? > Is the quotient 1/2 equal to 3/6? I think these are good examples that come up in the real world a lot. The representation structures we use are not sufficient for precise specification. So we have to overspecify (making a superfluous choice in representation, -90, 270, 630?). My opinion still is that data must be normalized with explicit procedure calls. Doing stuff implicitly is neither beneficient to efficiency nor to comprehensibility. Explicit normalization allows to leverage what the compiler _can_ infer. The other questions I have to return because it's not even clear to me, "Should they be"?
    • mbrock 10y ago
      Whether they should be depends on your needs, so it's nice to be able to choose the equality semantics for your application's types.
    • dllthomas 10y ago
      > My opinion still is that data must be normalized with explicit procedure calls. Doing stuff implicitly is neither beneficient to efficiency nor to comprehensibility. It can certainly benefit comprehensibility. Needing to explicitly normalize before I can apply standard comparisons leaves more space for things to go wrong. "Having a value of this type means that I have a normalized value" means I have fewer things to keep track of. (I do note that there is significant space between "it can benefit comprehensibility" and "it will always benefit comprehensibility" - that depends on what I need to be readily able to pull out of the implementation from a quick read of surface syntax) Also, some things may have an easy equality check while normalizing may be expensive or impossible - although I sadly can't think of any examples off the top of my head.
  • 10y ago
• justinpombrio 10y ago
  How would you want the compiler to compare graphs for equality? Graph isomorphism is a hard problem.
  • jstimpfle 10y ago
    I seem to think of equality as something trivial. Granted that structural equality isn't graph isomorphism. But I don't see why something as specific and performance-sensitive as that deserves the tag "equality". Make a function graphsIsomorphic(), where's the problem? Btw. in my practice (writing really dull code, and some algorithms) I've never seen the need for complex equality functions. In practice I test IDs - typically integers or short strings.
• dllthomas 10y ago
  I feel like all of the responses are missing most of your question. As I read you, you understand that there are other questions we might want to ask, but why not call them "compareRationals" or whatnot rather than giving them all the same name? I think that it comes down to a question of interfaces/abstraction. Quite a few languages provide you interfaces for asking both questions, "are these structurally equivalent" and "are these practically equivalent" for whatever choice of "practical".
  • jstimpfle 10y ago
    Thanks for putting it that way. I realize "equality" and "equivalence" gets confused a lot here. Equality is a special case of equivalence. It seems absurd to me to have more than one equality.
    • dllthomas 10y ago
      > It seems absurd to me to have more than one equality. Mathematics has several. Probably the most useful for CS is the notion from logic of "extensional equality" - two things are equal if I can't tell them apart. But we quickly want to restrict what approaches we can use, or for most languages that would necessarily be reference equality. Structural equality is one such restriction. For an abstract data type, there's a strong line of reasoning that would say two values should be equal if they aren't distinguishable through the abstraction.