Hi, martin wrote:
But I still have trouble to believe, that sorting (Ord=>) is cheaper than aligning (Eq=>) because sorting does aligning plus some more. Does (Ord=>) make life so much easier [...]?
Yes, it does. For example, if you know that x < y and you know that y < z, you immediately also know that x < z without having to call (<) a third time. But if you know that x /= y and you know that y /= z, you don't know anything about whether x /= z or not. To learn this, you have to call (/=) a third time. Many sorting algorithms exploit this by cleverly comparing elements in such an order that no matter how they compare, we get to safe some of the calls to (<). This situation is typical in programming: A seemingly harder problem can be easier to solve than an seemingly easier variant, because partial solutions of the seemingly harder problem contain more information than partial solutions of the seemingly easier variant of the problem. In this case, the partial solutions are the results of x < y and y < z, and if they are both true, they contain enough information to also know x < z without computing anything. So if you cannot solve a problem, sometimes you have to make it harder in order to make it easier. Tillmann