On Tue, Sep 20, 2011 at 5:56 PM, Evan Laforge
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: http://stackoverflow.com/questions/6399648/what-happens-to-you-if-you-break-... where I use it as an example of why it's important for type class instances to obey the relevant laws. - C.