Possible Duplicate:
Haskell ranges and floats
Why does the following output occur in haskel:
[0.1,0.3..1]
[0.1,0.3,0.5,0.7,0.8999999999999999,1.0999999999999999]
1.0999999999999999 (I am on a 64bit linux machine if its useful)?0.8999999999999999 when obviously 1.0999999999999999 is out of range?[0.1,0.3..1] is short for enumFromThenTo 0.1 0.3 1.0
The Haskell report says
For Float and Double, the semantics of the enumFrom family is given by the rules for Int above, except that the list terminates when the elements become greater than e3 + i∕2 for positive increment i, or when they become less than e3 + i∕2 for negative i.
Here e3 = 1.0 and your increment i = 0.2, so e3 + i∕2 = 1.1. It's only supposed to stop when it goes bigger than that.
You asked it to stop at 1, but it can only stop at 0.9 or 1.1. There's a rounding error (floating types are inherently inaccurate) and 1.1 has ended up as 1.09999999999, so since this is not greater than 1.0 + i/2, it's allowed.
In fact, even if it were equal to 1.0+i/2 it's allowed, as you can check using the exact [0.1,0.3..1]::[Rational] (after importing Data.Ratio).
You can avoid the problem by calculating the upper limit you're aiming for, 0.9, and specifying that: [0.1,0.3..0.9]. You won't suffer from rounding error unless your increment is small and your numbers are large, i.e. you're working beyond the accuracy of Double for large numbers.
1.09 recurring is mathematically indistinguishable from 1.1, but here we have a finite number of 9s, and that's strictly less than 1.1.
Floating point numbers are stored as if they're in scientific notation, eg 4.563347x10^-7, but in binary, so like 01.1001110101x2^01101110.
This means your number can only be stored completely accurately as a Float if you can express it by summing powers of two, just as you can only write a number in decimal if you can express is by summing powers of 10.
0.2 in your example is 0.001100110011 in binary, with the 0011 repeating forever and 1.1 is 1.0001100110011 again with 0011 repeating forever.
Since only a finite part of those will be stored, when converted back to decimal to show you, they'll be a little out. Often the difference is so small it gets rounded away again, but sometimes you can see it, as here.
This inherent inaccuracy is why enumFromThenTo lets you go above the top number - it's stopping you from having too few because of rounding errors.
To understand this behaviour, you need to know that the expression [a,b..c] will be desugared into enumFromThenTo a b c where enumFromThenTo is a method of the Enum class.
The Haskell standard says that
For
FloatandDouble, the semantics of theenumFromfamily is given by the rules forIntabove, except that the list terminates when the elements become greater thane3 + i∕2for positive incrementi, or when they become less thane3 + i∕2for negativei.
Standards are standards, after all. But that's not very satisfactory.
The Double instance of Enum is defined in the module GHC.Float, so let's look there. We find:
instance Enum Double where
enumFromThenTo = numericFromThenTo
That's not incredibly helpful, but a quick Google search reveals that numericFromThenTo is defined in GHC.Real, so let's go there:
numericEnumFromThenTo e1 e2 e3 = takeWhile pred (numericEnumFromThen e1 e2)
where
mid = (e2 - e1) / 2
pred | e2 >= e1 = (<= e3 + mid)
| otherwise = (>= e3 + mid)
That's a bit better. If we assume a sensible definition of numericEnumFromThen, then calling
numericEnumFromThenTo 0.1 0.3 1.0
will result in
takeWhile pred [0.1, 0.3, 0.5, 0.7, 0.9, 1.1, 1.3 ...]
Since e2 > e1, the definition of pred is
pred = (<= e3 + mid)
where
mid = (e2 - e1) / 2
Therefore we will take elements (call them x) from this list as long as they satisfy x <= e3 + mid. Let's ask GHCi what that value is:
>> let (e1, e2, e3) = (0.1, 0.3, 1.0)
>> let mid = (e2 - e1) / 2
>> e3 + mid
1.1
That's why you see 1.09999... in the list of results.
The reason that you see 1.0999... instead of 1.1 is because 1.1 is not representable exactly in binary.
Why would the standard prescribe such bizarre behaviour? Well, consider what might happen if you only took numbers that satisfied (<= e3). Because of floating point error or nonrepresentability, e3 may never appear in the list of generated numbers at all, which could mean that innocuous expressions like
[0.0,0.02 .. 0.1]
would result in
[0.0, 0.02, 0.04, 0.06, 0.08]
which seems a little bizarre. Because of the correction in numericFromThenTo, we make sure that we get the expected result for this (presumably more common) use case.
