On Mon, 2011-09-26 at 19:54 -0700, Donn Cave wrote:
Pardon the questions from the gallery, but ... I can sure see that 0.3 shouldn't be included in the result by overshooting the limit (i.e., 0.30000000000000004), and the above expectations about [0,2..9] are obvious enough, but now I have to ask about [0,2..8] - would you not expect 8 in the result? Or is it not an upper bound?
Donn, [0, 2 .. 8] should be fine no matter the type, because integers of those sizes are all exactly representable in all of the types involved. The reason for the example with a step size of 0.1 is that 0.1 is actually an infinitely repeating number in base 2 (because the denominator has a prime factor of 5). So actually *none* of the exact real numbers 0.1, 0.2, or 0.3 are representable with floating point types. The corresponding literals actually refer to real numbers that are slightly off from those. Furthermore, because the step size is not *exactly* 0.1, when it's added repeatedly in the sequence, the result has some (very small) drift due to repeated rounding error... just enough that by the time you get in the vacinity of 0.3, the corresponding value in the sequence is actually *neither* the rational number 0.3, *nor* the floating point literal 0.3. Instead, it's one ulp larger than the floating point literal because of that drift. So there are two perspectives here. One is that we should think in terms of exact values of the type Float, which means we'd want to exclude it, because it's larger than the top end of the range. The other is that we should think of approximate values of real numbers, in which case it's best to pick the endpoint closest to the stated one, to correct for what's obviously unintended drift due to rounding. So that's what this is about: do we think of Float as an approximate real number type, or as an exact type with specific values. If the latter, then "of course" you exclude the value that's larger than the upper range. If the former, then using comparison operators like '<' implies a proof obligation that the result of the computation remains stable (loosely speaking, the function continuous) at that boundary despite small rounding error in either direction. In that case, creating a language feature where, in the *normal* case of listing the last value you expect in the list, 0.3 (as an approximate real number) is excluded from this list just because of technicalities about the representation is an un-useful implementation, to say the least, and makes it far more difficult to satisfy that proof obligation. Personally, I see floating point values as approximate real numbers. Anything else in unrealistic: the *fact* of the matter is that no one is reasoning about ulps or exact rational values when they use Float and Double. In practice, even hardware implementations of some floating point functions have indeterminate results in the exact sense. Often, the guarantee provided by an FPU is that the result will be within one ulp of the correct answer, which means the exact value of the answer isn't even known! So, should we put all floating point calculations in the IO monad because they aren't pure functions? Or can we admit that people use floating point to approximate reals and accept the looser reasoning? -- Chris Smith