[swift-evolution] Custom equality/hash for Sets

[Jacob Bandes-Storch]

Thanks to everyone for a great discussion so far.

I'm interested in Joe's idea of private/local protocol conformances. What I
think might work nicely is the ability to provide a specific protocol
witness (which I think is the right terminology for the "bundle of function
pointers") for a conformance requirement of a type parameter. This would be
*part of the type*, so like Joe said, "set1 == set2" wouldn't work unless
they were using the same witness. That's totally fine and would be expected
behavior, as long as the difference between the types is obvious to the
user. I think you'd want to require it be specified explicitly, rather than
inferring it from the existence of some local extension.

Maximilian's point about behaviors makes sense in this context too, and I
think we're kind of getting at the same idea. Instead of a "var behavior",
it's more like a "protocol behavior":

    // All protocol requirements must be specified here; this declaration
basically provides an explicit protocol witness
    private *protocol behavior* pointerEquatable<AnyObject>: Hashable,
Equatable {
        var hashValue: Int { return unsafeAddressOf(self).hashValue }
        func ==(lhs: Self, rhs: Self) -> Bool { return lhs === rhs }
    }

    // This uses the witness provided by pointerEquatable instead of the
default one
    let objs = Set<@pointerEquatable MyClass> = []
    objs.insert(something)

Does this defeat possible optimizations, or cause issues like Joe mentioned
with "as?" lookups?

On Fri, Feb 19, 2016 at 11:11 AM, Joe Groff <jgroff at apple.com> wrote:

>
> On Feb 18, 2016, at 2:58 PM, Jacob Bandes-Storch via swift-evolution <
> swift-evolution at swift.org> wrote:
>
> Would it make sense for the standard library Set to provide variants (or
> parallel versions of the same data structure) that take custom hashValue/==
> implementations at init time (functions taking in Elements), rather than
> relying on Hashable/Comparable protocols?
>
> Use case: I want a set of objects that are compared for equality using ===
> rather than ==. This doesn't seem possible today, using Set, without
> creating some sort of wrapper object.
>
> This particular case would be analogous to using NSHashTable with
> NSPointerFunctionsObjectPointerPersonality. (Maybe all I'm asking for is a
> Swiftier API for NSHashTable — including ArrayLiteralConvertible, using
> generics instead of UnsafePointer<Void>, etc.)
>
> Similarly, C++'s unordered_map
> <http://en.cppreference.com/w/cpp/container/unordered_map> and friends
> have template parameters specifying the hash function and equality
> comparator, which use std::hash and == by default.
>
> (Apologies if this has been discussed already; I haven't seen it.)
> Jacob
>
>
> At an implementation level, we already pass a bundle of function pointers
> for the Equatable and Hashable conformances as part of the generic calling
> convention. In the implementation model, protocol conformances are
> independent entities, so technically the same type could conform to the
> same protocol multiple times in different ways. We could theoretically let
> you provide a scoped private conformance to Hashable overriding the default
> one:
>
> func foo() {
>   extension Int: private Hashable {
>     var hashValue: Int { return myHash(self) }
>   }
>
>   // This dictionary would use the local Int: Hashable
>   let dict: Foo<Int, Int> = [...]
>
>   use(dict)
> }
>
>
> Now, there would definitely be weird effects to this, since it allows for
> types that look the same but are formally different, since the `Key:
> Hashable` conformance is an implicit parameter to the type. For example,
> this wouldn't work:
>
> func returnMyWeirdDictionary() -> Dictionary<Int, Int> {
>   extension Int: private Hashable {
>     var hashValue: Int { return myHash(self) }
>   }
>
>   // This dictionary would use the local Int: Hashable
>   let dict: Foo<Int, Int> = [...]
>
>   // ERROR: dict has type Dictionary<Int, Int> (using local Int: Hashable
> conformance),
>   // but return type is declared Dictionary<Int, Int> (using default Int:
> Hashable conformance)
>   return dict
> }
>
>
> It also has interesting interactions with the runtime's support for
> protocol conformance lookup via `x as? P` casts—if there's more than one P
> conformance for the dynamic type of x, which one should the runtime pick?
>
> -Joe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160219/5b1d3fa1/attachment.html>