[swift-evolution] Custom equality/hash for Sets

[plx]

I think the points already-made about the weak semantics of such a type are well-founded and should curtail the idea of changing `Set` itself to take in optional “customized” functions for equality/hash.

However, this scenario, I think, makes an *excellent* testbed for Swift 3’s hopefully-still-incoming "conditional conformance” functionality (e.g. the thing that would let you say `Array:Equatable where Element:Equatable`).

Within Swift as it is right now, if you really want a “customizable set” as-requested, about the best you can do at this time is like so:

// step 1: a convenience protocol
protocol SetValueWrapper : Equatable, Hashable {
  typealias Value // note: it’s useful to require `:Equatable`, but not necessary
  var value: Value { get }
  init(_ value: Value)
}

// step 2: a convenience wrapper around `Set`
// 
// re-implement as much of the `Set` APIs as you need,
// but in a way that lets you ignore internal use of `W`
// 
// Note that in practice you may need to write this as
// struct WrappedValueSet<V,W:SetValueWrapper where V==W.Value>,
// as I’ve run into bugs where the compiler needs that `V` to figure things out.
// I’ve written it as it should be, not how it may need to be to use today.
struct WrappedValueSet<W:SetValueWrapper> {
   private var storage: Set<W>  

  // example re-implementations:
  //
  func contains(element: W.Element) -> Bool { return self.storage.contains(W(element))

  mutating func insert(element: W.Element) { self.storage.insert(W(element))

}

// step 3: per each customized equality/hash you need, write a wrapper;
// e.g., here is a complete “ObjectPointer” wrapper as per the original request:
struct ObjectPointer<T:AnyObject> : SetValueWrapper {

  typealias Value: T

  let value: T
  
  init(_ value: T) { self.value = value }

  var hashValue: Int { return ObjectIdentifier(value).hashValue

}

func ==<T>(lhs: ObjectPointer<T>, rhs: ObjectPointer<T>) -> Bool {
  return lhs.value === rhs.value
}

…and you’re done; the cost is basically one tedious session of re-implementing the Set-related APIs you want on your wrapper, and then one (short!) wrapper for each custom equality/hash combo you need.

This isn’t *great*, but it seems perfectly-reasonable to me when weighed against the drawbacks of a `Set`-like thing that took custom logic in its `init`.

With conditional-conformances in place, you can also improve your quality of life a lot; it’s a bit tricky, but you could — if conditional conformances work as I expect they will — use some trickery to “punch out” `Equatable` and `Hashable`, like so:

/// Basic protocol for “this is a wrapper”.
protocol ValueWrapper {
  typealias Value
  var value: Value { get }
  init(_ value: Value)
}

/// Specialized-wrapper-of-wrapper that is meant to source:
/// - Equatable, Hashable from the wrapped-value
/// - everything else (as needed) from the wrapped-value’s wrapped-value
///
/// …which means we can keep adding utility conformances here based on `W.Value`’s implementations,
/// while still having “punched-out” W’s native possible `==` and `hashValue` implementations in favor of
/// whatever implementations thereof are supplied by W.
struct WrapperWrapper<W:protocol<WrappedValue,Equatable,Hashable> where W.Value:WrappedValue> : WrappedValue {

  typealias Value = W.Value // note it somewhat hides the existence of the inner wrapper 
  
  private let storage: W
  var value: Value { return self.storage.value }

  init(_ value: Value) { self.storage = W(value) }
  
  // note it uses the wrapper’s (customized) hashValue implementation
  var hashValue: Int {
   return self.storage.hashValue 
  }

}

// note again this uses the *wrapper*’s implementation:
func ==<W>(lhs: WrapperWrapper<W>, rhs: WrapperWrapper<W>) -> Bool {
  return lhs.storage == rhs.storage // use wrapper’s (customized) equality
}

// but now we can start adding nice-to-have conformances based on `W.Value`
extension WrapperWrapper:CustomStringConvertible where W.Value:CustomStringConvertible {
  
  var description: String { return self.value.description }

}

// and so on and so forth, as-needed...

Although this still doesn't free you up from writing the “custom ==/hash wrappers”, if you rewrite the set-wrapper from step 2 in terms of a `WrapperWrapper` (hopefully with a better name!), then the values that are stored in the Set will pick up protocol conformances of interest from the underlying value, and thus trigger any conditional-conformances that are defined e.g. on `Set`, making it easy for you to add them to your own wrapper if you want, and so on.

Is this *great*? Arguably not, but I think it’s a reasonable situation, especially since the tedious parts (set-wrapper, wrapper-wrapper) are each write-once, re-use often, and the per-customization chores are really short (~5-10 lines, mostly boilerplate).

And again, you don’t *need* the set-wrapper or wrapper-wrapper, they just streamline the sites-of-use of such constructs.

Some form of actual “struct inheritance” might reduce the need to manually emulate it with protocols like the above, but protocols + conditional-conformance let you emulate enough of that feature to work out “OK” in this case, I think. 

> On Feb 18, 2016, at 4: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
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160219/df31b018/attachment.html>