[swift-evolution] Custom equality/hash for Sets

[Dave Abrahams]

on Thu Feb 18 2016, Jordan Rose <swift-evolution at swift.org> wrote:

>> On Feb 18, 2016, at 16:09 , Dave Abrahams via swift-evolution
>> <swift-evolution at swift.org> wrote:
>> 
>> 
>> on Thu Feb 18 2016, Jacob Bandes-Storch
>
>> <swift-evolution at swift.org
>> <mailto: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
>>> <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.
>> 
>> It might make sense.  How bad is the wrapper solution for user code?
>
> struct CustomHashableFoo: Hashable {
>   var value: Foo
>   func hash() -> Int {
>     // custom hash function here
>   }
> }
> func ==(a: CustomHashableWrapped, b: CustomHashableWrapped) {
>   // custom == here
> }
>
> Really not that bad, although you do have to get 'value' in and out of
> the box. 

But that's the part I'm worried about.

> It's also not reusable code—you have to rewrite the box for every
> type.

That's at least partially solvable: 

protocol CustomHash {
  associatedtype Base
  static func hash(Base) -> Int
  static func equal(Base, Base) -> Bool
}

struct CustomHashed<T: CustomHash> : Hashable {
  let value: T.Base
  func hash() -> Int { return T.hash(value) }
}

func == <T>(
  _ lhs: CustomHashed<T>, 
  _ rhs: CustomHashed<T>
) -> Bool {
  return T.equal(lhs, rhs)
}

// ---

// More compact than CustomHashableFoo at least.
struct MyFooHash : CustomHash {
  static func hash(Foo) -> Int { ... }
  static func equal(Foo, Foo) -> Bool { ... }
}

let s: Set<CustomHashed<MyFooHash>> = [ 
  CustomHashed(myFoo1), CustomHashed(myFoo2)
]

>
> I'd say you usually don't want to allow custom hash/== closures
> because (a) then you have to store them somewhere, and (b) the
> compiler won't usually be able to inline them away. You also end up
> with a Set<Foo> that doesn't behave like a normal Set<Foo>—maybe you
> can insert equal-but-not-identical elements—which is bad if anyone's
> relying on normal Set-like guarantees.

Not to mention that we don't know how to implement equality of closures.

If we were going to parameterize Set somehow, it would have to be

  CustomSet<T, H: CustomHash where H.Base == T>

and we'd want the ability to have a default for H when T conforms to
Hashable, which is currently beyond the language.


-- 
-Dave