Hacker News Reader

Comment by jzer0cool | Hacker News Reader

> "just not the sorted list we were probably hoping for ... > "For every item j in a list, ensure that the element j ≤ j+1 ... Yet the list [1, 2] also satisfies the definition since it is a sorted list, just not the sorted list we were probably hoping for.

If the input satisfies and happens to be the output in this case, why is article saying this to be a bug? Why "just not the sorted list we were probably hoping for"?

View on HN

> That is, given the list [7, 3, 5], she expects that the program will return [3, 5, 7] and satisfy the definition. Yet the list [1, 2] also satisfies the definition since “it is a sorted list, just not the sorted list we were probably hoping for,” Parno said.

Because the human meant "sort this list", not just "return a sorted list". They put in [7, 3, 5] and got back [1, 2]. Then they realized their specification was incomplete.

Thank you to help point out. I read the specification differently _because_ it we want a sorted list (a lot of implied definitions about input and output). I see how this complements the next paragraph how ambiguous and difficult in can be to write such formal definitions which includes all such cases.

> For every item j in a list, ensure that the element j ≤ j+1

What would be the model example for the correct formal definition? When I hear "sort", there are implied constraints/parameters so [1,2] would not have even been a possible solution.

To find the missing constraints, you can try asking what's wrong with the list [1, 2].

You might imagine trying to have an argument with a person trying to sell you a list sorter. The salesman is just going on and on about how "but look, each element of the list I gave you is in the right order! So you should buy my very nice list sorter!". I would want to yell "but you didn't include any of the numbers from the input list! You just forgot about 7, 3, and 5."

So, another formal constraint might be something like this:

    for each element, i, in the input list, the element i must be in the output list.

Then, you might again try putting in [7,3,5] and get back a list like this: [1,2,3,4,5,6,7]. Again, imagine arguing with the pushy salesman. The salesman says "Look, you wanted a list with the numbers 7, 3, and 5, and you wanted a list in order, this is both of those things, so you have to pay me for my fine list-sorter now!" And again, I would want to object and say something like "but wait a second, I want ONLY the numbers that I gave you in the input list in the output list!". So, you end up with something like:

    for each element, j, of the output list, the element j must be in the input list.

Now, you try putting in [7,3,5] again. What's the worst thing that might come out the other end that's still following all of these 3 rules? Can you spot the next problem?

A sorted list needs to not only be sorted, but to be a permutation of the original list.

Reply on news.ycombinator.com