Comments (7)
(FWIW, I think the comment about hard depth limit is something worthy of being in the package documentation. It solved my problem.)
from random.
Right now you have a 50% of terminating and a 50% of continuing. Continuing means three chances to continue again. So I think the expected value for the depth is just really high.
I am having trouble calculating the expected value of the depth, but I think that's the next step before saying this is an issue with the package.
In the meantime, my first instinct is to switch from uniform
to weighted
and make termination more likely. Non-termination is still possible though, so for a 100% reliable fix, you'd want to put in a hard depth limit. So you pass maxDepth
in the generator, and on each recursion you give maxDepth - 1
. If maxDepth <= 0
then you always terminate.
P.S. I am struggling because the probabilities get real complicated in the map3
case:
- 1/8 chance of terminating
- 3/8 chance of starting one extra level
- 3/8 chance of starting two extra levels
- 1/8 chance of starting three extra levels
Putting together two uniform distributions does not result in a uniform distribution, but I do not recall enough probability theory to figure it out. Would love to see someone figure it out though!
from random.
@evancz I can try and dust off my math to compute the probabilities 🙂 But I wonder, do you consider this a bug, or just a thing that would happen every now and then? Is this eg. solvable with some kind of trampolining?
from random.
It's pretty easy to use andThen
to request a limitless amount of random numbers:
endless : Generator (List Int)
endless =
Random.int 0 20
|> Random.andThen (\x -> Random.map (\xs -> x :: xs) endless)
What we're dealing with here though is a computation that might terminate quickly, or might balloon so much that termination becomes increasingly improbable, though never impossible.
Either way, I think we're up against the halting problem, so that's not something code can solve. We should advise people to use a hard depth limit, or perhaps a 1/depth
chance of recursing. We can improve the documentation when the error happens, perhaps pointing to a markdown page that explains the issue in depth (we already have some of these).
from random.
In terms of documenting this, where in the documentation should such a note be? Why would someone with this problem be reading the docs for map3
or uniform
when they run into this? Or is there some generator that they are guaranteed to have read in full before having this problem?
The root issue is that recursion may not terminate, which is not in the API of this library directly. It's just a thing about recursion. So it's not clear to me that this kind of thing can/should be documented in this library.
from random.
I was thinking about putting the note next to andThen
. Just a reminder about the possibility of infinite recursion. Other functions in the module probably don't have that ability to recurse infinitely on their own?
from random.
I agree, it belongs next to andThen
. I can confirm that none of the map
s can explode on their own.
Perhaps something like:
A word of caution: It's surprisingly easy to use this function to make a generator that requests an infinite amount of randomness. This will crash your program! Be sure there is some kind of branching that will guarantee you stop eventually. A common way to do this is with a depth limit, which is a number that only gets smaller as you ask for more randomness, and you stop once it gets small enough.
from random.
Related Issues (11)
- Rename Generator to Random HOT 2
- Feature Request: Random.generateTask
- broken link in README HOT 1
- How can I encode a seed as JSON? HOT 10
- Request: use better source of entropy HOT 3
- Why are the docs not updated? HOT 1
- `Random.float` lacks sanitization of input and emits invalid numbers when bounds are swapped
- Provide access to construct a generator from `Seed -> (a, Seed)`
- ‘Working example’ link in README is broken HOT 1
- Another broken link, this one in Random module docs HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from random.