Join egghead, unlock knowledge.

Want more egghead?

This lesson is for members. Join us? Get access to all 3,000+ tutorials + a community with expert developers around the world.

Unlock This Lesson
1×
Become a member
to unlock all features

Level Up!

Access all courses & lessons on egghead today and lock-in your price for life.

Autoplay

    Generate Randomness Using the State ADT

    Ian Hofmann-HicksIan Hofmann-Hicks
    javascriptJavaScript

    While the Math.random function that ships with JavaScript is super handy to have, it can make functional programmers cringe due to its, well randomness. We have no control over how the RNG is seeded, which removes all purity from the function and makes it difficult to test without mocking or implementing features like replays or time travel. We can take advantage of the nature of the State ADT by implementing a Linear Congruential Generator and keeping track of our seed in the state.

    Code

    Code

    Become a Member to view code

    You must be a Member to view code

    Access all courses and lessons, track your progress, gain confidence and expertise.

    Become a Member
    and unlock code for this lesson
    Transcript

    Transcript

    Instructor: 00:00 There are three steps to generating a pseudorandom number with the state ADT. First you generate a seed, then update the seed with a new seed, and finally provide a value with good statistical pseudorandomness. We store our seed in our initial state under the seed attribute.

    00:15 Let's go about implementing this first step. Over in our random model, we'll leverage this nextSeed function that takes an integer to an integer. It takes a seed as its input using the ANSI C values for a linear congruential generator.

    00:29 We'll use this function downstairs to calculate our next seed with a transaction that we call getNextSeed, taking a unit as its input. We define getNextSeed as a function that takes a unit to a state appState of integer.

    00:48 To implement, we reach for state's getConstruction function, passing it a function that destructures seed off of our state, passing it into nextSeed, placing the result into our resultant.

    01:00 Let's import this into our index file to see what we're working with. We just pluck getNextSeed off of our module at data model random. Now we can log out of the result of calling it, wrapped in our log function, to see we get back expected state instance.

    01:16 To check the resultant, we use evalWith, passing it our initial state, getting back this new seed just itching to be used for our next step, where we update our state with the new value.

    01:27 Over in our random model, we need a transaction that will take a given integer and update the seed attribute in our state, which will call updateSeed, taking a seed as its input.

    01:38 We define updateSeed as a function that takes an integer to a state appState of unit. Using the state's modifyConstruction function, we pass it a preloaded Crocks assoc function that will replace the seed with our input.

    01:54 Leaping back into our index file, we want to replace getNextSeed up top with updateSeed, as well as down below, calling it with a value of 42, and then take a peek at the state by using execWith to find 42 as our new seed, allowing us to seed like a 1337 h4x0r.

    02:13 That just leaves our final bit to transform this seed into a workable value. In our random model, we have this value function taking an integer to a number, converting the first 16 bits of our seed into a value between zero and one.

    02:26 We'll build another transaction that updates the seed in the state and deposits our value in the resultant at the same time and call it nextValue, defining this transition as a function that takes an integer to a state appState of number.

    02:43 To avoid playing leapfrog in a chain of fools, we reach for the converge combinator. Taking advantage of state's applicative nature, we'll merge with liftA2 loaded with the constant combinator, which resolves our final resultant to the resultant of our left function.

    02:59 Because we need a state for liftA2, we'll turn our value function into a Kleisli, using liftState loaded with value as our left function. On the right side, we use the updateSeed transaction we built moments ago.

    03:12 Now, in our index file, we just casually rid ourselves of updateSeed and replace with nextValue in our import. Then do the same down below, calling our nextValue with the large hexadecimal bad cat.

    03:25 Taking notice of our updated seed and evalWith shows us our expected float in our resultant. We now have everything in place to create a single transaction from these three steps.

    03:37 Back in our random model, we'll create a transaction with the sole purpose of combining our three steps that we simply call random, which we define as a Kleisli arrow that takes a unit to a state appState of number.

    03:52 We implement with the Crocks composeK helper function to sequentially chain our nextValue transition after our first step, getNextSeed, to generate the new seed. Now, for the moment we've all been waiting for, we'll import our hot, new random function into our index and hop along downstairs to call it with unit as our input, seeing our float in the resultant.

    04:17 With a call to execWith, we see that our original seed has been replaced. Furthermore, we can chain random as many times as we need, updating our seed to the next seed in the sequence each time.

    04:28 Not only is the seed updated, but we also get a new float with every call in our resultant. We get the same value every time we pull, all based on the initial value we seed our generator with.

    04:40 By replacing our seed to be the result of Date.now, we see that we still can get something that feels like Math.random, except we are in control of how the sequence is seeded. Sure, floats are great and all, but an integer within a range would be better.

    04:55 Tucked away in our random model, we have this normalize function that takes a pair of integers to a function that takes a number to an integer. It takes a min specifying the smallest value and max that specifies the length of the range, much like an array.

    05:10 It then returns a function that will provide an integer within our range from a given float X. We can now use this little helper to create a between transaction to provide us with pseudorandom integers within a range, taking a pair of min and max values as its input.

    05:26 We define our brand-new between transaction as a function that'll take a pair or a two tuple of integers to an instance of state appState of integer. Taking full advantage of the functorality of state, we call random and then map our normalize function loaded with our min and max values, which deposits our random integer into the resultant.

    05:50 Let's have a little play with our new friend to get a feel for how it behaves, swapping out random for between in our import and of course updating our log call to instead call between with a starting smallest value of zero and a length of one, observing we only get zero back. A length of two gives us values zero and one.

    06:10 By increasing our length to 200, we can randomly pull values between a range of 0and 199. Great for picking things out of arrays. We also see that the seed in our state is updated every time we save, working as expected, making things like time travel and replays easy-peasy.

    Discuss

    Discuss