Should Dictionary support first related methods from Collection conformance?

[dabrahams (Dave Abrahams)]

@Tino

Probably there are some odd things that actually have a really good explanation, but for a design which predates Evolution, there is no place to look for such justifications.

I'll try to present some of those justifications here, then. The collection hierarchy is by no means perfect, but I don't think it's as bad as you say. Hopefully this will provide some perspective:

Let me start by saying that it seems from your post that you and I judge the appropriateness of protocols by very different criteria. My criteria are based on the lessons learned by Alexander Stepanov and his collaborators in their work on generic programming, the discipline that protocols were designed to serve. I'm sorry if that sounds pompous; I only mention it because I want you to understand that the choices are not arbitrary, but are based on existing practice, solid experience, and a coherent set of principles.

@Tino

My general impression is that the hierarchy cares much more for (I'd say premature) optimization issues than for code that actually makes sense: We have BidirectionalCollection , which afaics is just about efficiency,

The ability to use a library, and especially to compose its parts, and reason about the efficiency of the composite is a fundamental feature of generic programming. I consider basing protocol distinctions on efficiency to be legitimate and often desirable. It's not uncommon that the choice of an algorithm's best implementation depends on the protocols to which its operands conform (see rotate for example).

Usually we try to combine efficiency distinctions with syntactic differences in the set of basis operations, by having requirements that only apply to the more efficient protocol. This practice helps with usability and qualitatively, tends to makes protocol differences based on efficiency “feel” more substantial.
That said, in the move from standalone incrementable indices to indices moved by collection methods, the differences in basis operations between BidirectionalCollection and RandomAccessCollection was lost. That's arguably a flaw; to avoid it we would have had to remove the index(:offsetBy:) algorithm from Collection and only make it available to RandomAccessCollection.

but we have no notion of fundamental concepts like finite vs. infinite, single- vs multi-pass -
and while all collections have (at least an implicit) order, there's still nothing like SortedCollection .
So I can write an generic function that can avoid some theoretical* complexity pitfalls, but for doing a binary search, I have to either roll my own protocol - or introduce another bunch of issues similar to Set.reverse , Dictionary.elementsEqual or infiniteSequence.shuffled .

OK, there's a lot here, so I'll take one thing at a time:

1. I disagree with the premise that finite vs. infinite is a fundamental concept that should be represented in the type system, because there exist finite collections that are, for all practical purposes, infinite. Take for example the finite collection 0...Int64.max: there is almost no operation you'd want to statically disallow for an infinite collection but that should be used on this value of Range<Int64>.

2. Single- vs multi-pass is captured: that's the distinction between Sequence and Collection. As I noted in the posting you referenced, the notion of single-pass is not really well-representable in a language without move-only types, and that accounts for some weaknesses in the current design, but we did make the single-vs-multipass distinction as best the language allowed.

3. SortedCollection is not needed for binary search. In fact, you want a binary search that doesn't require sortedness to be represented in the type system, because it should be possible to binary search in an Array after it has been sorted. That is, sortedness should be a precondition on the operand of the algorithm. In fact, here's a little gift for you. If you're interested in the background behind the naming choice you can read this and this. There may be a use for a SortedCollection protocol, but so far I haven't found one that justifies its conceptual weight.

* Yes, getting the predecessor in a (singly) linked list is somewhat stupid, and accessing the last element is expensive... but at the same time, Collection already inherits dropLast and suffix ; and we don't even have neither singly nor doubly linked list in the stdlib (do we? ;-).

I'm not sure what you're arguing for here, but I consider the fact that dropLast and suffix are exposed on Collection to be design bugs caused by the fact that Collection refines Sequence (which is flawed). So I wouldn't want to use that fact to justify any new design decisions.

I hope this perspective helps a bit.

Regards,
Dave