Member function doesn't work correctly for floating point numbers

Question

In this answer, the following code is evaluated as follows:

> let x = fromList  [0, -1, 0/0, -5, -6, -3] :: Set Float

> member 0 x
True

> let x' = insert (0/0) x

> member 0 x'
False

The author states the this happens because the Eq and Ord floating point instances don't obey the monad laws. How do the Eq and Ord floating point instances break the monad laws and why does that result in the behavior above?

Answer 1

It's not the monad laws that are violated, but the laws for Eq with respect to Ord.

The laws on Eq demand that (==) define an equivalence relation,

forall x. x == x
forall x y. x == y <=> y == x
forall x y z. x == y && y == z => x == z

and the contract of Ord is that < define a total ordering,

forall x. not (x < x)
forall x y. (x < y) || (x == y) || (y < x)
forall x y. not (x < y && y < x)

The floating point types violate these laws because NaNs (NaN = Not a Number) compare unequal to themselves,

0/0 /= 0/0

and any comparison <, <=, ... involving a NaN returns False.

So when there are NaNs in a tree that is supposed to be ordered, a comparison with a NaN when searching for an element can send the recursive search down the wrong subtree.