[swift-evolution] Custom equality/hash for Sets

[Andrew Bennett]

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.


> 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.

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:

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.


> - 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
>> >
>> > 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160219/ad775b89/attachment.html>