DEV Community

Cover image for JavaScript Iterators and Iterables
Adam Yeats for AppSignal

Posted on • Originally published at blog.appsignal.com

JavaScript Iterators and Iterables

Welcome to our first in-depth post on JavaScript! Here at AppSignal, we're gearing up to launch our all-new front-end monitoring solution, something we're very excited about and hope you will be, too.

Over the last few years, I've watched JavaScript evolve from somewhat of an oddity—an admittedly imperfect, but often misunderstood, scripting language for the browser—to a powerful and expressive language in its own right, deployable in multiple environments, and almost ubiquitous in today's computing landscape.

The aim of this corner of AppSignal.com is to explore this language in greater detail and uncover The Good Parts™ that make JavaScript awesome. Much like our sister blogs, Ruby Magic and Elixir Alchemy, we'll deep-dive into language features, patterns and frameworks, and share some other JavaScript insights along the way, too.

Let's get to it! But first, let's talk about Ruby.

On Linked Lists and Rubyists

In a previous edition of Ruby Magic, Jeff explored Ruby's Enumerator objects and Enumerable module. This is described by Jeff like this:

Enumeration refers to traversing over objects. In Ruby, we call an object enumerable when it describes a set of items and a method to loop over each of them.

Alright, sounds useful! I can already see plenty of reasons why you'd want this. In the aforementioned post, Jeff uses Enumerable to implement a Linked List — a common, almost evergreen data structure type that is a collection of data elements, in which each element points to the next. Each element in the list has two values, named the head and the tail. The head holds the element’s value, and the tail is a link to the rest of the list.

By ensuring that the linked list responds to the #each method, and by including the Enumerable module, it's possible to implement this data structure in Ruby without writing a whole mess of code. This got me thinking - I wonder if JavaScript can do something like that?

The answer: yes, it can! But, this wouldn't be a JavaScript blog post unless I told you that, of course, things are a little different here. Today, we're going to introduce you to JavaScript's close relative of Ruby's Enumerable class, the Iterable, and how we can leverage it to write a LinkedList class of our own.

Some of you may have never had to have implemented a Linked List before. No doubt, many of you have had to have implemented one as part of a job interview. Perhaps you, like the React team, are already using them to do non-trivial things in your codebase. The example we'll be implementing today is almost an exact port of Jeff's Ruby LinkedList class to JavaScript, which I really like due to the simplicity of the implementation. It is, perhaps, a little easier to grasp what's going on here than it would otherwise be with a "full-fat" implementation.

It doesn't catch all the edge cases, or provide a number of class methods that you might expect, but should help illustrate the idea. Consider yourself warned: you will be sent to programming hell if I catch you using this code in production, and there, no amount of random key combinations will help you exit Vim.

Okay, let's begin.

So, what's an iterator?

An iterable in JavaScript is an object that defines custom iteration behaviour via a method on itself or any of the objects in its prototype chain. You're probably already quite familiar with some of the built-in JavaScript types that are iterables, chiefly Array, Map, Set and String. In common programming parlance, we say that these types can be "looped over"; given a construct like a for loop, we can extract each value in order from the iterable and do something with it.

JavaScript provides the for...of loop for iterating over a generic iterable:

for (let value of iterable) { 
  console.log(value); 
}

You can also destructure an iterable to get a subset of its values as named variables. In the following example, a === 'a' and b === 'b':

const [a, b] = new Set(['a', 'b', 'c']);

Iterables can even be spread into an array literal, transforming your iterable into a linear array and allowing you to call array methods like .map() or .filter() on the returned value:

[...iterable].map(el => console.log(el));

So what makes an object iterable? Here's where things start to get a little more advanced.

@@iterator - The Invisible Property

In order to become an iterable, a special function must be implemented on the object itself - @@iterator. Now, to many of you out there, you would be forgiven to have been blissfully unaware that this property ever existed. It can't be accessed by calling iterable.@@iterator. It doesn't show up in a for loop or when calling Object.keys on an iterable. Often, console.log won't even reveal this property. So, where is it?

Unlike other programming languages, JavaScript doesn't (yet) have the concept of private methods or private fields on an object, but we can make a property of an object "pseudo-private" by referencing it using a special JavaScript type called a Symbol. The @@iterator property is implemented in this way: the value of the @@iterator property can only be referenced using a Symbol key that is defined as a constant on the Symbol type itself: Symbol.iterator.

Accessing it works like this:

class LinkedList {
  // ...
  [Symbol.iterator]() {}
}

// ...or using an object literal
const LinkedList = {};
LinkedList[Symbol.iterator] = function () {};

