[Haskell-cafe] instance Enum Double considered not entirely great?
cam at uptoisomorphism.net
Wed Sep 21 00:20:09 CEST 2011
On Tue, Sep 20, 2011 at 5:56 PM, Evan Laforge <qdunkan at gmail.com> wrote:
>> I actually think the brokenness of Ord for floating point values is
>> worse in many ways, as demonstrated by the ability to insert a value
>> into a Data.Set.Set and have other values "disappear" from the set as
>> a result. Getting an unexpected element in a list doesn't really seem
>> as bad as silently corrupting entire data structures.
> Whoah, that's scary. What are some examples of this happening? Does
> this mean it's unsafe to store Doubles in a Map?
Well, you can safely store Doubles in a Map as long as you use a key
type with a bug-free Ord instance. :]
Anyway, the problem with the Ord instance on floating point values is
that it attempts (but fails anyway) to implement the ordering
semantics given by the IEEE spec, which requires that all ordering
comparisons return false if either argument is NaN, and that NaN /=
NaN returns true. This is not the behavior normally expected from an
Ord instance! Adding insult to injury, the "compare" function returns
a value of type Ordering (which assumes a consistent total order), so
the instance contradicts itself: "compare (0/0) (0/0)" gives GT, but
"0/0 > 0/0" is false.
This plays havoc with the search tree used internally by Set and Map,
the result being that if you have any NaN values in the data
structure, you may not be able to find other values anymore. Because
NaN values never compare equal to themselves, I'm not sure if it's
even possible to remove them from the structure, and because of tree
rebalancing I'm not sure how to predict what the impact of one or more
NaNs would be over multiple operations on the data structure.
In short: Using Doubles in a Set, or as the key to a Map, should be
regarded as a bug until proven otherwise (i.e., proving that NaN will
never be inserted).
If you'd like to see an explicit demonstration (which you can try in
GHCi yourself!) see here:
where I use it as an example of why it's important for type class
instances to obey the relevant laws.
More information about the Haskell-Cafe