Generators in Javascript: How to use them

Generators in Javascript: How to use them:

What Is A Generator?

From its name, a generator is a function that allows you to generate one or more values by exiting and re-entering the execution procedure whilst saving its state (context) across multiple calls. To put it in simpler words, a generator is similar to normal functions, but has the ability to continue execution on demand at the point at which it was previously terminated, simply by saving its previous state. The following flowchart illustrates the difference between a normal function and a generator function.

Syntax

As you’ve already guessed, there are some syntactic differences between a normal function and a generator:

// Normal Function
function normalFunction(params) {
  // your logic goes here
  return value;
}

/* --------------------------------- */

// Generator Function
function* generatorFunction(params) {
  // your logic
  yield value1;

  // your logic
  yield value2;

  /*
.
.
.
*/

  // your logic
  yield valueN;
}

The first noticeable difference in syntax is that a generator is declared using the function* keyword instead of function. Also, notice how we use the returnkeyword in a normal function, while we use the yield keyword in a generator function instead, respectively. The yield keyword inside the generator allows us to ‘return’ a value, terminate execution, save the state (context) of the current lexical scope and waits for the next invocation to resume execution at the last termination point.

note: In a normal function, you can only execute the return keyword once, which will return a value and terminate the function completely. In a generator, you can use the yield keyword multiple times as much as you want to ‘return’ values on consecutive calls. You can also use the return keyword inside a generator, but leave this discussion for a different day.

Invocation

Now that we’ve covered the differences in syntax between both functions, let us see how does one invoke a generator and yield its values. First, consider the following piece of code which illustrates the invocation of a normal function:

function normalFunction() {
  console.log('I have been invoked');
}

// invocation
normalFunction();

In general, you can invoke a normal function by typing the function’s signature followed by a pair of parentheses (). The previous code will output:

I have been invoked

Now let’s try to use the same procedure to invoke a generator. Inspect the following piece of code closely:

function* generatorFunction() {
  console.log('I have been invoked');
  yield 'first value';

  console.log('resuming execution');
  yield 'second value';
}

// does this invoke the generator?
generatorFunction();

What do you expect from such program? Technically, we would expect that the function is to be executed until it hits the first yield keyword. However, the output of the previous program was empty:


that is because the normal invocation syntax does not actually execute the body of the generator function. Instead, it creates a Generator Object that holds multiple properties and methods. To prove this, we can try to print out console.log(generatorFunction()) and the output should be as follows:

Object [Generator] {}

So, the question is; how do we actually yield our values from a generator?

well, there are some important methods that belong to the Generator Object that we can utilize. The first and the most important method is called next(), which, from its name, yields the next value from the defined generator. Now lets modify our previous code to actually yield our values:

function* generatorFunction() {
  console.log('I have been invoked');
  yield 'first value';

  console.log('resuming execution');
  yield 'second value';
}

// store the Generator Object in a variable
let foo = generatorFunction();

// execute until we yield the first value
console.log(foo.next());

// resume execution until we yield the second value
console.log(foo.next());

// execute until the function ends
console.log(foo.next());

the output of the previous code is:

I have been invoked
{ value: 'first value', done: false }
resuming execution
{ value: 'second value', done: false }
{ value: undefined, done: true }

Let’s inspect the output line by line. When calling the first foo.next() method, the generator began to execute until it hit the first yield keyword and stops the execution. This is reflected in the first two lines of the output. Notice how the foo.next() returned an Object instead of the actual yielded value. This Object should always contain the following properties:

  • ‘value’: which holds the current yielded value from the generator.

  • ‘done’: a boolean flag which indicates whether the generator execution has reached the end or not.

Lets move on to the second foo.next() call. As expected, the generator resumes the execution from the last termination step and executes until it hits the second yield keyword, which is reflected in the third and fourth lines of the output. Notice how the done flag is still set by false, as it did not yet reach the end of the function.

On the last foo.next() call, the function resumes execution after the second yield keyword and finds nothing to execute, which indicates that we’ve reached the end of the function. At this point, there are no more values to yield and the done flag is set to true as reflected in the last line of the output.

Now that we’ve covered the basic concepts of generators in Javascript, lets take a look at some of its useful use cases.

Use Cases

Use case 1: Mimic the range() function from Python

According to the Python docs, “the range type represents an immutable sequence of numbers and is commonly used for looping a specific number of times in for loops.” The range() function in Python usually contains the following parameters:

  • start (optional, default = 0): the first number in the sequence, inclusive.

  • end (required): the last number of the sequence, exclusive.

  • step (optional, default = 1): the difference between any two given numbers in the sequence.

Basically, the usage of the range() function in Python is shown below:

# Python code
for i range(3):
    print(i)

# output:
# 0
# 1
# 2

what we need to do is to mimic this functionality in Javascript using generators. Inspect the following piece of code closely:

