[swift-evolution] Custom equality/hash for Sets

[Andrew Bennett]

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