Let Optional, Dictionary and Array conditionally conform to Hashable

Evolution Pitches
22

Sets have conformed to Hashable since they were introduced in Swift. The set's elements' hash values are combined using ^, which is commutative, so the same hash value is produced no matter the order.

1 Like
23

Yes, but ^ is a poor hash function (see ongoing discussion about combining hash functions). I think it would be better not to use that.

24

I don't see what is wrong with using xor to combine hash values in these cases, assuming the underlying hash function for elements is reasonably good. The arguments against using xor to combine are usually:

  1. It is order independent;
  2. If there are two identical values then the result is 0.

In these cases, i.e. unordered Set and Dictionary, 1. is desirable as the order of elements is undefined, and 2. is not an issue because sets and dictionaries cannot contain identical elements (where the element of a dictionary is a key-value pair).

6 Likes
25

Pretty neat side effect? :D

let test : [String? : String] = [nil : "hello"]
print("\(test[nil]!) world")
1 Like
26

Hi all,
In the current WIP implementation I think that I have gathered all suggestions from reviewers so far.
Thank you all for taking your time to review!
Can anyone advise on the next step from here?
(Cross-posted on the WIP PR.)

27

Thank you for implementing this!

I think it would be useful to find all stdlib types that could benefit from conditional Hashable conformance. (I listed some of these types above, but I could have missed some.) Do you have time to add additional implementations?

In any case, I believe it's time to start drafting a proposal. :tada:

1 Like
28

Is a proposal necessary? I do believe it should be covered under SE-0143 itself.

29

Yes, you’re right! This work is covered by SE-0143 already.

30

@Morten_Bek_Ditlevsen's WIP PR now includes additional implementations, including conditional conformances for Slice, based on elementwise processing.

The question is, of course, are we happy with this implementation? As @xwu correctly points out in review, it clearly violates the "equality implies substitutability" requirement. (Although for collection-related types, this requirement admittedly seems more like a polite suggestion, even in the stdlib.)

  • Is there a better way to define equality on a generic Slice? For example, what if we compared indices instead (with or without also comparing the base collection)? This also leads to a useful definition of equality, but it doesn't seem safe to do in general -- comparing indices coming from different collection instances is generally unwise.)
  • If there is no better way, is it better to have Slice not conform to Equatable/Hashable?

I worry that if we don't add these conformances, people would end up trying to implement them outside the stdlib.

31

I worry that if we don’t add these conformances, people would end up trying to implement them outside the stdlib.

Yeah in my opinion this is a must-have for Swift 4.1.

32

I think you're missing the gist of @lorentey's post. This is not a question about whether Optional, Dictionary, or Array should have conditional conformance to Hashable, which will be implemented shortly.

We're trying to start a discussion about the desired semantics for Slice types, specifically, to conditionally conform to Hashable, or whether that is a good idea at all in the absence of consensus on semantics.

1 Like
33

I didn't miss it, I was just agreeing with that point (that those types are a good idea for sure) :)

34

...with what semantics?

35

Before implementing conditional Hashable and Equatable conformance in the WIP PR, I had not dealt very much with the Slice type.

The current implementation in the WIP PR considers two slices to be equal if all of their elements are equal.

After thinking about what 'identity' would mean for the Slice type (and other types that are essentially 'views' into another structure), I am not certain that 'equal elements' are actually what I would expect.

With equality meaning 'the elements visible through the view are the same', you can naturally have two different slices into two different collections being equal.

But these different slices would have different public properties: startIndex, endIndex and base.
I think that I would expect these properties to be equal on two slices that are equal - not just the elements.

At the very least, the fact that these properties can be different on two slices that compare equal could easily confuse the consumer of the API.

A (very contrived) example is:
I have an index, z into a slice a. a compares equal to slice b.
In that case I would probably assume that I could use z as an index for b too.

Implementing equality to mean that startIndex, endIndex and base are equal would in my opinion cause less of a surprise.

If the consumer then wishes to test for element equality instead, then that is easy to express in code by using elementsEqual.

Just my 2 cents. :-)

1 Like
36

I agree this would be a useful feature of equality. My problem is that the stdlib is full of types that already violate this expectation -- off the top of my head, Set, String, Substring, all the substring views, and String.Index are examples where equality does not imply substitutability in this way. Equal values often have major observable differences -- basic properties return different values, equal indices aren't interchangeable, etc.

The stdlib evidently doesn't consider startIndex & endIndex (and basically anything related to indices) as obstacles of equality for collections. If anything, the rule seems to be that collections are generally compared by their contents:

let s1: Set<Int> = [23, 42]
var s2 = s1
s2.reserveCapacity(1000)
print(s1 == s2) // => true
print(s1.startIndex == s2.startIndex) // => false
print(s1.endIndex == s2.endIndex) // => false

let foobar = "foobarfoo" // No need for Unicode shenanigans
let foo1 = foobar.prefix(3)
let foo2 = foobar.suffix(3)
print(foo1 == foo2) // => true
print(foo1.startIndex == foo2.startIndex) // => false
print(foo1.endIndex == foo2.endIndex) // => false

I feel uneasy to draw the line at Slice; I agree there is a problem here, but I suspect it might be that Equatable's requirements are not well defined.

3 Likes
37

Here is another way to look at this: if we could add conditional conformances to protocols, would we have Collection implement Equatable when Element does?

extension Collection: Equatable where Element: Equatable { // (Not valid Swift)
  public static func ==(left: Self, right: Self) -> Bool {
    return left.count == right.count && left.elementsEqual(right)
  }
}
2 Likes
38

I think not; that seems to confuse == with elementsEqual, or in other words, make elementsEqual strictly redundant.

39

Indeed, but I don't think API redundancy is the issue; plus, elementsEqual(by:) would still be useful.

I think the real problem with that definition is that it gives incorrect results for unordered Collections.

On the other hand, I believe that Slice is, by its nature, an ordered collection, even when its base collection happens to be unordered. The index range that defines the slice imposes a strict ordering over its elements. (In fact, this is a general issue with the SubSequence associated type and its associated methods on Collection; they only really make sense for ordered collections. As soon as I call set.dropFirst(), I freeze the set into an ordered collection, practically indistinguishable from Array(set).dropFirst().)

I'd argue that

  1. The stdlib's all existing equatable collection types provide clearly established precedent for basing the equality of collection values on the equality of their contents,
  2. elementsEqual is The Obviously Correct Way to compare the contents of ordered collections for equality,
  3. Slice and ArraySlice are ordered collections,

therefore Slice and ArraySlice should also conditionally conform to Equatable with a definition that compares their contents using elementsEqual.

40

Hmm, I disagree. The existence of elementsEqual(_:) can only be justified if it is intentionally the case that equality of elements is not necessarily equality of the Collection type. And, since the design of Collection has ordered semantics and makes no explicit accommodations for unordered types, the existence of elementsEqual(_:) demonstrates to me that we make no assumption that such a relation holds in the general case for ordered Collections.

Put another way, it's fine to say that such is the case for concrete types such as String--even custom slice types such as Substring--but I would not favor your proposed Collection : Equatable where Element : Equatable semantics even if we did not have unordered Collection types. By the same token, I think that arbitrary Slices of arbitrary Collections should not have those semantics either, because although it is technically a concrete type, it's like AnyHashable in that there's a flavor of type erasure involved.

41

Actually, elementsEqual is generic and lets you compare *any* two sequences with the same Element type:

let str = "hi"
let arr: [Character] = ["h", "i"]
arr.elementsEqual(str)  // true
1 Like