[swift-evolution] Custom equality/hash for Sets

Maximilian Hünenberger m.huenenberger at me.com
Fri Feb 19 11:41:44 CST 2016


> Am 19.02.2016 um 15:47 schrieb Andrew Bennett <cacoyi at gmail.com>:
> 
> Hi Maximillian,
> 
> On Friday, 19 February 2016, Maximilian Hünenberger <m.huenenberger at me.com <>> wrote:
> Discussions on different index handling should belong to another thread if there isn't one already.
> I mentioned indices only to provide context :) the linked document (Swift master) discusses an approach that fixes many of the issues with a custom wrapper approaches mentioned here.
> 

Is there already a thread on swift-evolution which discusses these index changes?

> 
> Your proposed Set change covers at least the custom Hashable behavior.
> What about Equatable? I think it could be expressed as behaviors.
>  
> Custom Equatable could also be implemented as a similar closure (Element,Element)->Bool. I left it off, but I probably shouldn't have. My main goal was to minimise changes to the existing interfaces and provide similar performance.
> 
> I wonder if there's any cases someone would want anything other than Equatable or pointer comparison.
> 
> As for your behaviour suggestion: I may be misinterpreting how it works. I like the idea, but it seems like a much larger change than is necessary. It may change all the type signatures in normal usage, and obsfucate the Element type.
> 
> Ideally the sets type would only show the element type, not implementation details like a custom hash algorithm.
> 

I thought about "Property behaviors" (separate thread) where such an addition could be difficult to implement.

But if they are implemented we can then generalize them to a transparent wrapper type.

Pseudo implementation:

	var behavior pointerHashable<Value: AnyObject>: Value {}
	extension pointerHashable: Hashable {
		var hashValue: Int { return ObjectIdentifier(self).hashValue }
	}
	func ==<T>(lhs: pointerHashable<T>, rhs: pointerHashable<T>) -> Bool {
		return ObjectIdentifier(lhs) == ObjectIdentifier(rhs)
	}

	//usage
	var set: Set<pointerHashable<MyClass>> = [MyClass(), MyClass()]
	let firstElement = set.first! // returns MyClass

> If you're happy to change the Set's type signature for each hash/equality algorithm then a wrapper like Nicola suggests is probably good enough.
> 
> Even easier if you're happy to manually wrap and unwrap:
> 

a behavior would implicitly wrap/unwrap

> class HashableReference<T: AnyObject>: Hashable {
>     let object: T
>     var hashValue: Int {
>         return ObjectIdentifier(object).hashValue
>     }
> }
> func ==<T: AnyObject>(lhs: HashableReference<T>, rhs: HashableReference<T>) -> Bool {
>     return ObjectIdentifier(lhs) == ObjectIdentifier(rhs)
> }
> 
> Apologies for any errors, this was done from my iPhone from memory.

However if the behavior cannot be implemented easily this approach would be the best.

- Maximilian

> 
> 
> - Maximilian
> 
> Am 19.02.2016 um 11:58 schrieb Andrew Bennett via swift-evolution <swift-evolution at swift.org <>>:
> 
>> Good points Dimitri,
>> 
>> I only wrote this quickly, so please look for other issues too, I don't expect it to be complete by any means.
>> 
>> I think a way to get an element's hashValue should probably be exposed, similar to `collection.next(index)` that I mentioned earlier. I think this is useful, but I don't think it's actually necessary. Equatable is sufficient to provide Set functionality, Hashable is just for performance
>> 
>> I'm not aware of any algorithms that can't be built on top of the existing set methods that would require the same hash value the element used for binning.
>> 
>> I was initially thinking that you could compare the Hashable to determine equality, but I agree that there is a potential for the closure to convert to a narrower type.
>> 
>> A much stronger solution would change the interface slightly to require Element to be `Equatable`, and provide `Element -> Int` as the closure. It's slightly less flexibly, but I do agree that a narrowing makes Equatability of s1 == s2 ambiguous.
>> 
>> In summary:
>> 
>> - struct Set<Element: Hashable> {
>> - struct Set<Element: Equatable> {
>>     ...
>> -   public init() { ... }
>> +   public init(hashValueForElement: Element -> Int) {
>>       ... 
>>     }
>> -   public init(minimumCapacity: Int) { ... }
>> +   public init<H: Hashable>(minimumCapacity: Int, hashValueForElement: Element -> Int) {
>>       ... 
>>     }
>>     ... (same for other public initialisers)
>> +   public func hashValueForElement(element: Element) -> Int { ... }
>>   }
>> 
>> + extension Set where Element: Hashable {
>> +   public init() { ... }
>> +   public init(minimumCapacity: Int) { ... }
>> + }
>> 
>> -
>> Andrew Bennett
>> 
>> 
>> On Fri, Feb 19, 2016 at 7:14 PM, Dmitri Gribenko <gribozavr at gmail.com <>> wrote:
>> On Fri, Feb 19, 2016 at 2:06 AM, Andrew Bennett via swift-evolution
>> <swift-evolution at swift.org <>> wrote:
>> > Wrapper Solution?
>> >
>> > I've had a go at a wrapper solution before and it seems to either need a
>> > unique type per sort, or a block stored per element (unstable).
>> >
>> > Similar overheads were discussed when an index needs to store a reference to
>> > the parent. There's some work to fix it that makes indices moveable, so
>> > instead of going index.successor() you use collection.next(index).
>> >
>> > https://github.com/apple/swift/blob/master/test/Prototypes/CollectionsMoveIndices.swift <https://github.com/apple/swift/blob/master/test/Prototypes/CollectionsMoveIndices.swift>
>> >
>> > Potential solution:
>> >
>> > The collection interfaces could change like this:
>> >
>> > - struct Set<Element: Hashable> {
>> > - struct Set<Element> {
>> >     ...
>> > -   public init() { ... }
>> > +   public init<H: Hashable>(elementHasher: Element -> H) {
>> >       ...
>> >     }
>> 
>> How do you compare such sets?  That is, what does s1 == s2 mean, if
>> the two sets are constructed with a hashing closure?  We can't even
>> compare closures to find that they are the same.
>> 
>> Also, how would this affect algorithms on sets?  When handling a set,
>> you essentially wouldn't know the rules according to which it
>> operates, unless we expose this mapping function.
>> 
>> Dmitri
>> 
>> --
>> main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
>> (j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr at gmail.com <>>*/
>> 
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org <>
>> https://lists.swift.org/mailman/listinfo/swift-evolution <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/ca1d523b/attachment.html>


More information about the swift-evolution mailing list