Is a set a sequence?

Evolution Discussion
64

I think it's problematic enough if it's likely that someone might write (what they believe to be) a generally useful algorithm on Sequence while forgetting that a Sequence in Swift doesn't have to have a meaningful order.

There is no straight forward way of finding such examples in the wild, but I got one on my first attempt:

I just searched for "accumulated sum swift", and the following implementation turned up (it's the second answer to this Stack Overflow question).

protocol Accumulatable {
    static func +(lhs: Self, rhs: Self) -> Self
}
extension Int : Accumulatable {}

struct AccumulateSequence<T: Sequence>: Sequence, IteratorProtocol
where T.Element: Accumulatable {
    var iterator: T.Iterator
    var accumulatedValue: T.Element?
    
    init(_ sequence: T) {
        self.iterator = sequence.makeIterator()
    }
    
    mutating func next() -> T.Element? {
        if let val = iterator.next() {
            if accumulatedValue == nil {
                accumulatedValue = val
            }
            else { defer { accumulatedValue = accumulatedValue! + val } }
            return accumulatedValue
        }
        return nil
    }
}

Note that neither the author nor the comments mention anything about the fact that this will produce nonsense results for non-sequential Sequence types, ie:

let mySet: Set<Int> = [1, 2, 3]
let myAccSeq = AccumulateSequence(mySet)
for e in myAccSeq { print(e) }

may print 3 4 6 or 2 5 6 or for that matter 1 3 6, and so on.

If I understand you correctly, this is not an example of a problem since we cannot "have a reasonable expectation that [this particular] algorithm would work with a Set".

I do think this is an example of a problem; it shows how people probably forgets that Swift's Sequences can be non-sequential, and that an AccumulatedSequence-type won't make sense for any Sequence, despite its name.

My guess is that there are many more examples like this out there. And at the very least, the documentation has to be improved in order to make sure that everybody understands that a Sequence (in Swift) can be non-sequential, which is not only confusing in and by itself, but it also means that eg otherwise good names like AccumulatedSequence (and sequentiallyEqual) are actually problematic.

But improving the documentation cannot do anything about the following problem:

There are many generic algorithms that, like accumulated sum or elementsEqual, only makes sense for sequential Sequence types, but in Swift, we have no choice but to let them be available for all non-sequential Sequence types too, even though they only add confusing noise to these types. This problem goes both ways of course, algorithms that makes sense only for non-sequential Sequence types pollutes the sequential Sequence types.

It would be very interesting to see some serious discussion about how this situation can be improved. It would be nice if Sequence meant "sequential/ordered sequence of things". The elements of non-sequential/unordered collections/bags of things could still be iterable, but unordered bags shouldn't include properties and methods that only make sense for ordered sequences and vice versa.

3 Likes