On a given class or object, where the key is Symbol.iterator, the value must be a function. In a classic, synchronous implementation of an iterator, this function returns an object (called an iterable) that implements a function called next() as a property. Let's expand a little further on our example to see what this looks like:

class LinkedList {
  // ...
  [Symbol.iterator]() {
    return {
      next() {
        return {
          value: "a value",
          done: false
        }
      }
    }
  }
}

Holy nested statements! We've managed to erect a small pyramid in our shiny new codebase, but we have successfully implemented an iterator that returns an iterable. The iterable itself returns an object with two properties: value and done. Unsurprisingly, value is the current value of the iterator, and done is a boolean value to communicate to the iterator if the sequence of values has ended. If done === true, then the value property can be emitted.

Now we know a little more about how iterators and iterables work, let's see how we can apply this knowledge to build a LinkedList.

Building the LinkedList

Let's start out by just porting Jeff's Ruby class into JavaScript, sans the #each method used to create an Enumerable:

class LinkedList {
  constructor(head = null, ...rest) {
    this.head = head;

    if (rest[0] instanceof LinkedList) {
      this.tail = rest[0];
    }
    // roughly equivalent to `rest.any?` in ruby
    else if (rest.some(el => el)) {
      this.tail = new LinkedList(...rest);
    }
    else {
      this.tail = null;
    }
  }

  add(item) {
    return new LinkedList(item, this);
  }
}

So far, so good. Using the above example, we can already create a new LinkedList, and add new items to the head of the LinkedList, using the rest and spread operator (...) to create the tail. As the first argument to the constructor, we allow anyone using our LinkedList class to pass a head as the top of the linked list, and the rest operator in the constructor is able to convert any remaining arguments that are not head, and convert them to an array. The else if statement creates a new LinkedList from this array, and continues to do so until the last item in rest belongs to the head of a LinkedList.

Now, we'll need to implement the logic to retrieve the items from the LinkedList, but I can already see a problem. If we implement an iterator, and the subsequent iterable, using the technique outlined above, then we're already deviating from Jeff's initial design quite considerably. There's a lot more code to write, and we'll need to maintain state somehow, as we need to tell the iterable that our sequence is finished by setting done to true. It's certainly possible, but I think we can come up with something more elegant.

Enter the Generator function.

Generator functions

The value we set as Symbol.iterator can also be a generator, a new type of function that was introduced with ECMAScript 2015. The easiest way to think of a generator function is a function that you can exit and return to at will, optionally returning a value with the yield keyword. Using the power of closures, we can maintain the state of the function across multiple yields and re-entries. Importantly, generator functions have the same interface as an iterable, meaning values can be retrieved in the same manner as if we had implemented the iterable ourselves.

Let's implement an iterator to get all of the values from our LinkedList using a generator function:

class LinkedList {
  // ...implementation

  *[Symbol.iterator]() {
    yield this.head;
    let next = this.tail;

    while (next !== null) {
      yield next.head;
      next = next.tail;
    }
  }
}

The Full Implementation

So, when all is said and done, this is what we end up with:

class LinkedList {
  constructor(head = null, ...rest) {
    this.head = head;

    if (rest[0] instanceof LinkedList) {
      this.tail = rest[0];
    }
    // roughly equivalent to `rest.any?` in ruby
    else if (rest.some(el => el)) {
      this.tail = new LinkedList(...rest);
    }
    else {
      this.tail = null;
    }
  }

  add(item) {
    return new LinkedList(item, this);
  }

  *[Symbol.iterator]() {
    yield this.head;
    let next = this.tail;

    while (next !== null) {
      yield next.head;
      next = next.tail;
    }
  }
}

We can then use our new LinkedList class like so:

const ll = new LinkedList(0, 1, 1, 2, 3, 5, 8, 13);

for (let value of ll) { 
  console.log(value); // output: 0, 1, 1, 2, 3, 5, 8, 13
}

const [a, b] = ll; // a = 0, b = 1

[...ll].map((num) => console.log(num)); // output: 0, 1, 1, 2, 3, 5, 8, 13

And that's it!

The first time the function is run, we yield the current head. Then, as long as there is a tail to read from, we yield the head of the list item on the tail. Once we've done that, the iterator is implicitly done. In seven lines of code, we've implemented our iterator. Awesome!

Let us know what you think about this blog, or what JavaScript wonders you'd like us to write about on Twitter @AppSignal

Top comments (1)

Collapse
 
averyferrante profile image
Joseph Avery Ferrante

Wow! A lot of great use of some of the more complex features of JavaScript. Interesting read for sure! I need to go study generators some more :)