Bug 8469 – isSorted fails with predicate "a.length < b.length ? true : a < b"

This code fails the assertion: import std.algorithm; import std.stdio; void main() { string[] x = ["_10", "_20", "_100"]; assert(isSorted!"a.length < b.length ? true : a < b"(x)); } However, it _is_ sorted according to the predicate, so the assertion should pass. I ran into this because sort throws an AssertError sorting ["_100", "_10", "_20"] using that predicate, claiming that the sorting failed, when it actually succeeded. So, not only is this messing up isSorted, but it messes up sort in non-release mode.

That's quite a pickle. The predicate is not a valid sorting relation because according to it both "_20" < "_100" and "_100" < "_20" are true (so it's not antisymmetric). That's how isSorted operates - it compares adjacent elements with the predicate in swapped order. We could make isSorted work with broken predicates (at a performance cost for everyone), but then people may think if that works sort should works too with such predicates etc. etc. Best we can is include an assert in isSorted that catches bad predicates in debug builds. Thoughts?

(In reply to comment #1) > That's quite a pickle. The predicate is not a valid sorting relation because > according to it both "_20" < "_100" and "_100" < "_20" are true (so it's not > antisymmetric). That's how isSorted operates - it compares adjacent elements > with the predicate in swapped order. > > We could make isSorted work with broken predicates (at a performance cost for > everyone), but then people may think if that works sort should works too with > such predicates etc. etc. > > Best we can is include an assert in isSorted that catches bad predicates in > debug builds. Thoughts? Maybe some more advanced languages are or will be able to catch part of the mistakes in the sorting relation at compile-time. I suggest to leave sort()/isSorted() as they are, and add an explanation in the docs of sort() and isSorted() functions that explains the basics of this situation, what's a bad and good sorting relation. Generally when the compiler can't catch something at compile-time, the invariants should be written down in the documentation for the programmer. One characteristic of the the history programming languages is a progressive increase of expressivity, that allows to move move more and more information from the comments written for the programmer to invariants and code that the compiler is able to understand, verify and use.

What did I just read?

(In reply to comment #3) > What did I just read? An insightful answer and a solution to your problem :-)

Hmmm. I didn't realize that the predicate was screwed up, but it does indeed look like it was badly written (I didn't even think about comparing in both directions like that - I should have). I guess that I was in too much of a hurry when I wrote it. Well, sort gives an assertion failure which is pretty bad in this situation in that it claims that the sorting didn't work, which looks completely wrong, since it _did_ work. I definitely think that it makes the most sense to make isSorted assert on bad predicates and have it clearly state that predicate was bad because it's antisymmetric. Then it's clear that the problem is with the predicate and not sorted or isSorted.

(In reply to comment #5) > I definitely think that it makes the most sense to make isSorted assert on bad > predicates and have it clearly state that predicate was bad because it's > antisymmetric. How do you do this?

> How do you do this? I don't know, but from Andrei's comment, he seems to think that it's possible.

It's very simple, if isSorted finds two adjacent elements a, b that satisfy pred(b, a) it can also check whether pred(a, b) and assert if that's also true.

(In reply to comment #8) > It's very simple, if isSorted finds two adjacent elements a, b that satisfy > pred(b, a) it can also check whether pred(a, b) and assert if that's also true. I see, with run-time tests.

Commit pushed to master at https://github.com/D-Programming-Language/phobos https://github.com/D-Programming-Language/phobos/commit/fc99e5583e16897b487a60188421967f664ced02 Merge pull request #729 from andralex/bug8469 Added additional check to isSorted to detect invalid predicates