Simplify iteration of custom data structures in TypeScript with iterators

Rares Matei
InstructorRares Matei

Share this video with your friends

Send Tweet
Published 4 years ago
Updated 4 years ago

Traversing items of custom data structures, like trees or linked lists, require knowledge of how that data structure is built. That can lead to problems, as faulty iteration strategies might not visit all the items, or they might not know when they've finished visiting all of them. In this lesson, we're going to look at how TypeScript supports us in building custom ES6 iterators that can be then used by a simple "for..of" loop to ensure we provide an easy to use and reliable API for other developers to traverse our data structures.

Instructor: [00:00] Now we have all of our types ready for building this time travel debugger. However, we still have this somewhat messy implementation of consuming that API. Developers still have to work directly with this action node interface and they have to know that it has a previous link and also a next link.

[00:18] They also have to know that if they want to access the underlying action, they have to use the value property. Finally, they need to know that they have to stop eventually and they need to check for undefined in case we've reached the end of the list.

[00:32] We can find ourselves in a similar situation with arrays. One way of traversing an array would be to store an initial index and then each time we need to know to query the array by that index. Then we have to make sure to increment the index for the next iteration. Then finally we have to make sure to stop eventually once we've reached the end of the list.

[00:51] Thankfully, we don't always have to care about all of that. We can just use the for of loop which will abstract away all of these nasty details away from us. It's going to give us access to this variable which will contain each element on each iteration.

[01:05] To make my actions list behave similar to an array, I'm going to create a class called backwards action iterator that implements the iterable iterator interface. I'll pass in my action type as the generic parameter.

[01:19] What this means is that my iterator will give us actions on each run of the loop, similar to how the array we looked at earlier gave us numbers. I'm going to let Typescript do its magic and implement this for me. I'm just going to format this a bit and I'm going to remove all of the optionals.

[01:36] The question that's probably on everyone's mind, where did this type come from? Since we're targeting ES6, it just came with our default Typescript installation, so we don't need to install any external packages.

[01:47] We get it by default because both parts of this interface, the iterable and the iterator, aren't native JavaScript protocols part of the ES6 pack. All we're doing here is we're just enriching an already existing and predocumented JavaScript pattern with types.

[02:06] If we look at the first part of this, the iterable protocol says that our object must have a method with the name symbol dot iterator, which it does. This must also return an iterable iterator. Since our class already implements this, I can just return this from here.

[02:24] The second part of this interface, the iterator, the JavaScript protocol says that it must implement a next method which is going to give us results every time it's called. Once our for of loop will get an instance of this iterator by just calling this method, then it's going to attempt to call the next method for each item.

[02:45] The next method will do two things. It's going to be responsible for knowing how to move through each item in the list. Number two, it's going to return each one of those items every time it's called. The way we traverse a link list is we need an item from which to start. I'll just pass that in to the constructor.

[03:09] This will be the initial action from which we want to travel backwards or forwards in time. It needs to be the full node because it needs references to its previous or forwards neighbor. Back in my next method I'll first need to store a reference to my current node and then I'll need to check if the current node I'm looking at is defined and actually has a value.

[03:32] If it doesn't, that means we've reached the end of the chain of my link list. Either we got to the beginning if we're traveling backwards or we got to the last action that was emitted if we're traveling forward.

[03:45] The ES6 iterator protocol says that when we reach the end, we need to return an object with a null value and a done property of true. If it is defined however, we first need to do this. We move the current node pointer back one action to the previous one.

[04:04] The next time the next method runs, the current node, instead of pointing to the one we're looking at now, it's going to point at its previous sibling. Then because it has a value, we actually need to return a node.

[04:17] Based on what the JavaScript protocol says, we again need to return an object with the value, our node's current value, and a done property of false. This actually tells it that it needs to call the next method again because there might be some more nodes.

[04:31] By doing this here we'll actually get the underlying action directly without us having to know that we need to call the value on it. Let's go ahead and try this. I've defined four actions here. The intent is for them to be dispatched in this order.

[04:45] We're first going to log in, then we're going to load some posts, then we're going to display those posts, and then we're going to log out. Here I'm wrapping each one of them into a list node so that it's going to be the first track, the order in which they were dispatched.

[04:58] If we want to try to go backwards in time, we're first going to need to create a backwards action list. This is going to be an instance of my backwards action iterator. We're going to initialize it with the last node in my actions list, because we want to go backwards in time, so we need to start with the last one.

[05:20] Now all we need to do is just create the for of loop. I'm going to take each action one by one and I'm going to go for my backwards action list. On each iteration I just want to print out the type of the action. Let's try this. I'll open up the console and I'll first need to invoke the Typescript compiler on it.

[05:41] You'll notice we're targeting ES6 because the iterators are an ES6 feature. Now we're just going to execute the file. As expected, we first get the log out action, which is our last action in the list. Then we get the display posts, then loading of posts, and then finally the first action which is log in.

[06:00] Typescript is also able to infer the type of each item that was returned in here. If I hover over it, you're going to notice that it's of type action. I know this looks like a lot of code. For such a simple example, it definitely is.

[06:14] Now that we've built our iterator, it can start to be used in different places in our app. Every time it's used the developer won't have to worry about knowing how to traverse a link list, having to call previous and next on each item, knowing when to stop the iteration, or how to actually unpack an item by calling value on it.

[06:33] They can just keep using the familiar for of mechanism they're familiar with from arrays. Typescript fully supports us in our journey to build these iterators with the built in ES6 types.

- -
- -
~ 3 years ago

Interesting lesson!

Avi Aryan
Avi Aryan
~ 3 years ago

This is such a solid course, thank you Rares.

~ 3 years ago

So very well explained. Many thanks.

~ a year ago

I got this error Type 'null' is not assignable to type 'ListNode<Action>', but it worked for you, why?

~ 6 months ago

"I got this error Type 'null' is not assignable to type 'ListNode<Action>', but it worked for you, why?"

You have to turn off strictNullChecks in your tsconfig.