`sort-by` with comparator does not have the expected behaviour

skydread1 commented 2 years ago

Seems related to #221

Problem

If we use the default comparator of sort-by, which is compare, we have the expected result.

For instance:

;; same result for JVM and CLR
user> (sort-by first < [[2 1] [3 3] [1 2]])
([1 2] [2 1] [3 3])

;; equivalent to
user> (sort-by first #(compare %1 %2) [[2 1] [3 3] [1 2]])
([1 2] [2 1] [3 3])

However, with a custom comparator, we don't have the expected result.

For instance, to sort in ascending order:

;; in jvm (using emacs cider repl)
user> (sort-by first < [[2 1] [3 3] [1 2]])
([1 2] [2 1] [3 3])

;; in magic (using nostrand repl)
user> (sort-by first < [[2 1] [3 3] [1 2]])
([3 3] [2 1] [1 2])

skydread1 commented 2 years ago

Update

This test is failing without the optimisation.

I have not run the test with the optimisation yet as this one was already failing prior the optimisations.

skydread1 commented 2 years ago

After using the last nostrand commit, it solved the issue.

skydread1 commented 2 years ago

Edge Case Problem

In Clojure, for sort-by, equal elements will not be reordered.

So in a Clojure REPL:

user> (sort-by first [[1 1] [1 0] [0 0]])
=> ([0 0] [1 1] [1 0])

But in a Nostrand REPL:

user> (sort-by first [[1 1] [1 0] [0 0]])
=> ([0 0] [1 0] [1 1])

In MAGIC, in case of equal elements, unlike in Clojure, there is a reordering made using the rest of the data. In our example, the second element of the vector was considered as tie breaker.

nasser commented 2 years ago

This is because ClojureCLR's runtime sort bottoms out in System.Array.Sort which is documented as unstable

This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

while ClojureJVM bottoms out in java.util.Arrays.sort which is documented as stable

This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

given that clojure.core/sort is also documented as stable this is a standard library error on the part of ClojureCLR. We can fix it by moving our implementation to System.Linq.Enumerable.OrderBy which is guaranteed to be stable

This method performs a stable sort; that is, if the keys of two elements are equal, the order of the elements is preserved. In contrast, an unstable sort does not preserve the order of elements that have the same key.

nasser / magic