Why do I need a '<' overload for an Array class?

Question

I'm trying to add functionality to an Array class.
So I attempted to add a sort() similar to Ruby's lexicon.
For this purpose I chose the name 'ricSort()' if deference to Swift's sort().

But the compiler says it can't find an overload for '<', albeit the 'sort({$0, $1}' by itself works okay.
Why?

var myArray:Array = [5,4,3,2,1]
myArray.sort({$0 < $1}) <-- [1, 2, 3, 4, 5]
myArray.ricSort() <-- this doesn't work.

Answer 1

The reason you are getting an error is that the compiler cannot guarantee that the type stored in the Array can be compared with the < operator.

You can see the same sort closure on an array whose type can be compared using < like an Int:

var list = [3,1,2]
list.sort {$0 < $1}

But you will get an error if you try to use a type that cannot be compared with <:

var URL1 = NSURL()
var URL2 = NSURL()
var list = [URL1, URL2]
list.sort {$0 < $1} // error

Especially with all the syntax you can leave out in Swift, I don't see a reason to define a method for this. The following is valid and works as expected:

list.sort(<)

You can do this because < actually defines a function that takes two Ints and returns a Bool just like the sort method is expecting.

Answer 2

Here's a solution that is close to what you are looking for, followed by a discussion.

var a:Int[] = [5,4,3,2,1]

extension Array {

    func ricSort(fn: (lhs: T, rhs: T) -> Bool) -> T[] {
        let tempCopy = self.copy()
        tempCopy.sort(fn)
        return tempCopy
    }
}

var b = a.ricSort(<) // [1, 2, 3, 4, 5]

There are two problems with the original code. The first, a fairly simple mistake, is that Array.sort returns no value whatsoever (represented as () which is called void or Unit in some other languages). So your function, which ends with return self.sort({$0 < $1}) doesn't actually return anything, which I believe is contrary to your intention. So that's why it needs to return tempCopy instead of return self.sort(...).

This version, unlike yours, makes a copy of the array to mutate, and returns that instead. You could easily change it to make it mutate itself (the first version of the post did this if you check the edit history). Some people argue that sort's behavior (mutating the array, instead of returning a new one) is undesirable. This behavior has been debated on some of the Apple developer lists. See http://blog.human-friendly.com/swift-arrays-the-bugs-the-bad-and-the-ugly-incomplete

The other problem is that the compiler does not have enough information to generate the code that would implement ricSort, which is why you are getting the type error. It sounds like you are wondering why it is able to work when you use myArray.sort but not when you try to execute the same code inside a function on the Array.

The reason is because you told the compiler why myArray consists of:

var myArray:Array = [5,4,3,2,1]

This is shorthand for

var myArray: Array<Int> = [5,4,3,2,1]

In other words, the compiler inferred that the myArray consists of Int, and it so happens that Int conforms to the Comparable Protocol that supplies the < operator (see: https://developer.apple.com/library/prerelease/ios/documentation/General/Reference/SwiftStandardLibraryReference/Comparable.html#//apple_ref/swift/intf/Comparable)[1]. From the docs, you can see that < has the following signature:

@infix func < (lhs: Self, rhs: Self) -> Bool

Depending on what languages you have a background in, it may surprise you that < is defined in terms of the language, rather than just being a built in operator. But if you think about it, < is just a function that takes two arguments and returns true or false. The @infix means that it can appear between its two functions, so you don't have to write < 1 2.

(The type "Self" here means, "whatever the type is that this protocol implements," see Protocol Associated Type Declaration in https://developer.apple.com/library/prerelease/ios/documentation/swift/conceptual/swift_programming_language/Declarations.html#//apple_ref/doc/uid/TP40014097-CH34-XID_597)

Compare this to the signature of Array.sort: isOrderedBefore: (T, T) -> Bool

That is the generic signature. By the time the compiler is working on this line of code, it knows that the real signature is isOrderedBefore: (Int, Int) -> Bool

The compiler's job is now simple, it just has to figure out, is there a function named < that matches the expected signature, namely, one that takes two values of type Int and returns a Bool. Obviously < does match the signature here, so the compiler allows the function to be used here. It has enough information to guarantee that < will work for all values in the array. This is in contrast to a dynamic language, which cannot anticipate this. You have to actually attempt to perform the sort in order to learn if the types can actually be sorted. Some dynamic languages, like JavaScript, will make every possible attempt to continue without failing, so that expressions such as 0 < "1" evaluate correctly, while others, such as Python and Ruby, will throw an exception. Swift does neither: it prevents you from running the program, until you fixed the bug in your code.

So, why doesn't ricSort work? Because there is no type information for it to work with until you have created an instance of a particular type. It cannot infer whether the ricSort will be correct or not.

For example, suppose instead of myArray, I had this:

enum Color {
    case Red, Orange, Yellow, Green, Blue, Indigo, Violet
}

var myColors = [Color.Red, Color.Blue, Color.Green]
var sortedColors = myColors.ricSort() // Kaboom!

In that case, myColors.ricSort would fail based on a type error, because < hasn't been defined for the Color enumeration. This can happen in dynamic languages, but is never supposed to happen in languages with sophisticated type systems.

Can I still use myColors.sort? Sure. I just need to define a function that takes two colors and returns then in some order that makes sense for my domain (EM wavelength? Alphabetical order? Favorite color?):

func colorComesBefore(lhs: Color, rhs: Color) -> Bool { ... }

Then, I can pass that in: myColors.sort(colorComesBefore)

This shows, hopefully, that in order to make ricSort work, we need to construct it in such a way that its definition guarantees that when it is compiled, it can be shown to be correct, without having to run it or write unit tests.

Hopefully that explains the solution. Some proposed modifications to the Swift language may make this less painful in the future. In particular creating parameterized extensions should help.