[Haskell-cafe] groupBy without Ord?

[Tillmann Rendel]

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