Proposal: New Eq and Ord instances for Double and Float
Daniel Fischer
daniel.is.fischer at googlemail.com
Mon Sep 26 05:53:05 CEST 2011
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.
More information about the Libraries
mailing list