In practice it has turned out that every one of our concrete collection's non random-access indices holds a reference to the collection it traverses. This introduces complexity in implementations (especially as we try to avoid multiple-reference effects that can cause unnecessary COW copies – see Dictionary and Set) and presumably translates into less-efficient codegen. We should consider other schemes.
There are index-less schemes (c.f. D), but we should also consider a scheme where generic indices can't be moved without participation from the collection itself, e.g. collection.nextPosition(index). This would complicate generic code a bit, but working with Array would remain as simple as ever. We could even consider whether random access is special and RandomAccessIndex ought to be incrementable without a collection, although that may give up some error checking opportunities.