[swift-evolution] [Idea] Add AssociativeCollectionType to represent Dictionary-type relationships (was: Add an (Index, Element) sequence to CollectionType)

[David Waite]

> On Dec 31, 2015, at 9:53 AM, Dave Abrahams <dabrahams at apple.com> wrote:
> 
> What is the use-case for this protocol?

I actually suspect you have a better grasp of the pros and cons based on your prior experience, but here goes:

An AssociativeCollectionType would allow for alternate implementations from Dictionary, which provide space optimization, lookup performance, and functionality, to be used closer to the level of first-class citizenship that Dictionary has. This is similar IMHO to the status of say ArraySlice vs Array.

1. While there is a protocol for implementing your own collection, there is none for implementing your own associative collection. Without such a protocol, interfaces must be written to require Dictionary, and to get things into the Dictionary representation (rather than just exposing an associative interface) will require data copying as well as other probably smaller details like the value be Hashable

2. A single dictionary-like type means that features which may be desirable in an associative collection (preserving insertion order, sorting by key, atomicity guarantees, searching by closest match, computed/default/prototype-fallback value lookup) as well as problem-space optimized algorithms (hash vs tree vs splay vs skip list) would each either need to be features of Dictionary, or be second-class citizens. 

3. People who wish to have arrays behave like dictionaries (and are willing to take the performance hit re: array index out of bounds returning nil instead of raising a fatal error) could get the appropriate interface to do so

4. Array is mostly described (excluding certain mutating operations) by CollectionType. Dictionary on the other hand only really uses CollectionType to allow iteration and to reference items in buckets (I assume). The Raison d'etre of Dictionary as a core type is just not represented via protocols the way Array is


Some of this though is that many CollectionType and SequenceType operations are useful when considering a Dictionary as a sequence in a functional style - but is not the default way I at least think of Dictionaries. For instance, how often will people want to filter a dictionary into a tuple array, vs mutating or forming a new dictionary with predicate-failing entries removed?

As least in my personal experience, the difference in relationship between Array and CollectionType (Array being a type of collection) and Dictionary and CollectionType (dictionaries can be represented by a collection) is a constant source of confusion. 

Some the cons I’ve identified:
- Protocols today do not have generic arguments, making any function declaration wanting to take “any string to string associative collection” vs “[String:String]” be significantly more complex.

- It is more pragmatic and simpler from a type perspective to push code to use a single Array or Dictionary implementation rather than needing to support generic implementations, except when opted into. This is similar to the use of lazy, or the use of Int vs smaller or more specific types.

- Array has additional mutating methods which are not described by CollectionType or any other protocol. The ease of getting a new copy of an array and mutating it means code needing the ability to append (for instance) today will be declared using an explicit Array type. If this was desired to be fixed, it would require more protocols (ModifiableCollectionType?)

- Related to the previous point, there is no way to require value semantics via a protocol. If a ModifiableCollectionType was created today, there would need to be requirements on implementation outside what a protocol can enforce. 

- An array could not implement AssociativeCollectionType directly, because the index value and key would both be Int and there is a subscript property for both, but with different semantics and a different return type. You would need to ‘wrap’ an array to get this effect


And one final thought - It might have make sense for Dictionary to not directly be a CollectionType at all, but rather have a property that exposes the Dictionary as a CollectionType, similar to how I propose a wrapping an Array to make it act like an associative array. If you were to take a cue from Java, this would be an “entries” property on Dictionary (or AssociativeCollectionType)

-DW

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20151231/76910d6b/attachment.html>