GHC issueshttps://gitlab.haskell.org/ghc/ghc/-/issues2019-07-07T19:00:04Zhttps://gitlab.haskell.org/ghc/ghc/-/issues/4218System.Random is way too lazy2019-07-07T19:00:04ZEyalLotemSystem.Random is way too lazyrandomRs is too lazy, generates lists of large lazy-state thunks, rather than lists of strict values.
Test program is attached.
Also, randomIO is too lazy, and builds up huge thunks. Using (randomIO \>\>= evaluate) is fine, however.
F...randomRs is too lazy, generates lists of large lazy-state thunks, rather than lists of strict values.
Test program is attached.
Also, randomIO is too lazy, and builds up huge thunks. Using (randomIO \>\>= evaluate) is fine, however.
Fails with stack overflow:
```
rs <- replicateM 1000000 evaluate :: IO [Int]
print $ last rs
```
Works:
```
rs <- replicateM 1000000 (evaluate =<< randomIO) :: IO [Int]
print $ last rs
```7.10.1https://gitlab.haskell.org/ghc/ghc/-/issues/5280System.Random commits (rand `mod` base) error.2019-07-07T18:56:05ZrrnewtonSystem.Random commits (rand `mod` base) error.You have probably at some point come across the C code "`rand() % base`"'. It is very intuitive, but unfortunately creates non-uniform random numbers, which is easy to see if you imagine `rand()` producing numbers in say `[0,15)` and bas...You have probably at some point come across the C code "`rand() % base`"'. It is very intuitive, but unfortunately creates non-uniform random numbers, which is easy to see if you imagine `rand()` producing numbers in say `[0,15)` and base being `10`.
In the function `System.Random.randomIvalInteger` you can see the same thing happening.
The only way I know how to deal with it and generate uniform integers within a range is to artificially restrict the range of the source of randomness to be a multiple of the desired base. It can be done simply by throwing out some random results.
This strategy appears to be used by GMP's mpz_urandomm function:
> http://gmplib.org/manual/Integer-Random-Numbers.html\#Integer-Random-Numbers
The file `urandomm.c` has the code.
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 7.0.3 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"System.Random commits (rand `mod` base) error.","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"OwnedBy","contents":"rrnewton"},"version":"7.0.3","keywords":["base","mod","random"],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"You have probably at some point come across the C code \"{{{rand() % base}}}\"'. It is very intuitive, but unfortunately creates non-uniform random numbers, which is easy to see if you imagine {{{rand()}}} producing numbers in say `[0,15)` and base being `10`.\r\n\r\nIn the function `System.Random.randomIvalInteger` you can see the same thing happening. \r\n\r\nThe only way I know how to deal with it and generate uniform integers within a range is to artificially restrict the range of the source of randomness to be a multiple of the desired base. It can be done simply by throwing out some random results.\r\n\r\nThis strategy appears to be used by GMP's mpz_urandomm function:\r\n\r\n http://gmplib.org/manual/Integer-Random-Numbers.html#Integer-Random-Numbers\r\n\r\nThe file `urandomm.c` has the code.\r\n","type_of_failure":"OtherFailure","blocking":[]} -->7.10.1rrnewtonrrnewtonhttps://gitlab.haskell.org/ghc/ghc/-/issues/7379rangeTest test fails on Windows2019-07-07T18:50:01ZIan Lynagh <igloo@earth.li>rangeTest test fails on WindowsThe `CWchar` type on Win32 is unsigned:
```
Prelude> minBound :: Foreign.C.Types.CWchar
0
Prelude> (-100) :: Foreign.C.Types.CWchar
65436
```
This causes the `rangeTest` test to fail:
```
CWchar R:
Stderr:
rangeTest.exe: broke lower...The `CWchar` type on Win32 is unsigned:
```
Prelude> minBound :: Foreign.C.Types.CWchar
0
Prelude> (-100) :: Foreign.C.Types.CWchar
65436
```
This causes the `rangeTest` test to fail:
```
CWchar R:
Stderr:
rangeTest.exe: broke lower bound: 100
```
Ryan, could you take a look please?
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ------------------ |
| Version | 7.6.1 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | rrnewton@gmail.com |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"rangeTest test fails on Windows","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"7.6.1","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":["rrnewton@gmail.com"],"type":"Bug","description":"The `CWchar` type on Win32 is unsigned:\r\n{{{\r\nPrelude> minBound :: Foreign.C.Types.CWchar\r\n0\r\nPrelude> (-100) :: Foreign.C.Types.CWchar\r\n65436\r\n}}}\r\nThis causes the `rangeTest` test to fail:\r\n{{{\r\nCWchar R: \r\nStderr:\r\nrangeTest.exe: broke lower bound: 100\r\n}}}\r\n\r\nRyan, could you take a look please?\r\n","type_of_failure":"OtherFailure","blocking":[]} -->7.10.1https://gitlab.haskell.org/ghc/ghc/-/issues/7936newStdGen leaks memory when result is not used2019-07-07T18:47:23ZryantrinklenewStdGen leaks memory when result is not usedWhen newStdGen is invoked repeatedly without making any use of the resulting StdGen values, it leaks memory, as in the following:
```
-- Leaks memory
main = forever newStdGen
```
When a random number produced by the result is evaluated...When newStdGen is invoked repeatedly without making any use of the resulting StdGen values, it leaks memory, as in the following:
```
-- Leaks memory
main = forever newStdGen
```
When a random number produced by the result is evaluated, no leak occurs:
```
-- Does not leak memory
main = forever $ do
r <- newStdGen
evaluate $ fst $ next r
```
However, evaluating the result itself is not sufficient to eliminate the leak:
```
-- Leaks memory
main = forever $ do
r <- newStdGen
evaluate r
```
After sufficient iterations of newStdGen, subsequent use will cause a stack overflow:
```
-- Causes stack overflow
main = do
replicateM 1000000 newStdGen
r <- newStdGen
evaluate $ fst $ next r
```
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 7.6.3 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"newStdGen leaks memory when result is not used","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"7.6.3","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"When newStdGen is invoked repeatedly without making any use of the resulting StdGen values, it leaks memory, as in the following:\r\n\r\n{{{\r\n-- Leaks memory\r\nmain = forever newStdGen\r\n}}}\r\n\r\nWhen a random number produced by the result is evaluated, no leak occurs:\r\n\r\n{{{\r\n-- Does not leak memory\r\nmain = forever $ do\r\n r <- newStdGen\r\n evaluate $ fst $ next r\r\n}}}\r\n\r\nHowever, evaluating the result itself is not sufficient to eliminate the leak:\r\n\r\n{{{\r\n-- Leaks memory\r\nmain = forever $ do\r\n r <- newStdGen\r\n evaluate r\r\n}}}\r\n\r\nAfter sufficient iterations of newStdGen, subsequent use will cause a stack overflow:\r\n\r\n{{{\r\n-- Causes stack overflow\r\nmain = do\r\n replicateM 1000000 newStdGen\r\n r <- newStdGen\r\n evaluate $ fst $ next r\r\n}}}","type_of_failure":"OtherFailure","blocking":[]} -->7.10.1Edward KmettEdward Kmetthttps://gitlab.haskell.org/ghc/ghc/-/issues/8704Use GHC.Exts.build in randoms, randomRs to achieve fusion2019-07-07T18:43:53Zion1Use GHC.Exts.build in randoms, randomRs to achieve fusionrandoms, randomRs could take advantage of list fusion.
A commit is attached for consideration.
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Ver...randoms, randomRs could take advantage of list fusion.
A commit is attached for consideration.
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 7.6.3 |
| Type | FeatureRequest |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"Use GHC.Exts.build in randoms, randomRs to achieve fusion","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"7.6.3","keywords":["fusion"],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"FeatureRequest","description":"randoms, randomRs could take advantage of list fusion.\r\n\r\nA commit is attached for consideration.","type_of_failure":"OtherFailure","blocking":[]} -->7.10.1rrnewtonrrnewtonhttps://gitlab.haskell.org/ghc/ghc/-/issues/8899StdGen does not generate 02019-07-07T18:42:54ZnovadenizenStdGen does not generate 0`genRange` for `StdGen` returns `(0,2147483562)`. However, as far as I can tell, `StdGen` doesn't generate 0.
This code performs 200 billion iterations of `next` on a `StdGen`. I ran it and it output `Nothing`. The probability that no 0...`genRange` for `StdGen` returns `(0,2147483562)`. However, as far as I can tell, `StdGen` doesn't generate 0.
This code performs 200 billion iterations of `next` on a `StdGen`. I ran it and it output `Nothing`. The probability that no 0 was generated by chance is approximately *e\^-200/2.147\^* =\~ *10\^-40\^*.
`
import System.Random
import Data.Int
find0 :: StdGen -> Int64 -> Maybe Int64
find0 g0 n0 = aux g0 n0 where
aux _ 0 = Nothing
aux g r = let (v,g') = next g in
if v == 0 then Just (n0 - r + 1)
else aux g' (r-1)
main :: IO ()
main = print $ find0 (mkStdGen 1234) 200000000000
`
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 7.9 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"StdGen does not generate 0","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"7.9","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"`genRange` for `StdGen` returns `(0,2147483562)`. However, as far as I can tell, `StdGen` doesn't generate 0.\r\n\r\nThis code performs 200 billion iterations of `next` on a `StdGen`. I ran it and it output `Nothing`. The probability that no 0 was generated by chance is approximately ''e^-200/2.147^'' =~ ''10^-40^''.\r\n\r\n{{{#!haskell\r\nimport System.Random\r\nimport Data.Int\r\n\r\nfind0 :: StdGen -> Int64 -> Maybe Int64\r\nfind0 g0 n0 = aux g0 n0 where\r\n aux _ 0 = Nothing\r\n aux g r = let (v,g') = next g in\r\n if v == 0 then Just (n0 - r + 1)\r\n else aux g' (r-1)\r\n\r\nmain :: IO ()\r\nmain = print $ find0 (mkStdGen 1234) 200000000000\r\n }}}\r\n","type_of_failure":"OtherFailure","blocking":[]} -->7.10.1Edward KmettEdward Kmett