[swift-evolution] [Proposal Draft] Provide Custom Collections for Dictionary Keys and Values

[Alexis]

Just to clarify: It seems like the only ABI-affecting change here is the type of keys/values. As you note at the end of your proposal, this should just be Dictionary.Keys/Dictionary.Values regardless of whether we implement this proposal or not, in which case this can be punted for Swift 4. It should be fine to keep .Keys/.Values resilient so that we can change their implementation details later if we want.

On the actual proposal: this is a pretty reasonable given Swift’s current design and constraints. That said, I expect pushing forward on this kind of thing right now is premature given the goals of Swift 4. A major aspect of Swift 4 is reworking the way CoW semantics function internally, which could drastically affect the way we approach this problem.

I’d really like if we could eliminate the “double search/hash” in the no-existing-key case. There are ways to do this really cleanly, but they probably involve more advanced CoW-safety propagation. In particular, you want some way for the collection to return its search state to the caller so that they can hand it back to insertion to just resume from there.

For instance:

map.entries[key]           // An enum like Found(Value) | NotFound(SearchState)
   .withDefault(value: []) // Unwrap the enum by completing the NotFound(SearchState)
   .append(1)              // Now we have a value in both cases, we can append!



Or more complex:

map.entries[key] 
   .withDefault { /* logic that computes value */ }
   .append(1)

I think this can be made to work in the current system if withDefault is actually `[withDefault:]`, which is fine but a bit weird from a user’s perspective.

In an ideal world the user could actually pattern match on the result of `entries[key]`. In this way they could match on it and perform special logic in both cases for really complex situations. This would make withDefault “just a convenience”, so we aren’t pressured to add more methods like it every time someone has a new Even More Complex use-case. e.g.:

switch map.entries[key] {
case .Found(entry):
  if entry.value == 10 { 
    entry.remove()
    print(“Found a value too many times! Moving key to fast-path auxiliary structure…”) 
  } else {
    entry.value += 1
  }
case .NotFound(entry):
  entry.insert(1)
  print(“Found a value for the first time! Registering a bunch of extra stuff…”) 
}


But again, this is all dependent on a much more powerful SIL/ARC, and we just don’t know what we’re going to get at this stage.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20161012/a209a100/attachment.html>