Why Collections requires 'index(after...' method with Strideable Index Type

Hello. I have next code.

struct Forum {
    
    /// Just Integer maps to Strideble
    struct Myindex: Strideable {
        var position: Int
        public func advanced(by n: Int) -> Myindex {
            return Myindex(position: position + n)
        }
        public func distance(to other: Myindex) -> Int {
            return position - other.position
        }
    }
    
    struct One: Collection { // Type 'Forum.One' does not conform to protocol 'Collection'
  
        var storage = ["1", "2", "3"]

        // Collection
        subscript(position: Myindex) -> String { return storage[position.position] }
        var startIndex: Myindex { return Myindex(position: 0) }
        var endIndex: Myindex { return Myindex(position: 2) }
    }
    
    struct Two: RandomAccessCollection { // Fine

        var storage = ["1", "2", "3"]
        
        // RandomAccessCollection
        subscript(position: Myindex) -> String { return storage[position.position] }
        var startIndex: Myindex { return Myindex(position: 0) }
        var endIndex: Myindex { return Myindex(position: 2) }
    }
    
}

And compiler does not allows to conform struct One to Collection. But it allows to conform struct Two to RandomAccessCollection. Why more simple protocol Collection can not use advantage of Strideable Index Type as RandomAccessCollection for construct default implementation func index(after i: Forum.Myindex) -> Forum.Myindex method?

The semantics of RandomAccessCollection guarantee that the distance between adjacent indices is exactly 1. That guarantee allows it to provide a default method which merely increments the index.

Collection allows adjacent indices to be arbitrarily far apart internally. LazyFilterCollection is one such example. Since it cannot guarantee that an incrementation of the separate index type will actually produce an index that is valid in the collection, there is no viable default method.

1 Like

Thank you. Generic Type Alias... I see it at first.

This is not correct. RandomAccessCollection does not mandate these semantics.

However, if your index does happen to be strideable with an Int stride, and you declare you are random access, you will get a default implementation that works as you describe. But if that isn't what you want (and it isn't always), you need to implement index(after:) and friends yourself.

1 Like

Or rather, it depends what you mean when you say "distance". The "distance" between two elements in any collection, not just random access collections, is one, if you define distance to mean "how many elements after". But if you define distance as "the representation of location in the collection", whether or not that representation is transparent (i.e. it just uses an Int) or opaque, then it isn't a requirement that the difference between them be 1.

1 Like

What difference between opaque and transparent indices? Can index be more abstract than representation of an item?

Okay, aiming for higher technical precision this time (:crossed_fingers:):

[I]n order to meet the complexity guarantees of a random-access collection, either the index for your custom type must conform to the Strideable protocol or you must implement the index(_:offsetBy:) and distance(from:to:) methods with O(1) efficiency.

Yes, you could technically implement a collection whose indices are even Ints and still provide O(1) offsetting by multiplying the distance by 2. But the practical usefulness of any such scheme that is O(1) but has non‐contiguous transparent indices is so low that the standard library is willing to assume no one will ever do it and provides a default implementation that only works when the assumption holds.

On the other hand, when abandoning the O(1) requirement, there are many uses for transparent, non‐contiguous indices, even in the standard library. As an example, [1, 2, 3, 5, 8, 13].lazy.filter({ $0.isMultiple(of: 2) }) yields a collection with the indices 1 and 4 (which point at 2 and 8 respectively). Asking that collection for the index after 1 needs to get an answer of 4. If the default returned 2, that would be a problem. Hence no default implementation exists for plain Collections.

Is that more accurate?

If not, then the original poster’s question is a good one and still unanswered. Why is RandomAccessCollection able to have a default implementation, but Collection isn’t?

I have another question about String Indices. I have the next code.

func checkIndex() {
    let z = [1, 2, 3, 4]
    let index = z.index(z.startIndex, offsetBy: 60)
    print("index: \(index)")
}

func checkStringIndex() {
    let z = "One,Two,Three,Four"
    let index = z.index(z.startIndex, offsetBy: 60)
    print("index: \(index)")
}

The first function works and prints

index: 60

But second function does not work. And I get an error.

Fatal error: String index is out of bounds
Illegal instruction: 4

What did I miss? Why it does not allow me to get wrong Index from String?

Because Strings are not Array. Strings have more constraints.

https://developer.apple.com/documentation/swift/string/1786175-index

The value passed as n must not offset i beyond the bounds of the collection.

1 Like