Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is there a bug in the minimum function?

Tags:

haskell

I have a list mins of 415920 numbers, all supposed to be closed to 0.1:

Prelude Lib> take 5 mins
[9.83610706554002e-2,9.847021825032128e-2,9.847021825032128e-2,9.898395035483082e-2,9.898395035483082e-2]

However:

Prelude Lib> minimum mins
0.10087849151477328

The minimum function is not supposed to return the minimum ?

This result sounds plausible:

Prelude Lib> foldr min 100000 mins
1.1763616593045858e-4

Is it a bug, or I misunderstand minimum ?

Similar issue with maximum:

Prelude Lib> maximum mins
3261145.0627630088
Prelude Lib> foldr max 0 mins
0.1207868227600914

Sorting the list yields a third result for the maximum:

Prelude Lib> import Data.List as L
Prelude Lib L> mins' = sort mins
Prelude Lib L> head mins'
1.1763616593045858e-4
Prelude Lib L> last mins'
0.10295664278431726

And applying minimum and maximum on the sorted list yields a third result for the minimum:

Prelude Lib L> minimum mins'
0.10045801977483232
Prelude Lib L> maximum mins'
3261145.0627630088

Edit

After @max630's comment, I've searched in the list with a text editor. The 3261145.0627630088 is indeed here, and there are some NaN:

NaN,NaN,3261145.0627630088

Conclusion: it looks like minimum gives a wrong result, and maximum gives the correct result.

foldr max gives a wrong result, foldl max gives the good one:

> foldl max 0 mins
3261145.0627630088
like image 717
Stéphane Laurent Avatar asked Apr 06 '18 05:04

Stéphane Laurent


1 Answers

The reason to all issues is that the list contains NaN. Apparently it violated the Ord's total ordering requirement[*], so you cannot expect algorithms which use the ordering - either picking minimum or sorting - to produce correct result when it is in the input. Instead they will produce something which depends on their internal implementation, and may be different depending on seemingly unimportant reasons, for example input order. You should filter it out before doing anything else.

[*] Ord does not have it laws written out explicitely (neither does Eq which NaN also breaks), but here example of breaking totality rule, as it is described in Wikipedia (thanks @sjakobi for correcting):

Prelude> let nan = 0 / 0
Prelude> nan
NaN
Prelude> nan <= 1
False
Prelude> 1 <= nan
False
Prelude>
like image 155
max630 Avatar answered Oct 15 '22 16:10

max630