[Haskell-cafe] Bug with [Double]
Hello all, It seems that I saw something like this in Cafe recevtly. But I am not sure... In GHC 6.12.1 (Platform 2010 on Windows Vista) I have Prelude [1,1+2/3..10] [1.0,1.6665,2.333,2.9996,3.666,4.332,4.998,5.664,6.33,6.9964,7.6625,8.329,8.995,9.66,10.327] -- It is a bug! Prelude [1,5/3..10] [1.0,1.6667,2.3335,3.0,3.6665,4.333,5.0,5.667,6.334,7.001,7.668,8.336,9.004,9.671] -- correct, but... Prelude [1,5/3..4] [1.0,1.6667,2.3335,3.0,3.6665,4.333] -- ... wrong again Prelude [1,1+2/3..10] :: [Float] [1.0,1.667,2.335,3.002,3.67,4.34,5.01,5.68,6.35,7.02,7.69,8.36,9.03,9.7] -- correct Prelude [1,1+2/3..10] :: [Double] [1.0,1.6665,2.333,2.9996,3.666,4.332,4.998,5.664,6.33,6.9964,7.6625,8.329,8.995,9.66,10.327] -- wrong Any comments? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Bug with [Double]
Dmitry Olshansky wrote: It seems that I saw something like this in Cafe recevtly. But I am not sure... In GHC 6.12.1 (Platform 2010 on Windows Vista) I have snip Any comments? The problem you point out is not a problem with Haskell, but a problem with the whole concept of floating point arithmetic as implemented on all modern CPUs. See: http://docs.sun.com/source/806-3568/ncg_goldberg.html You would have got similar problems with just about any language running on the same hardware. Erik -- -- Erik de Castro Lopo http://www.mega-nerd.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Bug with [Double]
Dmitry Olshansky olshansk...@gmail.com writes: Hello all, It seems that I saw something like this in Cafe recevtly. But I am not sure... In GHC 6.12.1 (Platform 2010 on Windows Vista) I have Prelude [1,1+2/3..10] [1.0,1.6665,2.333,2.9996,3.666,4.332,4.998,5.664,6.33,6.9964,7.6625,8.329,8.995,9.66,10.327] -- It is a bug! No it isn't, because of the dodgy Ord instance for Float and Double values. -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Bug with [Double]
2010/5/19 Erik de Castro Lopo mle...@mega-nerd.com: Dmitry Olshansky wrote: It seems that I saw something like this in Cafe recevtly. But I am not sure... In GHC 6.12.1 (Platform 2010 on Windows Vista) I have snip Any comments? The problem you point out is not a problem with Haskell, but a problem with the whole concept of floating point arithmetic as implemented on all modern CPUs. See: http://docs.sun.com/source/806-3568/ncg_goldberg.html You would have got similar problems with just about any language running on the same hardware. This is what used for Double list generation (Haskell Platform 2010): -- numericEnumFromThenTo :: (Ord a, Fractional a) = a - a - a - [a] numericEnumFromThenTo e1 e2 e3 = takeWhile predicate (numericEnumFromThen e1 e2) where mid = (e2 - e1) / 2 predicate | e2 = e1 = (= e3 + mid) | otherwise = (= e3 + mid) -- So normal C loop like for {double i = 1; i = 10; i += 1+2/3) { insert_list(i); } won't generate the same list, as Haskell does in [1,1+2/3..10]. PS Rationals: Prelude [1,1+2/3..10] :: [Rational] [1 % 1,5 % 3,7 % 3,3 % 1,11 % 3,13 % 3,5 % 1,17 % 3,19 % 3,7 % 1,23 % 3,25 % 3,9 % 1,29 % 3,31 % 3] Same result. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Bug with [Double]
Ivan Lazar Miljenovic ivan.miljeno...@gmail.com writes: Dmitry Olshansky olshansk...@gmail.com writes: Hello all, It seems that I saw something like this in Cafe recevtly. But I am not sure... In GHC 6.12.1 (Platform 2010 on Windows Vista) I have Prelude [1,1+2/3..10] [1.0,1.6665,2.333,2.9996,3.666,4.332,4.998,5.664,6.33,6.9964,7.6625,8.329,8.995,9.66,10.327] -- It is a bug! No it isn't, because of the dodgy Ord instance for Float and Double values. And by Ord, I of course mean Enum... -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Bug with [Double]
But Prelude Data.List [1,1+2/3..4] :: [Double] [1.0,1.6665,2.333,2.9996,3.666,4.332] Prelude Data.List unfoldr (\n - let n'=n+2/3 in if n' = 4 then Just (n',n') else Nothing) 1 :: [Double] [1.6665,2.333,2.9996,3.666] Prelude Data.List takeWhile (=4) $ iterate (+2/3) 1 :: [Double] [1.0,1.6665,2.333,2.9996,3.666] How 'dodgy' it should be to produce different result? How [a,b..c] works in this case? 2010/5/19 Ivan Lazar Miljenovic ivan.miljeno...@gmail.com: Dmitry Olshansky olshansk...@gmail.com writes: Hello all, It seems that I saw something like this in Cafe recevtly. But I am not sure... In GHC 6.12.1 (Platform 2010 on Windows Vista) I have Prelude [1,1+2/3..10] [1.0,1.6665,2.333,2.9996,3.666,4.332,4.998,5.664,6.33,6.9964,7.6625,8.329,8.995,9.66,10.327] -- It is a bug! No it isn't, because of the dodgy Ord instance for Float and Double values. -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Bug with [Double]
Thanks, it's clear now. 2010/5/19 Serguey Zefirov sergu...@gmail.com: 2010/5/19 Erik de Castro Lopo mle...@mega-nerd.com: Dmitry Olshansky wrote: It seems that I saw something like this in Cafe recevtly. But I am not sure... In GHC 6.12.1 (Platform 2010 on Windows Vista) I have snip Any comments? The problem you point out is not a problem with Haskell, but a problem with the whole concept of floating point arithmetic as implemented on all modern CPUs. See: http://docs.sun.com/source/806-3568/ncg_goldberg.html You would have got similar problems with just about any language running on the same hardware. This is what used for Double list generation (Haskell Platform 2010): -- numericEnumFromThenTo :: (Ord a, Fractional a) = a - a - a - [a] numericEnumFromThenTo e1 e2 e3 = takeWhile predicate (numericEnumFromThen e1 e2) where mid = (e2 - e1) / 2 predicate | e2 = e1 = (= e3 + mid) | otherwise = (= e3 + mid) -- So normal C loop like for {double i = 1; i = 10; i += 1+2/3) { insert_list(i); } won't generate the same list, as Haskell does in [1,1+2/3..10]. PS Rationals: Prelude [1,1+2/3..10] :: [Rational] [1 % 1,5 % 3,7 % 3,3 % 1,11 % 3,13 % 3,5 % 1,17 % 3,19 % 3,7 % 1,23 % 3,25 % 3,9 % 1,29 % 3,31 % 3] Same result. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Bug with [Double]
On 19/05/2010, at 19:24, Dmitry Olshansky wrote: Prelude [1,1+2/3..10] [1.0,1.6665,2.333,2.9996,3.666,4.332,4.998,5.664,6.33,6.9964,7.6625,8.329,8.995,9.66,10.327] -- It is a bug! Unfortunately, it isn't. Section 6.3.4 of 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. In this case, i = 2/3 so the last value in the list is 10+1/3. The same applies to the other examples. Personally, I consider the Enum class itself to be broken. Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Bug with [Double]
Roman Leshchinskiy r...@cse.unsw.edu.au writes: Personally, I consider the Enum class itself to be broken. Oh? In what sense? It seems to work fine for data types representing bounded enumerable values with a proper mapping to/from Int (it's not bijective since there's no proper mapping from Int - Bool for example); the problem is the fact that Double, etc. are made instances of Enum when this is not the case for those data types. -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Bug with [Double]
On 19/05/2010, at 20:36, Ivan Lazar Miljenovic wrote: Roman Leshchinskiy r...@cse.unsw.edu.au writes: Personally, I consider the Enum class itself to be broken. Oh? In what sense? Firstly, the enumFrom* family of functions shouldn't be methods and the class itself should provide enough facilities for implementing them generically. GHC, for instance, specialises them for all primitive numeric types just to get foldr/build fusion to work. That shouldn't be necessary and doesn't help with overloaded code anyway. For instance, this generates an intermediate list: foo :: Enum a = a - a - [Int] foo a b = [fromEnum x | x - [a..b]] It's even worse when you want to implement similar functionality for other data structures. In vector, I basically had to duplicate all those specialisations to get decent performance. The generic case is horribly inefficient: enumFromTo x y = fromList [x .. y] There is no other sensible definition. Secondly, it should be possible to compute the length and the nth element of [a..b] in constant time. At the moment, it's impossible to distribute [a..b] efficiently across multiple threads - you have to generate the entire list first and then split it into chunks. It's completely unclear to me what [:a .. b:] should mean in DPH, for instance. So basically, Enum only provides enough functionality to desugar [a..b] and friends and even here, it doesn't interact well with fusion. Of course, these concerns weren't relevant back when the class was designed. But it is really broken now, IMO. Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Bug with [Double]
On Wed, May 19, 2010 at 10:57 AM, Serguey Zefirov sergu...@gmail.com wrote: PS Rationals: Prelude [1,1+2/3..10] :: [Rational] [1 % 1,5 % 3,7 % 3,3 % 1,11 % 3,13 % 3,5 % 1,17 % 3,19 % 3,7 % 1,23 % 3,25 % 3,9 % 1,29 % 3,31 % 3] Same result. This sounds like a bug to me. The section of the Haskell Report that deals with the Enum class mentions Float and Double, not Rational, and there's really no sensible reason why Rationals would exhibit this behaviour given that they don't have rounding error. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Bug with [Double]
* Ben Millwood wrote: Prelude [1,1+2/3..10] :: [Rational] [1 % 1,5 % 3,7 % 3,3 % 1,11 % 3,13 % 3,5 % 1,17 % 3,19 % 3,7 % 1,23 % 3,25 % 3,9 % 1,29 % 3,31 % 3] Same result. This sounds like a bug to me. The section of the Haskell Report that deals with the Enum class mentions Float and Double, not Rational, and there's really no sensible reason why Rationals would exhibit this behaviour given that they don't have rounding error. Double is not better: Prelude [9,9+2/3..10] [9.0,9.666,10.332] Prelude [7,9 .. 10] [7,9] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Bug with [Double]
On 19/05/2010, at 23:44, Ben Millwood wrote: On Wed, May 19, 2010 at 10:57 AM, Serguey Zefirov sergu...@gmail.com wrote: PS Rationals: Prelude [1,1+2/3..10] :: [Rational] [1 % 1,5 % 3,7 % 3,3 % 1,11 % 3,13 % 3,5 % 1,17 % 3,19 % 3,7 % 1,23 % 3,25 % 3,9 % 1,29 % 3,31 % 3] Same result. This sounds like a bug to me. The section of the Haskell Report that deals with the Enum class mentions Float and Double, not Rational, and there's really no sensible reason why Rationals would exhibit this behaviour given that they don't have rounding error. From Section 12.1 of the Library Report: instance (Integral a) = Enum (Ratio a) where succ x = x+1 pred x = x-1 toEnum = fromIntegral fromEnum = fromInteger . truncate -- May overflow enumFrom = numericEnumFrom -- These numericEnumXXX functions enumFromThen = numericEnumFromThen -- are as defined in Prelude.hs enumFromTo = numericEnumFromTo -- but not exported from it! enumFromThenTo = numericEnumFromThenTo The numericEnum functions are defined in Section 8 of the Language Report and have semantics required for Float and Double. Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe