Personal tools

Ord instance

From HaskellWiki

Revision as of 09:35, 3 September 2010 by Lemming (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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 principle we could also provide machine dependent efficient representations of boolean values in Haskell.

If "true" is associated with -1 then it holds
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
Set
s 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
Integer
s and
1 > 2
for, say,
Rational
s. The solution might be a type class especially for
Set
and
Map
.

However it would miss automatic instance deriving.


See also