topic proposal: pseudorandom number generators

[rtfeldman]

We already have an implementation of PCG pseudorandom number generation in roc-random but implementing random generators in a purely functional language seems like a good fit for this book because:

• Most languages have something like a random() function which isn't pure (since it potentially returns a different answer each time it's called). Because of this, it's a common beginner surprise to discover that a random number generator in a pure FP language has to present a different API.
• There are a bunch of different PRNG algorithms out there, including ones that are simple enough that you can write the "randomness" part in a few lines of code, and then focus on the concept of how computers do "randomness" and pure FP API differences (including generating things other than numbers) for the rest of the chapter - which are the more interesting parts.
• There's a good opportunity for some "further reading" notes on why algorithms like PCG and xoroshiro provide better distributions of outputs, performance tradeoffs, entropy sources for secure randomness, etc.

[nathanielknight]

(Copied from Zulip)

I think I'm interested in contributing to the chapter on PRNGs. I don't have a lot of Roc experience, but I'm comfortable with numerical programming and technical writing.

I think something in the PCG family of RNGs would be a good one to use; it's got good numerical properties and is very compact.

In terms of content, I'd see the following sections:

• what's a PRNG and why can't a pure random function exist in Roc
• implementing a naive PRNG (e.g. RANDU) that generates random 32-bit integers and has an opaque state
• extending the PRNG to generate other kinds of integer, floats, maybe arrays (depending on how much type wizardry the reader is ready for / I'm ready to explain :sweat_smile: )
• testing the statistical properties of the naive PRNG and finding it wanting
• replacing our naive PRNG with a PCG which, thanks to our opaque state, doesn't affect the extensions we wrote 🎉