[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