Ord instance

From HaskellWiki

Revision as of 09:00, 3 September 2010 (edit) Lemming (Talk | contribs) (sketch) ← Previous diff		Current revision (09:35, 3 September 2010) (edit) (undo) Lemming (Talk | contribs) (corrections)
(2 intermediate revisions not shown.)
Line 7:		Line 7:
	Depending on these opinions we come to different conclusions		Depending on these opinions we come to different conclusions
	whether there should be <hask>Ord</hask> instances for <hask>Bool</hask> and <hask>Complex</hask> numbers.		whether there should be <hask>Ord</hask> instances for <hask>Bool</hask> and <hask>Complex</hask> numbers.
		+	In most circumstances expressions like <hask>a < b</hask> are certainly a bug,
		+	when <hask>a</hask> and <hask>b</hask> are <hask>Bool</hask> or <hask>Complex</hask> 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 <hask>(<)</hask> has to be applied to results of <hask>abs</hask>,
		+	<hask>realPart</hask> or other functions that yield a real.
		+	The truth of <hask>False < True</hask> relies on the encoding of <hask>False</hask> by 0 and <hask>True</hask> 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 <hask>False > True</hask>.
		+	If you use the numeric value of boolean values for arithmetics like in <hask>2 * fromEnum bool - 1</hask>
		+	in order to map <hask>False</hask> to -1 and <hask>True</hask> to 1 without an <hask>if-then-else</hask>,
		+	then porting a program between different representations of boolean values becomes error-prone.
-	== Ord for magnitudes ==	+	However you like to work with <hask>Set</hask>s of boolean values and complex numbers,
		+	and <hask>Set</hask> requires an <hask>Ord</hask> instance.
		+	You may consider using the <hask>Ord</hask> instance by <hask>Set</hask> operations an abuse,
		+	since they do not require a particular ordering.
		+	Ordering is only needed for implementation of efficient <hask>Set</hask> operations
		+	and the operations would be as efficient, if the order is reversed or otherwise modified.
		+	But we would certainly not like to have <hask>1 < 2</hask> for <hask>Integer</hask>s
		+	and <hask>1 > 2</hask> for, say, <hask>Rational</hask>s.
		+
		+	The solution might be a type class especially for <hask>Set</hask> and <hask>Map</hask>.
		+	However it would miss automatic instance deriving.
-	== Ord for arbitrary total orderings ==
	== See also ==		== See also ==

---

Current revision

What is the meaning of the instance? Certainly most people agree that an 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 instances for and numbers. In most circumstances expressions like are certainly a bug, when and are or 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 , or other functions that yield a real. The truth of relies on the encoding of by 0 and 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 . If you use the numeric value of boolean values for arithmetics like in in order to map to -1 and to 1 without an ,

then porting a program between different representations of boolean values becomes error-prone.

However you like to work with s of boolean values and complex numbers, and requires an instance. You may consider using the instance by operations an abuse,

since they do not require a particular ordering.

Ordering is only needed for implementation of efficient operations

and the operations would be as efficient, if the order is reversed or otherwise modified.

But we would certainly not like to have for s and for, say, s. The solution might be a type class especially for and .

However it would miss automatic instance deriving.

See also

• Haskell-Cafe on Unnecessarily strict implementations

Category: Style