Should Dictionary support first related methods from Collection conformance?

This is more or less exactly what I have said:

I never said we should abolish protocols that exist to guarantee performance, I just think it's odd that at the same time we have no such restrictions for types where certain operations simply don't make sense.

It is "forbidden" to get the predecessor in a list, but it's ok to reverse a Sequence that has no end
¯_(ツ)_/¯

You can’t forbid writing bugs; you can only hope to make them harder to write. I guess. And some kinds of bugs were deemed more important than others, I also guess.

That's great! I'm not as unhappy with the status quo as it might have seemed, though ;-)
Especially, I found the link to https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md to be quite useful, as it shows a simple remedy for awkward repetition like someStringWithAQuiteLongName[someStringWithAQuiteLongName.index(after: someStringWithAQuiteLongName.firstIndex(of: ".")!)]

I just wanted to express that I understand the motivation to disallow certain operations, and it seems that we share some concerns regarding Sequence:

That's true indeed. Ultimately, I think this isn't about infinity at all, but rather about "is it too large to fit in a computer", and this question has no clear answer.
Without the suffix-methods, it would be much less controversial that a Sequence can have no end.

Luckily, I didn't claim to have a plan to resolve that one ;-) - but maybe the introduction of move-only types could be a opportunity to "fix" Sequence?

No, I personally don't want Array.binarySearch ;-) - and I'm pretty sure that I don't need it, because it hasn't been there the last years.
I think it also wouldn't be consistent to allow arrayThatIsntSortedAtAll.binarySearch(element) despite the fact how unhappy many people are that they can't do stringThatsReallyOnlyBoringASCII[5] ;-).

But I better stay out of this discussion, as I found someone who is way more qualified than me:

(-: just joking here - that message starts with the disclaimer that it's posted on behalf of others)

So… if I write a generic algorithm that takes only a single pass over an input sequence, I shouldn't be able to use that on an Array?

extension Sequence where Element == Int {
    /// Returns the sum of the elements
    func sum() -> Int  { ... }
}

print([1, 2, 3].sum()) // illegal?

All algorithms that can operate on a single-pass Sequence work equally well when given a multipass Collection. If you want to avoid a refinement relationship between these two protocols, yes, you could drop Sequence and just write the single-pass algorithms as mutating methods on Iterator. But with the current language features, it would be impossibly baroque to use those algorithms in the vast majority of cases where you do in fact have a Collection:

print(a.sum())                // error: value of type '[Int]' has no member 'sum'

print(a.makeIterator().sum()) // error: cannot use mutating member on immutable value: 'makeIterator' returns immutable value

var i = a.makeIterator()
print(i.sum())                // OK

In this world, you can forget about ever writing something like:

a.map { ... }.filter { ... }.reduce(3) { ... }

If you still don't believe me, you actually have all the tools you need at your disposal to explore what your library design could look like, using the current language features. I'd be more than happy to be proven wrong.

This has nothing to do with the index increment change, it's a performance optimization. If it weren't there, calling a generic Collection method like dropFirst(n) on a RandomAccessCollection would take O(n) time instead of O(1) time. It would have equally been an issue with the old model, and if we were still using it now, I would guess that Collection would have had an advanced(by:) requirement on its indices even if it didn't in Swift 2 (I don't know if it did or not)

Any algorithm that uses first can be rewritten in terms of iterators in general, because first itself can be rewritten in terms of iterators:

var first: Element? {
    var iter = makeIterator()
    return iter.next()
}

By that logic we should just get rid of first, it's clearly useless

first and dropFirst are clearly useful and desirable on collections that have a semantic ordering, like arrays. The question was whether they are necessary on collections in general, particularly dictionaries but by implication also sets.

Brent was effectively arguing that they are necessary, or at least useful, since they allow generic iterator-like code like his example. I am suggesting that they are not, since iterators exist.

If it was easy to use iterators, you could just have people use them instead of first for their arrays. It's not, iterators are a pain to use due to their use of mutating methods.
Why would the fact that order is meaningless suddenly make iterators easier to use?

I'm not sure I understand everything you're saying here, but I stand by everything I wrote. Before the change, indices of RandomAccessCollection were Strideable, which meant i += 5 was legal syntax for an Index i of a RandomAccessCollection, but was not legal for an Index of an arbitrary BidirectionalCollection. That distinction was lost when we made the change because the only requirement on any Index type became conformance Comparable.

Also, I think you misunderstood me; I was not suggesting that removing index(:offsetBy:) from Collection would be the only change required; there are a whole bunch of knock-on changes we'd have to make. Among those, dropFirst(n) would have to become a protocol requirement of Collection so it could be implemented as O(1) for RandomAccessCollection.

I'm glad you reminded me of this, actually, because now I remember that when we analyzed going in this direction we explicitly decided it was better to give up the syntactic distinctions between BidirectionalCollection and RandomAccessCollection, than to accept the increased number of protocol requirements and consequent complexity of implementing a new collection type.

Point being, design in this area is hard, and full of complex tradeoffs that have to be discovered through experience. I won't claim it can't be done better than we did it, but I would bet that any unimplemented, untested idea posted to a forum after even a few weeks' thought has much more serious problems. You need to put all the pieces together, get them to compile, discover the way they interact, and actually use them in real code before you can see whether any library design works.

1 Like