/*
range function implemented in Javascript
*/
function* range({start = 0, end, step = 1}) {
  for (let i = start; i < end; i += step) yield i;
}

Lets take it step by step. Firstly, the function signature defines a generator that takes three params: startend and step, in which start and step are defaulted to 0 and 1 respectively. Moving onto the function body, it contains a basic for loop that starts iterating from start inclusive till end exclusive. Inside the loop’s scope, we yield the value i of the current number in the sequence.

Lets see it in action. The following piece of code illustrates different examples of the implemented range function:

// first example
for (let i of range({end: 4})) console.log(i);

/*
output:
0
1
2
3
*/

// second example
for (let i of range({start: 2, end: 4})) console.log(i);

/*
output:
2
3
*/

// third example
for (let i of range({start: 1, end: 8, step: 2})) console.log(i);

/*
output:
1
3
5
7
*/

Use case 2: Visualize the Bubble Sort algorithm

In this use case, we will attempt to output a step-by-step execution of the Bubble Sort algorithm on a given array to easily visualize it. Briefly, bubble sort works as follows; given an array of length n and i as the current iteration, propagate the max(array[0:n - i]) to the index n - i repeatedly until the array is sorted. The default implementation is shown below:

/*
Bubble Sort implementation in javascript
*/
function bubbleSort(arr) {
  for (let i = arr.length - 1; i >= 0; i--) {
    for (let j = 0; j  arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
      }
    }
  }

  return arr;
}

Our job is to visualize the step-by-step comparisons and swaps that are carried out throughout this algorithm. This can be easily done using generators. We simply yield the current array after each iteration in the inner loop. The new function will be as follows:

/*
visualize Bubble Sort implementation in javascript
*/
function* visualizeBubbleSort(arr) {
  for (let i = arr.length - 1; i >= 0; i--) {
    for (let j = 0; j  arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }

      yield arr;
    }
  }
}

This will yield the array for each iteration in the inner loop, showing us the current state of the array. Consider the following example:

let inputArray = [40, 30, 2, 20];
let currentStep = 1;
for (let val of visualizeBubbleSort(inputArray)) {
  console.log(`step #${currentStep}: [${val}]`);
  currentStep++;
}

The output of the previous program will be:

step #1: [30,40,2,20]
step #2: [30,2,40,20]
step #3: [30,2,20,40]
step #4: [2,30,20,40]
step #5: [2,20,30,40]
step #6: [2,20,30,40]

we can clearly see what is happening throughout the algorithm thanks to the implemented generator:

  • step 1 -> swap 40 with 30

  • step 2 -> swap 40 with 2

  • step 3 -> swap 40 with 20

  • step 4 -> swap 30 with 2

  • step 5 -> swap 30 with 20

  • step 6 -> do not swap anything, array is sorted

Note: this technique can be used to visualize any given algorithm easily. It can be very helpful sometimes.

Use case 3: Generate distinct random numbers on demand

In this use case, we will try to generate a series of distinct random numbers using generators. First, we would put some constraints on the inputs and outputs as follows:

  • The function should only generate positive integers.

  • The function should take a parameter limit, which determines the maximum number of generated integers as well as the largest possible generated integer.

  • The function should have a way to store the valid pool of integers to choose from.

Following the previous constrains carefully, we can implement this functionality using generators easily:

/*
distinctRandom implementation in js */
function* distinctRandom({limit = 10}) {
  // we create an array that contains all numbers in range [0:limit)
  // this is our initial pool of numbers to choose from
  const availableValues = [...new Array(limit)].map((val, index) => index);

  // we repeatedly loop until the available pool of numbers is empty
  while (availableValues.length !== 0) {
    // generate a random index in range [0: availableValues.length)
    // then, yield the number that is present at the chosen index
    // Finally, remove the picked item from the pool of available numbers
    const currentRandom = Math.floor(Math.random() * availableValues.length);
    yield availableValues[currentRandom];
    availableValues.splice(currentRandom, 1);
  }
}

Briefly, the previous generator tries to maintain a pool of available integers to choose from. In each iteration, we randomly choose a number from this pool, then yield it and remove it from the valid pool. Theoretically, the maximum number of generated integers should be equal to limit and all generated integers must be distinct. We can easily proof this by exhausting the implemented generator until the end of execution:

// we set the limit to 8
for (const val of distinctRandom({limit: 8})) {
  console.log(val);
}

/*
sample output:
3
7
5
2
4
0
1
6
*/

Closing Note

Generators are a great addition to ES6 which provides a solution for multiple problems and use cases. You can use them anywhere for sure, but I would suggest looking into alternative solutions for the problem in-hand before settling for a generator, as they can introduce more complexity to your code as well as they can be hard to debug at times. 

from Tumblr https://generouspiratequeen.tumblr.com/post/642357413418336256

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s