I have a compare function which I use as the first argument of sort. I have occasionally gotten an exception raised by Tim Sort that my compare function does not enforce certain invariants. However, the error message does not report the offending input sequence being sorted.
My attempts to print the sequence before sorting it have failed, as the exception is rare. I tried refactoring my compare function, guessing about what the error might be. I cannot reproduce error.
Can someone take a look at my function and warn me about potential problems?
(defn sort-operands [operands]
(letfn [(cmp [a b]
(cond
(= a b) 0
(not (= (type a) (type b)))
(compare (.getName (type a))
(.getName (type b)))
(and (seq? a)
(seq? b))
(loop [a a
b b]
(cond
(and (empty? a)
(empty? b)) 0 ;; can this occur? we know the sequences are not =
(empty? a) 1
(empty? b) -1
(= (first a) (first b)) (recur (rest a) (rest b))
:else (cmp (first a) (first b))))
(seq? a) 1 ;; can this occur? because (type a) = (type b), and they are not both seq?
(seq? b) -1
:else
(compare a b)))]
(sort cmp operands)))
Very likely this comparator function you have written does not represent a total order on all of the values you are trying to sort. That is, it violates one of the properties of a total order: https://en.wikipedia.org/wiki/Total_order
Reading your comparator function, it is not yet clear to me which of these properties is violated, but these things can be subtle. Are you trying to create a comparison function that works for arbitrary types of objects? That can be very tricky. I started creating one, but I do not trust it to be correct or complete for all possible types, near the end of this article: https://clojure.org/guides/comparators#_comparators_that_work_between_different_types
I would recommend adding a try expression around your call to sort, and if it throws an exception, catch it and save the operands somewhere that you can investigate them later. If you can reproduce it in a REPL session, then saving them in a ‘global’ atom using ‘swap!’ is a good place that you can access it in the REPL later. Writing it to a file is a bit tougher to do it in a way that preserves all information about the run-time objects that might be relevant, but you can try that, too.
Is it possible for two object to have the same type, with one a seq? and the other not be? I’ve included that case in the code, but I’m not sure whether it can happen.
That sounds complicated. Where is what I’m trying. Is it correct?
(def problematic-operands (atom ()))
(defn sort-operands
"Sort the given list of operands into deterministic order, making it possible
to easily find identical elements, and to write test cases."
[operands]
(letfn [(cmp [a b]
(cond
(= a b) 0
(not (= (type a) (type b)))
(compare (.getName (type a))
(.getName (type b)))
(and (seq? a)
(seq? b))
(loop [a a
b b]
(cond
(and (empty? a)
(empty? b)) 0
(empty? a) 1
(empty? b) -1
(= (first a) (first b)) (recur (rest a) (rest b))
:else (cmp (first a) (first b))))
(seq? a) 1
(seq? b) -1
:else
(compare a b)))]
(try (sort cmp operands)
(catch Exception e
(do (swap! problematic-operands (fn [_] operands))
(printf "saving problematic operands in *problematic-operands*: %s" operands)
(throw e))))))
I cannot think of a way that could happen. Given the definition of seq?, either an object x has a class that makes (instance? clojure.lang.ISeq x) true, or it doesn’t. If two objects have the same class, then they should return the same value for seq? as each other. Note that type can return the same value for objects with different classes. You could try class instead of type, but I do not know what input you are using, and whether your data that is causing the exception would be one of those cases.
That looks correct to me. You can always try out the exception handling stuff in a test function that always throws an exception, to test if it works, if you are worried about wasting time with wrong error-handling code.
You say that it sounds complicated. I am sure there are other ways to find out what data is causing the exception to occur, but this seems pretty straightforward to me. Recording actual data that causes a problem can be a whole lot more informative, and take less time, than guessing without getting results.
Again I forgot that (seq? [1 2 3]) returns false. So my function is not sorting arrays the way I want. I want lists and arrays to sort according to the first unequal objects. For example. [1 2 "hello" 5 6] vs [1 2 "world" 8 9] these should compare by comparing "hello" to "world". I think what I need is sequential? rather than seq?.
How many times will that bite me before I learn that arrays are not seq? ?
seq? Is true for lists, cons cells, and lazy sequences sequential? is true for all seq? and vectors seqable? is also true for arrays, queues, sets and maps.
I just discovered a problem with my try/catch after receiving the following output of the failure in my ci pipeline. Notice that my printf attempts to print the sequence which caused a problem, but I forgot to call (seq operands), so it printed as the unhelpful clojure.lang.LazySeq@f54c3f6e
124 saving problematic operands in *problematic-operands*: clojure.lang.LazySeq@f54c3f6e
125 lein test :only clojure-rte.rte-tester-test/t-test-rte-to-dfa
126 ERROR in (t-test-rte-to-dfa) (TimSort.java:903)
127 Uncaught exception, not in assertion.
128 expected: nil
129 actual: java.lang.IllegalArgumentException: Comparison method violates its general contract!
130 at java.util.TimSort.mergeHi (TimSort.java:903)
131 java.util.TimSort.mergeAt (TimSort.java:520)
132 java.util.TimSort.mergeForceCollapse (TimSort.java:461)
133 java.util.TimSort.sort (TimSort.java:254)
134 java.util.Arrays.sort (Arrays.java:1441)
135 clojure.core$sort.invokeStatic (core.clj:3115)
136 clojure.core$sort.invoke (core.clj:3102)
If either a is a lazy sequence, I’d like to recursively call (cmp (seq a) b), similarly for b. How can I make this check? Do I need to make it before or after the equality check? Certainly before the type check, because if a is lazy and b is not then their types are different, but I’d like to compare them by content via the loop.
Assuming both are some kind of sequence (lazy or not), why not call both with seq?
It’s also fine to use = to compare sequences because comparison is done by value, not by type, so [1 2 3] == '(1 2 3)
wrt to your case, you can loop on
Ah, if sequence equality is done by value, then that’s perhaps the transitive issue with my code wrt Tim Sort. Tim sort assumes a < b, b < c => a<c. But my code enforces a < b if (.getName (type a)) < (.getName (type b)), even in cases where (= a b)
For example if Tim sort as moved a and b into different buckets and sorted those buckets separately, then later discovers that a==b, that sounds like something that would violate the general contract of Tim sort.
I don’t think it’s safe to assume that if one sequence is lazy, then also the other is. It might be the case that one sequence is generated with map and other is generated with (....) or (list …)`
That’s the case I was aiming at, perhaps the fault is with how I presented it.
The sequence can be a result of map, list or [...] but they are all “the same” in the eyes of seq
Specifically:
Jim, I would recommend taking a look at the code at the following link that I wrote some years back – but haven’t battle-tested by heavy use. It uses sequential? as a way to identify most (all? no guarantees today, but read the comments) data values in Clojure that are ‘similar’ to sequences/vectors. It defines a function comparison-class that is called on both of the values to compare, and is more “coarse” in putting different types into the same “sort bucket” versus type or class: https://clojure.org/guides/comparators#_comparators_that_work_between_different_types
after receiving the following output of the failure in my ci pipeline. Notice that my