[Haskell-cafe] groupBy without Ord?
Tillmann Rendel
rendel at informatik.uni-marburg.de
Mon Mar 31 22:00:31 UTC 2014
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
More information about the Haskell-Cafe
mailing list