LazyCollection behavior when indexing directly via subscript

I received a great question over email that I want to answer publicly via gist:

At the end [of the Grokking Lazy Sequences and Collections talk], someone asked you if they can just access a lazy collection randomly and it will not run the transform (map for example) on every element in the collection up to the one they chose.

You said that is correct, but I think that it only applies if the Collection is a RandomAccessCollection? Otherwise, access is not random and is sequential instead, so the iterator’s next() method will be called on each element up to the one requested, and that transform will be executed on each one.

Actually, my response is correct! Confusingly, Collection does support subscript random access (with an expected O(1) runtime in fact) if you have an index. RandomAccessCollection conformance implies that you can compute the distance between indicies in O(1) time (aka moving an index is fast).

If you do happen to have an index for a lazy collection (even a non-RandomAccessCollection) you can index into it without calling next() over and over again (this is in contrast to Sequence where that would be expected), so you only need to invoke one transform on a LazyCollection.

Proof: http://swift.sandbox.bluemix.net/#/repl/58c4f4c1579d675918b224f5

Attached:

import Foundation

struct SomeCollection<T>: Collection {
    private let xs: Array<T>

    init(_ xs: Array<T>) {
        self.xs = xs
    }

    var startIndex: Int {
        return 0
    }

    var endIndex: Int {
        return xs.count
    }

    func index(after i: Int) -> Int {
        return i + 1
    }

    subscript(i: Int) -> T {
        return xs[i]
    }
}

let c: SomeCollection<Int> = SomeCollection([1, 2, 3, 4, 5, 6])
print(c.lazy.map{ x in print("hello"); return x + 1 }[4])

bkase/lazycollection-indexing-behavior.md