Diabolical Interfaces

18 Apr 2019

Every graduating student can (or should) be able to tell you what an interface is about, it defines some methods that can be implemented by a class and creates an is-a relationship with the classes that implement it, but what we're going to talk about today are interfaces that are not possible to implement in the general case.

Comparable, IComparable, IEquatable (& Object)

I'm lumping these together even though they have different signatures and Object isn't even an interface because they share the same flaw. I can show what's wrong with all of these with this interface:

interface IsComparable {
    bool isEqualTo(IsComparable other);
}

The simplest possible implementation for objects is generally:

class Object IsComparable {
    bool isEqualTo(IsComparable other) {
        return this is the same instance as other;
    }
}

This is the only straightforward implementation, however, that really works, all other implementations have bizarre edge-cases. Say you have to define the method for String.

class String IsComparable {
    char[] chars;
    bool isEqualTo(IsComparable other) {
        if other isn't a String return false;
        return this.chars are all the same as other.chars;
    }
}

That seems like it works OK, but what if I want to compare strings without casing? Well, let's just make a new class and override the behavior.

class IgnoreCaseString(String) IsComparable {
    bool isEqualTo(IsComparable other) {
        if other isn't a String return false;
        return this.chars are all the same as other.chars when compared without case;
    }
}

The problem arises now that isEqualTo is no longer commutative.

name = String("kyle sletten")
Name = IgnoreCaseString("Kyle Sletten")

Name isEqualTo name # => true
name isEqualTo Name # => false

But wait! I can fix that!

class String IsComparable {
    char[] chars;
    bool isEqualTo(IsComparable other) {
        if other isn't a String return false;
        if other is a derived type of String return other isEqualTo this;
        return this.chars are all the same as other.chars;
    }
}

class IgnoreCaseString(String) IsComparable {
    bool isEqualTo(IsComparable other) {
        if other isn't a String return false;
        if other is a derived type of IgnoreCaseString return other isEqualTo this;
        return this.chars are all the same as other.chars when compared without case;
    }
}

OK, but let's add another test case:

name = String("kyle sletten")
Name = IgnoreCaseString("Kyle Sletten")
naMe = String("kyle Sletten")

Name isEqualTo name # => true
name isEqualTo Name # => true
naMe isEqualTo name # => false
naMe isEqualTo Name # => true

So now isEqualTo isn't transitive, what is the world coming to! It becomes very clear that the only way to have more than one implementation of isEqualTo (without weirdness) is to require two types to always be exactly equal.

class String IsComparable {
    char[] chars;
    bool isEqualTo(IsComparable other) {
        if other isn't a String and not a derived type return false;
        return this.chars are all the same as other.chars;
    }
}

class IgnoreCaseString(String) IsComparable {
    bool isEqualTo(IsComparable other) {
        if other isn't a IgnoreCaseString and not a derived type return false;
        return this.chars are all the same as other.chars when compared without case;
    }
}

Comparable<T>, IComparable<T>, IEquatable<T>

Never fear, generics are here. Let's make the interface generic on the comparing type, and then everything will be OK.

interface IsComparableTo<T> {
    bool isEqualTo(T other);
}

class String IsComparableTo<String> {
    char[] chars;
    bool isEqualTo(String other) {
        return this.chars are all the same as other.chars;
    }
}

class IgnoreCaseString(String) IsComparableTo<IgnoreCaseString> {
    bool isEqualTo(IgnoreCaseString other) {
        return this.chars are all the same as other.chars when compared without case;
    }
}

But now we're doing static dispatch, which works well until it doesn't.

name = String("kyle sletten")
Name = IgnoreCaseString("Kyle Sletten")

Name isEqualTo name # => true
name isEqualTo Name # => true
Name isEqualTo (Name as String) # => false

So we need to do some extra dynamic-ish stuff.

class IgnoreCaseString(String) IsComparableTo<IgnoreCaseString> {
    bool isEqualTo(String other) {
        if other is IgnoreCaseString return this isEqualTo (other as IgnoreCaseString);
        return this String.isEqualTo other;
    }
    bool isEqualTo(IgnoreCaseString other) {
        return this.chars are all the same as other.chars when compared without case;
    }
}

Yeah, that should do it.

name = String("kyle sletten")
Name = IgnoreCaseString("Kyle Sletten")

Name isEqualTo name # => true
name isEqualTo Name # => true
Name isEqualTo (Name as String) # => true

Have we won, yet? All of our comparisons work and the world is set right, except now we have this silly extra IgnoreCaseString that we don't really need and means we need to create new objects when we want to compare strings using IgnoreCaseString. We've lost any ability to compare different things too, and so it seems like…

What if we just, didn't?

How would we represent IsComparable if we decided that we didn't want to try to do all that just to get them to work right? Is there a simpler IsComparable that would work better?

interface CanCompare<T> {
    bool areEqual(T left, T right);
}

IgnoreCase = CanCompare<String, String> {
    bool areEqual(String left, String right) {
        return left.chars are all the same as right.chars when compared without case;
    }
}

Which… is exactly what C# ultimately added to address the issues brought up in this post. Standard library types will accept some other object to decide how to do the comparison for Dictionaries, etc.

public Dictionary (System.Collections.Generic.IEqualityComparer<TKey> comparer);