[swift-evolution] Custom equality/hash for Sets

Maximilian H├╝nenberger m.huenenberger at me.com
Fri Feb 19 07:54:06 CST 2016


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>


More information about the swift-evolution mailing list