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

[Dave Abrahams]

on Wed Oct 12 2016, Alexis <swift-evolution at swift.org> wrote:

> 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. 

No, it can't, in the sense that just making them typealiases would be
insufficient to create resilience.

> 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.

IMO this should be written as follows:

  map[key, default: []].append(1)

> 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.

This compiles today:

  extension Dictionary {
    subscript(k: Key, body: (inout Value?)->()) -> Void {
      get {
        // Exercise for the reader.  Efficient and safe implementation only
        // possible inside the stdlib.
      }
    }
  }

  map[key] { v in 
    if let found = v { 
      if found == 10 { v = nil; print("Found too many") }
      else { v = found + 1 }
    }
    else {
      v = 1
      print("Found first")
    }
  }

No need, really, to use subscript; it could be spelled:

  map.withValue(forKey: key) { ... }

ersump'n.

-- 
-Dave