Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

sortBy prepends pivot element to list when all elements return 0 #2926

Closed
ArseAssassin opened this issue Nov 22, 2019 · 7 comments
Closed

sortBy prepends pivot element to list when all elements return 0 #2926

ArseAssassin opened this issue Nov 22, 2019 · 7 comments

Comments

@ArseAssassin
Copy link

Working on a constraint-based sorting algorithm and ran into this issue:
R.sortBy(R.always(0), R.range(0, 11)) // [5, 0, 2, 3, 4, 1, 6, 7, 8, 9, 10]

Expected result:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Is this expected behavior?

@CrossEye
Copy link
Member

CrossEye commented Nov 22, 2019

Where do you run it to get that result?

When I test it in the REPL, I get your expected result.

Now, if I do

R.sortBy(R.always(0), [5, 0, 2, 3, 4, 1, 6, 7, 8, 9, 10])

I get back [5, 0, 2, 3, 4, 1, 6, 7, 8, 9, 10], as expected.

sortBy(always(0)) should be an identity call. If it's not for you, I really want to know why.

And I don't know what you mean in the title by prepending the pivot element.

@ArseAssassin
Copy link
Author

I get the unexpected result using that link.

https://ramdajs.com/repl/#?R.sortBy%28R.always%280%29%2C%20R.range%280%2C%2011%29%29

Strangely enough this seems to occur in the REPL only on my Chrome on Linux. Using an incognito window doesn't solve the issue. Even stranger, it seems to reliably reproduce on Node.

.nvmrc

10.16.3

package.json

{
  "name": "ramda-test",
  "version": "1.0.0",
  "description": "",
  "main": "index.js",
  "scripts": {
    "test": "echo \"Error: no test specified\" && exit 1",
    "start": "node index.js"
  },
  "author": "",
  "license": "ISC",
  "dependencies": {
    "ramda": "^0.26.1"
  }
}

index.js

let R = require('ramda')

console.log(R.sortBy(R.always(0), R.range(0, 11))) // [ 5, 0, 2, 3, 4, 1, 6, 7, 8, 9, 10 ]

@CrossEye
Copy link
Member

CrossEye commented Dec 3, 2019

That it happens on Node and Chrome should not be surprising as they share their JavaScript implementation, V8. It works properly on my year-old version of Chrome on Ubuntu and even older Chromium. I will try to remember to check tomorrow on a more modern Chrome on Windows.

When I look at this again, though, I was hasty in saying that

sortBy(always(0)) should be an identity call.

That is only true if the underlying sort implementation is stable. If not, all bets are off. Last I remember, V8 had switched to a stable sort, but I haven't been paying a lot of attention.

We've discussed including our own sort before, and perhaps it's time we do. That would make things more predictable. Maybe a Timsort.

@Bradcomp
Copy link
Member

Bradcomp commented Dec 3, 2019

@CrossEye timsort is one of my favorite algorithms. It's such a great blend of theory and pragmatism.

What you bring up about stable / unstable is the crux of the the cause, but I am not sure this is an issue regardless of whether we write our own sort. Technically the initial answer is correct. According to the predicate, all items are equal and thus the ordering is irrelevant. If the ordering is relevant then that should be reflected in the sortBy predicate.

Thinking further, if you need a way of telling the sort to just maintain the current order, and you didn't want to rely on the underlying sorting algorithm, you could use an approach like one of these which I think will work no matter what.

@CrossEye
Copy link
Member

CrossEye commented Dec 3, 2019

Quick report. This processes as expected on Chrome 78 / Win64 (that is it acts as if the sort is stable.)

@Bradcomp: I'm afraid I'm not following. I understand that the first answer is correct, but it's incorrect if we insist on a stable sort. Ramda could decide to impose a stable sort. If nothing else, it make for better referential transparency, as it would disallow a sort that randomly picked one of the two values to go first if the comparator returned 0, and it would guarantee results across different JS engines.

I didn't follow what you were trying to suggest with these two snippets, but they are not stable on my Chrome 78 / Win 64 work box:

const sortClosure = () => {
  let i = 0;
  return () => i++;
}
sortBy(sortClosure(), [1,2,3,4,3,2,1,2]) //=> [2, 1, 2, 3, 4, 3, 2, 1]

sort((a, b) => -1, [1,2,3,4,5,6,7,6,5,4,3,2]) //=> [2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 2, 1]

And yes, I love timsort too.

@Bradcomp
Copy link
Member

Bradcomp commented Dec 3, 2019

but they are not stable on my Chrome 78 / Win 64 work box

You're right, I spoke too soon :(

@wojpawlik
Copy link
Contributor

ES2019 requires Array.prototype.sort to be stable. I suggest doing nothing.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants