[Pitch] Making array and friends conform to Comparable

Evolution Pitches
1

Sequence types such as Array do not currently conform to Comparable, which means this code is valid:

let items1 = (1, 2, 3)
let items2 = (4, 5, 6)
print(items1 < items2)

But this is not:

let items3 = [1, 2, 3]
let items4 = [4, 5, 6]
print(items3 < items4)

(One minor wrinkle: print([1, 2, 3] < [4, 5, 6]) is valid today, but only if you import Foundation thanks to IndexPath. This started a debate with my kid, and now I'm here…)

I'd like to propose adding an extension to Sequence to use the built-in lexicographicallyPrecedes() method to make that second code sample valid, like this:

extension Sequence where Element: Comparable {
    public static func <(lhs: Self, rhs: Self) -> Bool {
        lhs.lexicographicallyPrecedes(rhs)
    }
}

We could then manually conform specific types such as array to Comparable:

extension Array: Comparable where Element: Comparable { }

My thinking here is that we already support Comparable for tuples, strings, and IndexPath, so there's a fair chunk of Swift precedent for this behavior. Such a feature also appears standard in other languages such as Rust, Python, Ruby, etc.

I've chosen Sequence because it matches the availability of the lexicographicallyPrecedes() method.

All input welcome. Thank you!

10 Likes
2

Is it possible Sequence left out that conformance due to performance? Tuple, String, and even IndexPath are all fairly likely to be pretty small. Arrays generally have far more elements.

I’m not actually opposed to the change; more power is more better. But comparing large arrays is always expensive.

3

I understand why arrays can be Equatable, it comes up a lot especially with SwiftUI's .onChange and friends.

But what are some practical applications of Comparable arrays? Sort an array of arrays?

4

I guess every person will have different practical examples, but you might:

  • Have version numbers of n components and want to sort them. (Tuple comparisons only support identical arity.)
  • Create a priority queue where ordering tasks depends on the highest priority, but might also involve any number of other things such as the task's deadline, size, last runtime, owner etc.
  • Track an array of football teams and want to sort them by number of wins, or by number of wins then number of losses, or by number of wins then number of losses then number of ties, etc, or by number of goals, or number of matches played, etc.
  • Store customers with a whole bunch of individual purchases and want to sort them so that customers with the biggest purchases come first.

As you say, it's ultimately sorting arrays of arrays.

6 Likes
5

I’m afraid a default implementation of < for all Sequence conformances might be source breaking with existing types that conform to both Sequence and Comparable, if those types pick up their implementation of < from some other protocol extension, the conformance might become ambiguous, or it might even silently pick the new overload and change behavior.

If we’re going to do this, I would suggest overloading < on only those concrete types that will conform to Comparable instead.

Tuples are not (yet) Comparable, but they do overload <. The fundamental distinction here is that since only tuples of the same length can be compared, there’s no potential confusion about what to do when the lengths don’t match. With arrays, there are several possible options, and the author of the conformance has to make some choice among several.

9 Likes
6

Yeah, and, String and IndexPath both carry semantic information that admits the lexicographic ordering as (IMO) a bit more ‘natural’ than it would be for all arrays. They do provide precedent that would make such ordering not exactly surprising for array, but IMO there’s a much stronger argument for “Strings should compare in dictionary order” than there is for “and we should generalize that to Array with any Element type.

5 Likes
7

While I don't think that having < makes sense when similar arity can't be guaranteed, and the language agrees with me at the most basic level:

// Binary operator '<' cannot be applied to two 'Int?' operands
Optional(1) < Optional(2)

…the precedent is set for confusion. All of these are true:

"111" < "2"
[1, 1, 1].lexicographicallyPrecedes([2])
[1].lexicographicallyPrecedes([2, -2])
"1" < "2 - 2"

To be consistent, these should return true as well.

(1, "🍼🐣", false, ()) < (1, "🥛🐥")
(1, "🍼🐣") < (1, "🥛🐥", false, ())

func < <Comparable0: Comparable, Comparable1: Comparable, each Suffix>(
  _ comparables: (Comparable0, Comparable1),
  _ suffixed: (Comparable0, Comparable1, repeat each Suffix)
) -> Bool {
  // You can't implement this with a parameter pack.
  // The compiler can't work with tuple.1 yet.
  // It should be `comparables < (suffixed.0, suffixed.1)`
  fatalError()
}

func < <Comparable0: Comparable, Comparable1: Comparable, each Suffix>(
  _ suffixed: (Comparable0, Comparable1, repeat each Suffix),
  _ comparables: (Comparable0, Comparable1)
) -> Bool {
  // It should be `(suffixed.0, suffixed.1) < comparables`
  fatalError()
}
1 Like
8

I don’t think we should implement comparison for tuples of different lengths. The current plan is to eventually replace the six fixed-length overloads of < on tuples with a single parameter pack version where both sides have the same type (and thus length).

12 Likes
9

I also agree that comparison of sequences of different lengths is ill-defined, but your example isn’t illustrating that. One could invent a reasonable overload of < for Optional<T> where T: Comparable that returned T?.

10

Perhaps you mean Bool?, but at that point it's not a linear order and it's not Comparable. To get a Bool result from comparing two Optionals, you have to decide if nil is smaller than all other values, or if all other values are smaller than nil. (I guess if you think of an Optional as a collection of zero or one elements, nil being the smallest element probably makes the most sense, but it's still an arbitrary choice, so there's no "canonical" way to define such a conformance.)

4 Likes
11

Yes, I meant Bool?. That was a copy editing error.

My definition would be:

lhs: T? rhs: T? Result
.none .none nil
.none .some(_) nil
.some(_) .none nil
.some(x) .some(y) x < y

I think this thread is a great example of why Optional should not be considered a sequence of zero or one elements.

12

What you're talking about generalizable as zip+map.

extension Optional where Wrapped: Comparable {
  static func < (lhs: Optional, rhs: Optional) -> Bool? {
    _?.zip(lhs, rhs).map(<)
  }
}
Optional.zip 
extension Optional {
  static func zip<each _Wrapped>(_ optional: repeat (each _Wrapped)?) -> Self
  where Wrapped == (repeat each _Wrapped) {
    try? (repeat (each optional).value)
  }

  struct NilError: Error { init() { } }

  var value: Wrapped {
    get throws  {
      switch self {
      case let wrapped?: return wrapped
      case nil: throw NilError()
      }
    }
  }
}

That's useful, but it's not Comparable.

It would not make sense for any Sequence to be Comparable unless Optional is made Comparable as well, using the same logic that lexicographicallyPrecedes uses.

(< would be a better representation of what lexicographicallyPrecedes actually does, which is the intersection/conflation of comparing the count of the elements, and all of their values. This is undocumented, but reasonably inferable from the Complexity callout.)

func test<Comparable: Swift.Comparable>(
  empty: Comparable, notEmpty: Comparable
) {
  #expect(empty < notEmpty)
  #expect(notEmpty > empty)
}
test(empty: "", notEmpty: "1") // Already worked without these extensions.
test(empty: [], notEmpty: [1])
test(empty: nil, notEmpty: 1)

extension Array: @retroactive Comparable where Element: Comparable {
  public static func < (lhs: Self, rhs: Self) -> Bool {
    lhs.lexicographicallyPrecedes(rhs)
  }
}

extension Optional: @retroactive Comparable where Wrapped: Comparable {
  public static func < (lhs: Optional, rhs: Optional) -> Bool {
    guard let lhs else { return rhs != nil }
    guard let rhs else { return false }
    return lhs < rhs
  }
}

See also: Implementing `Comparable` for types with optional fields is too hard

13

I would respectfully oppose this idea. This feels like one of those "simple" / "helpful" things that leads to a lot of confusion down the road. PHP and JavaScript have shown us the darkest version of what can happen if a language makes comparisons too flexible.

There is no single, obvious way to compare Arrays of different lengths, which in my mind entirely forecloses this possibility.

6 Likes
14

What if we first introduce a "sort by key" operation:

extension Sequence {
  func sorted<Key: Comparable>(key: (Self.Element) -> Key) -> [Self.Element] {
    return sorted { key($0) < key($1) }
  }
}

The main use case would be sorting an array of structs by some field, eg people.sorted(key: \.firstName). A few other APIs like min and max that take a comparator could be generalized in the same way to take a key projection function.

Now, you can also define a "key type" to make a Sequence into a Comparable:

struct Lexicographic<S: Sequence>: Comparable where S.Element: Comparable {
  let seq: S
  static func <(lhs: Self, rhs: Self) -> Bool {
    return lhs.seq.lexicographicallyPrecedes(rhs.seq)
  }
}

extension Sequence where Self.Element: Comparable {
  var lexicographic: some Comparable { return Lexicographic(seq: self) }
}

To sort an array of arrays in lexicographic order, you would do myArray.sorted(key: \.lexicographic).

Now this works with any type that conforms to Sequence; the type doesn't have to "opt in". Also, you can define other orders on Sequence in the same way. Eg, a hypothetical .shortlex order would instead compare lengths first, so that all sequences of length 2 precede all sequences of length 3, etc.

Here's another trick that composes with the above:

struct Descending<C: Comparable>: Comparable {
  let value: C
  static func <(lhs: Self, rhs: Self) -> Bool {
    return lhs.value > rhs.value
  }
}

extension Comparable {
  var descending: some Comparable { return Descending(value: self) }
}

struct Person {
  let firstName: String
}

let people: [Person] = []
people.sorted(key: \.firstName.descending)

let arrayOfArrays: [[Int]] = []
arrayOfArrays.sorted(key: \.lexicographic.descending)
11 Likes
15

This sounds like sorted(using:) with a KeyPathComparator, although there is no LexicographicComparator to implement this operation.

1 Like
16

That's just a partial order, which I've been told, we've already rejected from the standard library as a concept.

17

Do you know where that discussion is so we can link to it? Reading that may provide some useful context.

While I am not saying it is or is not the case here, sometimes we can add something that was previously rejected, if the reasoning no longer applies. It would be good to review prior discussions to see the reason this idea was previously rejected.

18

It's not quite true that we've flat-out rejected partial orders from the standard library. It would be more accurate to say that all proposals to date to formalize them more in the standard library would have created more trouble than they fixed, in the eyes of the core team / LSG.