#15081: Finite list becomes infinite after maping fractional function for high numbers -------------------------------------+------------------------------------- Reporter: Onsed | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Linux | Architecture: x86_64 Type of failure: Incorrect result | (amd64) at runtime | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by sighingnow): Look at the enumerate method for fractional types: {{{#!hs numericEnumFrom :: (Fractional a) => a -> [a] numericEnumFrom n = n `seq` (n : numericEnumFrom (n + 1)) numericEnumFromTo :: (Ord a, Fractional a) => a -> a -> [a] numericEnumFromTo n m = takeWhile (<= m + 1/2) (numericEnumFrom n) }}} A possible improvement should be recording the accumulate increment and add it to the base number, rather than `+1` every time. For `Double` (64-bit floating point), the number `9007199254740991 + 1/2` has binary representation: {{{ 0x4340000000000000 }}} However, the number * `9007199254740990` is: `0x433ffffffffffffe` * `9007199254740990 + 1` is `0x433fffffffffffff` * `(9007199254740990 + 1) + 1` is `0x4340000000000000` * `((9007199254740990 + 1) + 1) + 1` is `0x4340000000000000` Note that `(9007199254740990 + 1) + 1` has the same binary representation with `((9007199254740990 + 1) + 1) + 1`, so the condition `(<= m + 1/2)` will always hold. Then we get the infinite list. If we change the upper bound, for example, {{{ map (/2) [9007199254740989..9007199254740990] }}} It works fine and prints `[4.5035996273704945e15,4.503599627370495e15]`. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/15081#comment:2> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#15081: Finite list becomes infinite after maping fractional function for high numbers -------------------------------------+------------------------------------- Reporter: Onsed | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Linux | Architecture: x86_64 Type of failure: Incorrect result | (amd64) at runtime | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Yes, dead right. Does not look hard to fix, if someone could look at the library instances for `Enum Double` and `Float`. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/15081#comment:4> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#15081: Finite list becomes infinite after maping fractional function for high numbers -------------------------------------+------------------------------------- Reporter: Onsed | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Linux | Architecture: x86_64 | (amd64) Type of failure: Incorrect result | Test Case: at runtime | libraries/base/tests/enumNumeric Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D4650 Wiki Page: | -------------------------------------+------------------------------------- Changes (by sighingnow): * testcase: => libraries/base/tests/enumNumeric * status: new => patch * differential: => Phab:D4650 -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/15081#comment:6> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#15081: Finite list becomes infinite after maping fractional function for high numbers -------------------------------------+------------------------------------- Reporter: Onsed | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Linux | Architecture: x86_64 | (amd64) Type of failure: Incorrect result | Test Case: at runtime | libraries/base/tests/enumNumeric Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D4650 Wiki Page: | -------------------------------------+------------------------------------- Comment (by sighingnow): This ticket should be fixed by Phab:D4650, by using an increment accumulator to get the next enumerated number rather than adding 1 to previous number at every run. For more related discussion about the implementation and the result the benchmark, see Phab:D4650, and `Note [Numeric Stability of Enumerating Floating Numbers]` in base/GHC/Real.hs. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/15081#comment:8> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#15081: Finite list becomes infinite after maping fractional function for high numbers -------------------------------------+------------------------------------- Reporter: Onsed | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Linux | Architecture: x86_64 | (amd64) Type of failure: Incorrect result | Test Case: at runtime | libraries/base/tests/enumNumeric Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D4650 Wiki Page: | -------------------------------------+------------------------------------- Comment (by thomie): It is still possible to get an infinite list with `enumFromThenTo` and `Double`: {{{

[9007199254740992,9007199254740993..9007199254740994]::[Double] <infinite list> }}}

Another funny result: {{{

[9007199254740993..9007199254740991]::[Double] [9.007199254740992e15,9.007199254740992e15] }}}

Notice that `from` is bigger than `to`, so one would expect an empty list as a result. Like svenpanne said in comment:5:

The underlying problem stays: You can write more precise Integers than Double can represent, and enumerating floating point numbers is inherently fragile.

-- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/15081#comment:11> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#15081: Finite list becomes infinite after maping fractional function for high numbers -------------------------------------+------------------------------------- Reporter: Onsed | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Linux | Architecture: x86_64 | (amd64) Type of failure: Incorrect result | Test Case: at runtime | libraries/base/tests/enumNumeric Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D4650 Wiki Page: | -------------------------------------+------------------------------------- Comment (by sighingnow): @thomie Thanks for your program in comment:11. However I think we have no way to improve the situation further. The double number `9007199254740992` and `9007199254740993` have same binary representation. You could check this problem with the following program. {{{#!cpp #include <stdio.h> #include <stdint.h> union double_uint64 { double x; uint64_t y; }; int main() { union double_uint64 z; z.x = 9007199254740992; printf("%lu\n", z.y); z.x = 9007199254740993; printf("%lu\n", z.y); } }}} In Haskell, we have {{{#!hs

(9007199254740993 :: Double) == (9007199254740992 :: Double) True }}}

Thus, `[9007199254740992,9007199254740993..9007199254740994]::[Double]` is equivalent to `[9007199254740992,9007199254740992..9007199254740994]::[Double]`, the later will produce infinite list. For the second example, `[9007199254740993..9007199254740991]::[Double]` should be `[]`, but the program is equivalent to {{{#!hs takeWhile (<= 9007199254740991 + 1 / 2) [9007199254740993, 9007199254740993 + 1, 9007199254740993 + 2, 9007199254740993 + 3, ... ] }}} We have: {{{#!hs

:m +Data.Binary :m +Data.ByteString.Lazy unpack $ encode ((9007199254740991 + 1 / 2) :: Double) [1,1,0,0,0,0,0,0,0,7,0,0,0,0,0,0,16,0,0,0,0,0,0,0,1] unpack $ encode ((9007199254740993) :: Double) [1,1,0,0,0,0,0,0,0,7,0,0,0,0,0,0,16,0,0,0,0,0,0,0,1] unpack $ encode ((9007199254740993 + 1) :: Double) [1,1,0,0,0,0,0,0,0,7,0,0,0,0,0,0,16,0,0,0,0,0,0,0,1] unpack $ encode ((9007199254740993 + 2) :: Double) [1,1,0,0,0,0,0,0,0,7,1,0,0,0,0,0,16,0,0,0,0,0,0,0,1] }}}

Then we get the error. A possible improvement should be replacing the `1/2` with a smaller number (such as `0.1`), but when the base number `9007199254740991` grows up, we will get into trouble again. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/15081#comment:13> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#15081: Finite list becomes infinite after maping fractional function for high numbers -------------------------------------+------------------------------------- Reporter: Onsed | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Linux | Architecture: x86_64 | (amd64) Type of failure: Incorrect result | Test Case: at runtime | libraries/base/tests/enumNumeric Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D4650 Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): I know that this is probably going to be an unpopular point-of-view but I would argue that we should consider just dropping the `Enum` instance on floating point types. As was stated earlier, enumerating floating point numbers is inherently fragile. I'm sure removing the instance would break a non-trivial amount of code, but arguably that code is broken anyways. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/15081#comment:15> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler