Reviews are an important part of the Swift evolution process. All review feedback should be either on this forum thread or, if you would like to keep your feedback private, directly to me as the review manager. When contacting the review manager directly, please put "SE-0514" at the start of the subject line.
What goes into a review?
The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:
What is your evaluation of the proposal?
Is the problem being addressed significant enough to warrant a change to Swift?
Does this proposal fit well with the feel and direction of Swift?
If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
How much effort did you put into your review? A glance, a quick reading, or an in-depth study?
More information about the Swift evolution process is available at:
The problem is arguably minor, but the change is also minor, and both the problem and the change are examples of a larger class of problem (assorted missing conformances in the stdlib in general) that I think we should attempt to tackle. Starting at the shallow end of the space seems wise.
Yes.
Quick reading of this specific proposal, but in-depth study of this area.
This proposal has Swift 6.3 in the examples. Isn't it far too late for that, given we've started the 6.3 beta process for full release in maybe a month? Should the examples be bumped to 6.4?
Dictionary.Keys gains unconditional Hashable conformance. Since dictionary keys are always Hashable (as required by Dictionary's type constraints), the keys view is always hashable. The hash implementation uses a commutative hashing algorithm (XOR of individual element hashes) to ensure that two Dictionary.Keys collections hash to the same value if they contain the same elements regardless of iteration order.
Is there anything here we need to keep in mind about bridging NSDictionary to Swift.Dictionary? The allKeys property on NSDictionary is not typed to Hashable:
A Dictionary.Keys, by virtue of the elements being unique, is effectively a Set, so the implementation for that is straightforward. Dictionary.Values with Hashable elements, on the other hand, doesn't require uniqueness but the order still doesn't matter, making it more like a multiset. If we already had a multiset type in the standard library we could probably use that as precedent, but we don't, and adding the conformances to Dictionary.Values would effectively be backdooring one in through that type in a super awkward way. That doesn't feel ideal to me.
I updated the proposal to use 6.4, but as a general rule any availability that appears in a proposal should be understood as a placeholder for “the release that this lands in”, since we don’t generally know what that release will be at the time that a proposal is running.
Without Dictionary.Values conforming to Hashable, we’re effectively forced to convert values into Array-like collections whenever hashing is required. In performance-sensitive contexts, this conversion can introduce significant overhead.
The standard library doesn’t aim to completely prevent all forms of misuse, and I don’t think it should in this case either. Also I see no problem to use e.g. [String: Int] | dict[key: key, default: 0] += 1 to imitate multiSet, especially given that the standard library currently provides no dedicated alternative.
By not making Dictionary.Values hashable, we’re not really preventing incorrect usage – we’re primarily nudging users toward less efficient workarounds. Prohibiting something doesn’t make the underlying problem go away.
Do you have an example where hashing of a dictionary’s values is required? But not its keys? I’ve hashed Sets, but it’s rare to hash dictionaries, let alone just their values.
EDIT: I also can’t think of an efficient implementation for Equatable on Dictionary.Values that doesn’t involve actually constructing the multiset. I suppose that’s still O(n), but it doesn’t feel like a natural behavior of the type. Whereas Dictionary.Keys is basically a Set already.
Yes, in diffable datasource sometimes where a list of elements is shown horizontally in a vertical list. Its not needed be strictly Hashable but it is needed to be equatable.
Also:
state management diffing and invalidation
when writing tests
comparing data, e.g. previous and current value or reactiveStream.removeDuplicates
Aren't Dictionary and its views already a bad data structure for this sort of thing because they don't guarantee iteration order, and presumably you'd want to display the elements in a well-defined order?
Dictionary is not bad or not bad. Sometimes it is not possible to rewrite the whole Data layer in a legacy codebase, where data is already stored in dictionaries.
And often Dictionaries of all kinds are exactly suitable collection, including Swift.Dictionary.
There are also generic algorithms over Collection where I definitely don't want to convert Dictionary.Values to Array to just make equality comparison.
Indeed, when you remove the qualifier from the sentence you quoted, it changes the meaning, but that's not what I was arguing. The use case you originally cited was one that seemed to rely on ordering of the elements, so the full question was "is Dictionary bad/unsuitable for that use case"? And the answer to that is yes, unequivocally.
Converting it directly to Array would already be incorrect (if you mean in the sense of Array(someDictionaryValues)), because it's again forcing a specific but arbitrary order on the elements. Given two Dictionary.Valuesa and b with the same elements and the same count for each element, Array(a) may not equal Array(b). To compute the actual multiset equality, you'd need to actually compute the element -> count mappings of each one (what Jordan was saying above), which either (1) implies that the elements must also be Hashable—not simply Equatable—if you want construction of that mapping to be efficient, or (2) will be time- and space-inefficient.
If you want Dictionary.Values: Equatable where Element: Equatable with no other constraints, I think that would require quadratic time and linear space in the worst case. If you wanted Dictionary.Values: Equatable where Element: Hashable, I think that gets you down to linear for both. But I'm not aware of any other standard library data structures that have non-constant space requirements to implement equality, and that's probably a good reason that we shouldn't add it by default to this peculiar view type.
(By contrast, a true multiset type that already represented itself as an element -> count mapping would have O(1) space requirements for equality, which is a lot more sensible.)
It was not about the ordering, it was about fast access with O(1) while having an ability to detect changes via Equatable.
I will be very glad to have a MultiSet in standard library. Despite that, MultiSet doesn't replace dictionary in all situations where Equatable Dictionary.Values is useful.
Not really relevant to this thread, but O(1) space for multiset equality checking is trivially attainable even with a terrible data structure, as long as you allow quadratic time:
guard lhs.count == rhs.count else {
return false
}
for x in lhs {
let m = lhs.count(where: {$0 == x})
let n = rhs.count(where: {$0 == x})
if m != n { return false }
}
return true
Obviously not a good idea, but technically possible.
(Well, the time complexity is quadratic in the total number of elements. With respect to the number of distinct elements it is actually unbounded, whereas a good implementation would be linear. The space is still O(1) though.)
Sure, but Swift has also gotten into a bad habit of not actively updating proposals once the release version is known. Swift 6.3 includes a few different changes, but the CHANGELOG isn't updated, Apple's release notes include no Swift changes at all, and the proposals themselves aren't often updated to indicate their release version. For instance, it seems that SE-0491 has shipped as part of 6.3, yet it appears in the CHANGELOG under Swift (new), and there's no indication in the proposal it's actually in 6.3.
So while I recognize the need for flexibility, I would ask that proposals aren't actively misleading, perhaps by using a placeholder version. And I'd ask for a little more effort in keeping the various change records up to date.
NSDictionary.allKeys is [Any] instead of [AnyHashable] since NSDictionary.allKeys is an NSArray, which is imported to Swift as [Any]. Nevertheless, the Hashable constraint on Swift.Dictionary.Key is sufficient to assert that the elements of Swift.Dictionary.keys are all Hashable.