On Mon, Sep 26, 2011 at 5:53 AM, 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.
I just want to point out that (everyone probably knows this, but it wasn't mentioned explicitly), as I understand it, conceptually a NaN value of a floating-point type has a different meaning from (say) a Nothing value of a Maybe type. Nothing usually means Nothing. NaN means "anything else": an undefined, invalid, unrepresentable, *or* missing number. The operation that produced it might've had a well-defined value in theory, but the type couldn't represent it. So it's so-to-speak an existential value: it has a value, you just can't know what it is. In the same way that existential types don't unify with any other types, even other existential types, NaNs don't compare equal with any other value, even other NaNs. NaN /= NaN because sqrt(-2) /= sqrt(-3). Notwithstanding the above, it might be useful practically to treat a NaN as analogous to a Nothing anyways (as per your examples), so this is neither a vote for nor against.
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.
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
-- Work is punishment for failing to procrastinate effectively.