News for hackers. Stuff that matters.
Re:Ask HN: What is your favorite CS paper? by stevenschmatz on Thursday August 24, 2017 @02:37PM (#15092759)
What's the catch? Are there any preconditions on the input required?
Re:Ask HN: What is your favorite CS paper? by kraghen on Thursday August 24, 2017 @03:54PM (#15093468)
All orderings must be specified as a reduction to a primitive order using the fact that if you have an equivalence relation on some type A and a reduction f : B -> A then you have an equivalence on B defined by x = y when f(x) = f(y).

Now, take the rational numbers. For the usual binary comparison we can simply define (a/b) < (c/d) as ad < cb. It's not obvious how to express this as a reduction to a primitive ordering (the answer is to compute the continued fraction).

In fact, I'm not aware of any systematic way of deriving discrimination-suitable orderings from binary predicates -- it might be an open research problem, as far as I am aware.

Re:Ask HN: What is your favorite CS paper? by KirinDave on Thursday August 24, 2017 @04:04PM (#15093570)
> In fact, I'm not aware of any systematic way of deriving discrimination-suitable orderings from binary predicates -- it might be an open research problem, as far as I am aware.

That'd be an even more remarkable discovery in light of the stuff you worked on though, wouldn't it?

Re:Ask HN: What is your favorite CS paper? by kraghen on Thursday August 24, 2017 @04:14PM (#15093660)
It might, I never really discussed this aspect with Fritz! For my thesis I was mostly focussed on applications to database queries, and I never encountered any concrete examples of orderings that couldn't be dealt with in an obvious way using discrimination based sorting.
Re:Ask HN: What is your favorite CS paper? by KirinDave on Thursday August 24, 2017 @02:49PM (#15092872)
No. The catch is that it's hard to write it in a way that doesn't require very fiddly local mutation or explosive allocation.

The other catch is that no one has demonstrated that you can do it without a good static type system. It shouldn't be impossible, but there are a lot of challenges in an already challenging algorithm.

Re:Ask HN: What is your favorite CS paper? by gbacon on Thursday August 24, 2017 @03:14PM (#15093098)
What are the constants hiding inside that 𝒪(𝑛)?
Re:Ask HN: What is your favorite CS paper? by KirinDave on Thursday August 24, 2017 @03:28PM (#15093225)
They can be bad. But so was merge sort in its naive implementation and folks worked that out. Radix sort sees a lot of use in the real world and it saves a lot of energy.