Ord instance

From HaskellWiki
Revision as of 09:30, 3 September 2010 by Lemming (talk | contribs) (Ord instance for Set)

Jump to: navigation, search

What is the meaning of the Ord instance? Certainly most people agree that an Ord instance shall provide an total ordering. However opinions differ whether there shall be more in it:

  • An Ord instance may also suggest a notion of magnitude
  • An Ord instance may be free of any other association

Depending on these opinions we come to different conclusions whether there should be Ord instances for Bool and Complex numbers. In most circumstances expressions like a < b are certainly a bug, when a and b are Bool or Complex numbers. Consider someone rewrites an algorithm for real numbers to complex numbers and he relies on the type system to catch all inconsistencies. The field operations can remain the same, but (<) has to be applied to results of abs, realPart or other functions that yield a real. The truth of False < True relies on the encoding of False by 0 and True by 1. However there are also programming languages that represent "true" by -1, because this has bit pattern 1....1. The CPU has an instruction to fill a byte with the content of a flag and you can use this bit pattern for bitwise AND and OR operations. This makes that representation very efficient. In such a language it is False > True. If you use the numeric value of boolean values for arithmetics like in 2 * fromEnum bool - 1 in order to map False to -1 and True to 1 without an if-then-else, then porting a program between different representations of boolean values becomes error-prone.

However you like to work with Sets of boolean values and complex numbers, and Set requires an Ord instance. You may consider using the Ord instance by Set operations an abuse, since they do not require a particular ordering. Ordering is only needed for implementation of efficient Set operations and the operations would be as efficient, if the order is reversed or otherwise modified. But we would certainly not like to have 1 < 2 for Integers and 1 > 2 for, say, Rationals.

The solution might be a type class especially for Set and Map. However it would miss automatic instance deriving.


See also