Geek Answers Handbook

Member function does not work correctly for floating point numbers

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 claims that this happens because the floating-point instances Eq and Ord not subject to the laws of the monad. How do floating-point instances Eq and Ord violate the laws of the monad, and why does this lead to the behavior above?

+6
source share
1 answer

These are not the monad laws that are violated, but the laws for Eq regarding Ord .

The laws in Eq require that (==) determine the equivalence relation,

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

and the Ord contract is that < defines a complete ordering,

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

Floating-point types violate these laws because NaNs (NaN = Not a Number) are compared unevenly with themselves,

 0/0 /= 0/0

and any comparison < , <= , ... using NaN returns False .

Therefore, when there are NaNs in the tree to be ordered, a comparison with NaN when searching for an item can send a recursive search down the wrong subtree.

+14
source

More articles:


All Articles