Allow opt-in conformance to Comparable for Sequences

If the following were added to the standard library:

public extension Sequence where Self: Comparable, Element: Comparable {
    @inlinable static func < (lhs: Self, rhs: Self) -> Bool {
        var lI = lhs.makeIterator()
        var rI = rhs.makeIterator()
        var lOV = lI.next()
        var rOV = rI.next()
        var strictlyLess = lOV == nil && rOV != nil
        while let lV = lOV, let rV = rOV {
            guard lV <= rV else {
                return false
            }
            strictlyLess = strictlyLess || lV < rV
            lOV = lI.next()
            rOV = rI.next()
        }
        return lOV == nil && (rOV != nil || strictlyLess)
    }
}

Then a Sequence could easily opt-in to conforming to Comparable, e.g.:

extension Array: Comparable where Element: Comparable {}

To test the above extension a test framework is useful:

extension Bool {
    var toInt: Int {
        return self ? 1 : 0
    }
}
func cTest<C>(_ a: C, _ b: C) -> (Bool, Bool, Bool, Int) where C: Comparable {
    let e = a == b // One and only one of these should be true.
    let l = a < b
    let g = b < a
    return (e, l, g, e.toInt + l.toInt + g.toInt) // Sum of ints should be 1.
}

Then the extension can be tested:

let t = [Int]()
let t0 = [0]
let t012 = [0, 1, 2]
let t01U = [0, 1, 42]

print(cTest(t, t)) // Equal
print(cTest(t0, t0)) // E
print(cTest(t, t0)) // Less than
print(cTest(t0, t)) // Greater than
print(cTest(t0, t012)) // L
print(cTest(t012, t0)) // G
print(cTest(t012, t01U)) // L
print(cTest(t01U, t012)) // G

What to people think? Worth adding?

Hello @hlovatt, is it the same algorithm as Sequence.lexicographicallyPrecedes(_:)?

That looks like a useful addition to me.

A slightly different implementation (that I understand better):

public extension Sequence where Self: Comparable, Element: Comparable {
    @inlinable static func < (lhs: Self, rhs: Self) -> Bool {
        var lI = lhs.makeIterator()
        var rI = rhs.makeIterator()
        
        while let lV = lI.next() {
            if let rV = rI.next() {
                if lV < rV { return true }
                if rV < lV { return false }
            } else {
                return false // rhs shorter than lhs
            }
        }
        return rI.next() != nil // lhs shorter than rhs?
    }
}
1 Like

Maybe this should only be available to Collection, given that comparing a single-pass sequence might consume it?

Unless I am mistaken, sequences (and collections) of Equatable elements are not even Equatable, there is only a elementsEqual(other:) method of the Sequence protocol.
So making general sequences conform to Comparable might indeed be of limited use.

I am not sure what the right type is on which this should/could be implemented.

This wouldn't be the right level to litigate the single-pass sequence issue at, given all the other Sequence methods that also consume them. But, as @gwendal.roue says, I believe this is already available as lexicographicallyPrecedes(_:) (and lexicographicallyPrecedes(_:by:)), so this is kind of a minor convenience, saving you about 3 lines of code. It raises some questions as to whether this is a good default for sequences in general, because it could theoretically be used accidentally (probably not a big risk).

Good point, I did not know (or had forgotten :) about lexicographicallyPrecedes.

What about making Array conditionally conform to Comparable (similar to the existing
conditional conformances to Equatable, Hashable, Codable, ...). Has this been discussed before?

While I do not think every sequence should have a default == and < based on elementsEqual and lexicographicallyPrecedes, I do wonder if AnySequence should.

Except that < is not a method, it's an operator. Sequence has no first property for the same reason, i.e. it would probably be too surprising for a computed property to consume the sequence.

Oh, perhaps. It seems obvious that comparing single pass sequences will consume them for any reasonable comparison method, though. first is a little different to me, because it would have been possible to make it work for most sequences without too much effort or overhead, even if they are single pass (e.g. the commonly provided peek method for streams). So Swift could have required that first has sensible semantics for all sequences, but that might have imposed one element of extra storage in some cases.

You are right - I should use that - thanks.

Currently Array etc. conditionally conforms to Equatable, Hashable, and Codable and adding the proposed extension would then allow extensions on Array etc., so that Comparable behaves like Equatable, etc.

You can's just add Comparable into Set however, because it doesn't have a defined iteration order. But assuming that Array conditionally conforms to Comparable (as suggested), then:

extension Set: Comparable where Element: Comparable {
    @inlinable public static func < (lhs: Set<Element>, rhs: Set<Element>) -> Bool {
        return lhs.sorted() < rhs.sorted()
    }
}

For a dictionary: very similar to Set (treating an entry as a (key, value) tuple).

I don't think that single-pass sequences are a problem, because everyone would expect a comparison to consume the sequences (if you did a comparison, it is likely that is what you wanted the single-pass sequences for in the first place).

Therefore I think it is viable to add this extension to Sequence rather than higher up the hierarchy.