Proposal: New Eq and Ord instances for Double and Float

[Daniel Fischer]

Proposal: Provide Double and Float with Eq and Ord instances that introduce 
a total order.

Discussion period: Two weeks

Rationale:

The Eq and Ord instances for Double and Float currently follow the IEEE 
specification in that
* NaN == x = False
* NaN /= x = True
* NaN < x = False
* NaN > x = False
* NaN <= x = False
* NaN >= x =  False

This has several undesirable consequences:
- (==) does not define an equivalence relation on those types
- (<) does not define a total order on those types (not even a partial 
order)
- compare always returns GT if (at least) one argument is a NaN

As a result, various algorithms and data structures are broken in the 
presence of NaNs:

Prelude Data.List Data.Set> let nan :: Double; nan = 0/0
Prelude Data.List Data.Set> max nan 1
NaN
Prelude Data.List Data.Set> max 1 nan
1.0
Prelude Data.List Data.Set> minimum [0,1,nan,2,nan,3,4,nan,5,6]
5.0
Prelude Data.List Data.Set> sort [0,1,nan,2,nan,3,4,nan,5,6]
[0.0,1.0,3.0,5.0,6.0,NaN,4.0,NaN,2.0,NaN]
Prelude Data.List Data.Set> let st = fromList [0,1,nan,2,nan,3,4,nan,5,6]
Prelude Data.List Data.Set> Prelude.filter (`member` st) [0 .. 10]
[0.0,1.0,2.0,5.0,6.0]
Prelude Data.List Data.Set> Prelude.filter (`member` (Data.Set.filter (not 
. isNaN) st)) [0 .. 10]
[0.0,1.0,2.0,3.0,4.0,5.0,6.0]
=====================

I therefore propose to change the Eq and Ord instances for Double and Float 
to conform with the behaviour expected from such instances in Haskell, and 
to make the comparisons with IEEE semantics available from the RealFloat 
class.

In more detail:

* Eq:

The Eq instance for Double and Float shall be changed so that
NaN == NaN = True
NaN /= NaN = False

Since there are many bit patterns which are NaN values, there remains the 
question whether all NaNs shall be considered equal or whether only NaNs 
with identical bit patterns should be considered equal.

I lean towards treating all NaNs equal to each other.

A different edge-case is negative zero. At the moment, we have
0.0 == (-0.0) = True
as mandated by IEEE. The question is whether that should be kept or we want 
to disinguish between 0.0 and -0.0.

Because of

recip 0.0 = Infinity
recip (-0.0) = -Infinity

I lean towards distinguishing.



* Ord:

The Ord instance shall be modified so that 
- if currently x < y holds, that shall remain so
- NaN shall (arbitrarily, in analogy to Maybe's Ord instance[s]) be 
considered smaller than all non-NaN values.

If Eq should distinguish different NaNs, the Ord instance should do the 
same.
If Eq should distinguish 0.0 and -0.0, so should the Ord instance.



* IEEE comparisons:

These shall be made available from the RealFloat class (where applicable, 
if the hardware doesn't provide them, default them to the Ord methods).

Two reasons: first their semantics might be needed in some programmes; 
second, as hardware operations, they're fast, in number-crunching 
programmes where NaNs can't occur, that can make a significant difference.

These operators should be visually similar to the Eq and Ord operators but 
not too similar. The ML languages - afaik - mark operators on floating 
point values by appending a dot, (+.), (<.) etc.
That seems too easy to overlook to me, by enclosing the operator in dots,
(.==.), (.<.) the opportunity to spot the difference is doubled without 
being too heavy notation.
On the other hand, we already use the dot for other things, so using dots 
as the distinguishing means may be less that optimal.
Suggestions welcome.