Infinite Data Structures In JavaScript

Languages like Haskell are able to deal directly with Infinite Lists, but can that ability be brought to the world of JavaScript? https://codepen.io/fstokesman/pen/maBBQG In the real world we deal with “infinite” ideas all the time. All the positive numbers is an example of an infinite concept we wouldn’t bat an eye at. But typically when we are programming we have to think of these concepts in a way. You can’t have of all the positive numbers (at least not in JavaScript!). infinite finite an Array What I want to introduce in this article is the idea of an data structure, which can represent some never ending sequence, and let’s us use common operations like and to modify and create new sequences. Infinite List map filter When we want to , we can just some concrete amount of it. actually use the data take Creating an Infinite List To create the kind of structure defined above, we first need some way to just an infinite thing without needing to actually evaluate it (which would kill the computer fast). To do that we first need to understand 2 things: describe really The iterator pattern functions Generator The iterator pattern Let’s start with the first. The is a kind of design pattern where you can produce a lot of values, one at a time. It’s basically just an object with a method. When that method is called, it returns another object with 2 keys: and . As we call the property indicates whether the iterator has more values to give us, and the is of course the value. Below is a simple iterator that returns values 0 to 3: iterator pattern iterator pattern .next() value done .next(), done value This kind of pattern has a place in JavaScript. and can all implement the by conforming to an interface called . first-class Arrays, Objects, Maps, Sets iterator pattern Iterable Generator functions Generator functions are a special kind of function in JavaScript which is declared with the syntax. Generator functions are used to create objects (ones with a method), but in much clearer and more concise way. Below is a generator that creates an equivalent iterator: function* iterator .next() finite Here, the keyword is used to indicate the value that is returned every time the iterator is called. You can think of the function after every , and picking up where it left off when the ’s method is called again. yield pausing yield iterator .next() All it would take to make this an generator is to turn the loop into a loop. For a better feel, here’s an generator for the famous fibonacci sequence: infinite while (x < 4) while (true) infinite Putting it together Iterators seem like a representation of something infinite because it lets us ask for the element indefinitely. Furthermore, a seems like a good way to specify the iterator, because we can write succinct algorithms for infinite series without the boilerplate of manually crafting iterators. .next() generator But this still isn’t enough, because as powerful as are, they’re not really . If I wanted to create a generator where I to all the fibonacci numbers that ended with a 5, I can’t easily use my existing to do that — i.e. I can’t compose the idea of the + on it. generators compositional filtered createFibSeqIterator() original generator some new operation To remedy this, we first need to encapsulate the generator into a data type, which we can do with a class: It’s on this class that we will implement our operations like , , and . filter map take Infinitely Lazy You might be puzzled when thinking about how we could implement an operation such as . The answer is simple: we do it . Instead of actually trying to filter our list, we just make a note inside the class. Then when the user wants concretely some elements of it, we can do the actual business of ** **ing then. filter lazily Infinite .take() filter The Infinite class gets a new property, and creates a new Infinite with the same generator and array, and pushes a into the list. transformations filter transformations transformation We now have all the components we need now to write a that will make the list concrete. .take() When we call , we can create an iterator out of the generator, and then initialize a fixed-length array with elements. This will be our list. An variable can be used to keep track of how many concrete values we’ve collected so far. Using a while loop, we can get a value out of the iterator, and then run our list of on it. If one of those transformations is a filter, and it doesn’t pass the test, we simply don’t add it to our list, and repeat the loop. When we’ve collected elements, we’re done and can return the concrete list. .take(n) n concrete index transformations concrete n Let’s see how that looks with the fibonacci example from before: To implement , we could use much the same approach as with . The map method itself just clones the current and adds a new transformation to the list. Inside , it’s enough to just add an inside the transformation loop. map filter Infinite take else-if Conclusion In this article we’ve explored the and in order to build a and data structure. iterator pattern generator functions compositional lazily-evaluated Infinite List The in this article is a bit limited however, because it lacks some operations that would make it truly useful, like a map implementation, dependent filtering, or the ability to combine s together (like pairing every fibonacci number with a prime number, for example). Infinite List Infinite For these I created a more powerful Infinite List structure, that conforms to the . , or to give it a try in your next project with lazy-infinite , Fantasy-Land specification I’d love for you to take a look on github npm i lazy-infinite If you’ve enjoyed this delve into Infinite Data Structures, , and considering giving this article a 👏. Hit me up on twitter @fstokesman