[swift-evolution] Custom equality/hash for Sets

[Joe Groff]

> 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/b550ff4e/attachment.html>