[swift-evolution] Custom equality/hash for Sets

[Maximilian Hünenberger]

Discussions on different index handling should belong to another thread if there isn't one already.

Your proposed Set change covers at least the custom Hashable behavior.
What about Equatable? I think it could be expressed as behaviors.

- 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/3796cb02/attachment.html>