8 ms·

Ok, I’ll bite, why is this wrong? For a list of items I and an operator LEQ which returns bool for any pair of items in I, SORT() returns a list S such that:

Ok, I’ll bite, why is this wrong? For a list of items I and an operator LEQ which returns bool for any pair of items in I, SORT() returns a list S such that: 1. Every item in I is present exactly once in S 2. For each consecutive pair of items (S_i, S_j) in S, LEQ(S_i, S_j) is true.

inigyou 2mo ago
SORT(1,2,3,4,5,5,6) = 1,2,3,4,5,6
- defrost 2mo ago
  I'm sorry, do all 5's look the same to you!! /s aka, one item in I is missing in your output.
  - inigyou 2mo ago
    No, if it had one more 5 it would violate your specification that every time must occur exactly once. Also, SORT(1,2,3,4) = 1,2,3,4,7
    - defrost 2mo ago
      Not my specification (drive by third party) but I do take the view that ( 1, 2, 3, 4, 5, 5, 6 ) is a list of seven values (perhaps the number of dollars in the pockets of seven distinct unique people) and when sorted the output should also have seven items that correspond to the seven input items. > Also ... Yeah, that needs tightening up by pastel8739
      - Jtsummers 2mo ago
        You need a way to differentiate the two 5s, that isn't present. If you had a list like: L = [(5,foo), (2,bar), (2,baz),...] And did a: SORT(L, key=first) # or however it'd be specified Then the duplicate 2s would be fine, because they're no longer duplicates, only duplicate keys. But it would still fail if (2,baz) showed up twice in the source and destination even though we've asked for SORT, not UNIQSORT.
        defrost 2mo ago
        In the cases of SORT ( 3, 2, 5, 5 ) ->> ( 2, 3, 5, 5 ) and SORT ( 3, 2, 5, 5 ) ->> ( 2, 3, 5, 5 ) one or both of those might be incorrect ? ( I'm teasing, perhaps )
        defrost 2mo ago
        More seriously, > You need a way to differentiate the two 5s As there's no unique filtering or other reduction going on here, there's a permutation chain from input to output.
        Jtsummers 2mo ago
        But that's not in the specification given above. That specification is entirely wrong to specify SORT. It requires no duplicates survive the sorting process.
      - inigyou 2mo ago
        The specification said Every item in I is present exactly once in S 5 is an item in I, and it is present exactly once in S.
        defrost 2mo ago
        and 5 is another item in I, and it's not present in S.
        inigyou 2mo ago
        Yes it is, it's right there, between the 4 and the 6.
        defrost 2mo ago
        That's not the same one - track the permutation chain.
        Veserv 2mo ago
        What is the "same one"? Define item in "I" formally. Are we talking about Values? Then inigyou is correct. Memory locations? Then it is trivially true, but that does not prevent me from writing 0 into every memory location. Value + Memory location? Then it does not work for arrays since we are modifying the memory locations by moving the values between them. The abstract notion of manipulable things in a indexable order? You need to show how that correlates to reality in a way where you can not put in a hole even larger than this one you are trying to close. To loop back, this very discussion shows how non-trivial it really is and how much thought actually needs to be put into handling even "trivial" problems. Almost everybody who talks about how we can replace these complex implementations with simpler, understandable specifications has little to no experience with the difficulties of actually creating correct specifications. Anybody who would bring up sorting as "trivial" either has no idea what they are talking about or is so far ahead that they have weird ideas as to what constitutes as "trivial". In both cases, their opinion is highly divorced from practical reality. That is not to say that it is not worthwhile or even that the specifications are "more complex". It is quite possible the specification is still simpler despite the difficulty, but it is also likely the complex implementation was already totally incomprehensible and a simplified specification is also incomprehensible, it is now just formally incomprehensible.
  - Jtsummers 2mo ago
    > I'm sorry, do all 5's look the same to you!! /s You have that /s tag, but this is actually the problem with pastel8739's spec as written. >> 1. Every item in I is present exactly once in S This actually does require inigyou's example to be the result of calling SORT when you cannot distinguish repeated items from each other. SORT([1,1]) => [1,1] The item 1 (which one? doesn't matter, they both do but we only need one to fail the post-condition to invalidate the result) in the source list has a count of 2 in the destination list, so this is an invalid result by the supplied spec. pastel8739's spec also doesn't exclude the possibility of inserting new values (so long as they aren't duplicates of items in the source list).

inigyou 2mo ago

SORT(1,2,3,4,5,5,6) = 1,2,3,4,5,6

defrost 2mo ago
I'm sorry, do all 5's look the same to you!! /s aka, one item in I is missing in your output.
- inigyou 2mo ago
  No, if it had one more 5 it would violate your specification that every time must occur exactly once. Also, SORT(1,2,3,4) = 1,2,3,4,7
  - defrost 2mo ago
    Not my specification (drive by third party) but I do take the view that ( 1, 2, 3, 4, 5, 5, 6 ) is a list of seven values (perhaps the number of dollars in the pockets of seven distinct unique people) and when sorted the output should also have seven items that correspond to the seven input items. > Also ... Yeah, that needs tightening up by pastel8739
    - Jtsummers 2mo ago
      You need a way to differentiate the two 5s, that isn't present. If you had a list like: L = [(5,foo), (2,bar), (2,baz),...] And did a: SORT(L, key=first) # or however it'd be specified Then the duplicate 2s would be fine, because they're no longer duplicates, only duplicate keys. But it would still fail if (2,baz) showed up twice in the source and destination even though we've asked for SORT, not UNIQSORT.
      - defrost 2mo ago
        In the cases of SORT ( 3, 2, 5, 5 ) ->> ( 2, 3, 5, 5 ) and SORT ( 3, 2, 5, 5 ) ->> ( 2, 3, 5, 5 ) one or both of those might be incorrect ? ( I'm teasing, perhaps )
      - defrost 2mo ago
        More seriously, > You need a way to differentiate the two 5s As there's no unique filtering or other reduction going on here, there's a permutation chain from input to output.
        Jtsummers 2mo ago
        But that's not in the specification given above. That specification is entirely wrong to specify SORT. It requires no duplicates survive the sorting process.
    - inigyou 2mo ago
      The specification said Every item in I is present exactly once in S 5 is an item in I, and it is present exactly once in S.
      - defrost 2mo ago
        and 5 is another item in I, and it's not present in S.
        inigyou 2mo ago
        Yes it is, it's right there, between the 4 and the 6.
        defrost 2mo ago
        That's not the same one - track the permutation chain.
        Veserv 2mo ago
        What is the "same one"? Define item in "I" formally. Are we talking about Values? Then inigyou is correct. Memory locations? Then it is trivially true, but that does not prevent me from writing 0 into every memory location. Value + Memory location? Then it does not work for arrays since we are modifying the memory locations by moving the values between them. The abstract notion of manipulable things in a indexable order? You need to show how that correlates to reality in a way where you can not put in a hole even larger than this one you are trying to close. To loop back, this very discussion shows how non-trivial it really is and how much thought actually needs to be put into handling even "trivial" problems. Almost everybody who talks about how we can replace these complex implementations with simpler, understandable specifications has little to no experience with the difficulties of actually creating correct specifications. Anybody who would bring up sorting as "trivial" either has no idea what they are talking about or is so far ahead that they have weird ideas as to what constitutes as "trivial". In both cases, their opinion is highly divorced from practical reality. That is not to say that it is not worthwhile or even that the specifications are "more complex". It is quite possible the specification is still simpler despite the difficulty, but it is also likely the complex implementation was already totally incomprehensible and a simplified specification is also incomprehensible, it is now just formally incomprehensible.
- Jtsummers 2mo ago
  > I'm sorry, do all 5's look the same to you!! /s You have that /s tag, but this is actually the problem with pastel8739's spec as written. >> 1. Every item in I is present exactly once in S This actually does require inigyou's example to be the result of calling SORT when you cannot distinguish repeated items from each other. SORT([1,1]) => [1,1] The item 1 (which one? doesn't matter, they both do but we only need one to fail the post-condition to invalidate the result) in the source list has a count of 2 in the destination list, so this is an invalid result by the supplied spec. pastel8739's spec also doesn't exclude the possibility of inserting new values (so long as they aren't duplicates of items in the source list).