on Wed Jul 06 2016, Brent Royal-Gordon <brent-AT-architechies.com> wrote:
>> On Jul 5, 2016, at 7:39 PM, Dave Abrahams via swift-evolution >> <[email protected]> wrote: >> >> Anyway, the thoughts of the community on this topic would be interesting >> to us. We need to make a decision about this very soon. > > I've wanted the Index protocols to be Comparable since the Swift 1 > days. (Apple people, see rdar://17768142; non-Apple people, I was > looking to measure distance and, under the old indexing model, the > inability to determine which index came later was one of several > impediments.) > > Going back to the beginning: > >> For example, with >> Comparable indices, you can't build a linked list that supports >> restructuring (e.g. insert, delete, splice) in O(1) without invalidating >> indices... not even an unsafe linked list with reference semantics. >> [While I don't think linked lists are terribly good data structures for >> most things, they are still useful in teaching, and it bothered me that >> we were ruling them out.] Even if you take away the index invalidation >> restriction, you have to store a counter in the index, which is an awkward >> inefficiency. > > You *can* have O(1) restructuring without index invalidation if you're > willing to tolerate O(n) comparisons; you just walk forward from the > left-hand side and return `true` if you encounter the right-hand side > before reaching the end. Yeah, but O(1) is a basic requirement of Comparable. I consider that to be inviolable. > I'm not certain, but I think there's a three-way tradeoff here: you > can have any two of fast restructuring, fast comparisons, and > always-valid indices. > > In general, though, `Collection` is not very good at modeling linked > lists—for one thing, it can't model a value-typed linked list without > enormous index invalidation issues. I can't quite bring myself to > worry too much about linked-list handling here. Yes, I'm not too worried about it either. I'm more concerned about trees, FWIW. >> * A Range<T>, where T is not Comparable, could be constructed with any >> pair of Equatable T instances. We'd only detect that the Range may be >> invalid when T happened to also be Comparable. However, the fact that >> you are creating a Range already sort of implies an underlying >> ordering. > > Such a Range can't actually test whether a given value is *in* the > range. That basically just makes it a glorified typealias for > `(lowerBound: Bound, upperBound: Bound)`. Yes. > A Range without Comparable is a type without any semantics. Practically speaking, yes. >> * A Collection with non-Comparable indices still imposes an ordering >> upon the indices. > > And it also still needs to be able to *test* the ordering of > indices. For instance, `distance(from:to:)` is a bit difficult to > implement (at least in `BidirectionalCollection`) if you can't tell > which index comes earlier in the collection. Well, you can make it a precondition that the indices are in order. That's what Swift 2 did (and what C++ does with its forward and bidirectional iterators). It is certainly nice that Swift 3 lifts that restriction. -- Dave _______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
