[swift-evolution] [RFC] New collections model: collections advance indices

[Károly Lőrentey]

On 2016-03-08 11:46:18 +0000, Pyry Jahkola via swift-evolution said:

> On 08 Mar 2016, at 03:25, Dmitri Gribenko via swift-evolution 
> <swift-evolution at swift.org> wrote:
> What does everyone think about requiring indices to conform to
> Hashable, in addition to the existing requirements for Equatable and
> Comparable?
> 
> Why impose such a restriction?
> 
> I think it's better to just make any concrete index types (e.g. 
> DictionaryIndex<K,V>) in the standard library Hashable where possible. 
> People are still free to constrain their algorithms to `C : 
> CollectionType where C.Index : Hashable` whenever needed.

I agree with Pyry. I haven't come across an index that couldn't
easily conform to Hashable, but I'd find it annoying to be forced
to write & test a hashValue property whenever I create a new
index for private use in my own app. Hashable indices should perhaps
be a recommendation for reusable collections, rather than a hard
requirement.

> Besides, in the proposed design, is it really necessary to make Index 
> also Comparable, or wouldn't Equatable be enough? Is it just a question 
> of convenience and failing to find an example of and index type that's 
> Equatable but not Comparable?

Having to implement Comparable indices on tree-based collections
does put constraints on the underlying tree structure: e.g., they'll
need to be augmented with subtree counts for O(1) comparisons. But
order statistic trees are a good idea anyway, and I find implementing
`<` far less odious a requirement than `hashValue`. (More
straightforward to write, far easier to test.)

-- 
Károly