未加星标

Infinite Data Structures In JavaScript

字体大小 | |
[前端(javascript) 所属分类 前端(javascript) | 发布者 店小二04 | 时间 2019 | 作者 红领巾 ] 0人收藏点击收藏

Infinite Data Structures In 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 infinite concepts in a finite way. You can’t have an Array of all the positive numbers (at least not in javascript!).

What I want to introduce in this article is the idea of an Infinite List data structure, which can represent some never ending sequence, and let’s us use common operations like map and filter to modify and create new sequences.

When we want to actually use the data , we can just take some concrete amount of it.

Creating an InfiniteList

To create the kind of structure defined above, we first need some way to just describe an infinite thing without needing to actually evaluate it (which would kill the computer really fast). To do that we first need to understand 2 things:

The iterator pattern Generator functions The iteratorpattern

Let’s start with the iterator pattern first. The iterator pattern 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 .next() method. When that method is called, it returns another object with 2 keys: value and done . As we call .next(), the done property indicates whether the iterator has more values to give us, and the value is of course the value. Below is a simple iterator that returns values 0 to 3:

This kind of pattern has a first-class place in JavaScript. Arrays, Objects, Maps, and Sets can all implement the iterator pattern by conforming to an interface called Iterable .

Generator functions

Generator functions are a special kind of function in JavaScript which is declared with the function* syntax. Generator functions are used to create iterator objects (ones with a .next() method), but in much clearer and more concise way. Below is a finite generator that creates an equivalent iterator:

Here, the yield keyword is used to indicate the value that is returned every time the iterator is called. You can think of the function pausing after every yield , and picking up where it left off when the iterator ’s .next() method is called again.

All it would take to make this an infinite generator is to turn the while (x < 4) loop into a while (true) loop. For a better feel, here’s an infinite generator for the famous fibonacci sequence:

Putting ittogether

Iterators seem like a representation of something infinite because it lets us ask for the .next() element indefinitely. Furthermore, a generator 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.

But this still isn’t enough, because as powerful as generators are, they’re not really compositional . If I wanted to to create a generator where I filtered to all the fibonacci numbers that ended with a 5, I can’t easily use my existing createFibSeqIterator() to do that ― i.e. I can’t compose the idea of the original generator + some new operation on it.

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 filter , map , and take .

Infinitely Lazy

You might be puzzled when thinking about how we could implement an operation such as filter . The answer is simple: we do it lazily . Instead of actually trying to filter our list, we just make a note inside the Infinite class. Then when the user wants concretely .take() some elements of it, we can do the actual business of filter ing then.

The Infinite class gets a new transformations property, and filter creates a new Infinite with the same generator and transformations array, and pushes a transformation into the list.

We now have all the components we need now to write a .take() that will make the list concrete.

When we call .take(n) , we can create an iterator out of the generator, and then initialize a fixed-length array with n elements. This will be our concrete list. An index 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 transformations 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 concrete list, and repeat the loop. When we’ve collected n elements, we’re done and can return the concrete list.

Let’s see how that looks with the fibonacci example from before:

To implement map , we could use much the same approach as with filter . The map method itself just clones the current Infinite and adds a new transformation to the list. Inside take , it’s enough to just add an else-if inside the transformation loop.

Conclusion

In this article we’ve explored the iterator pattern and generator functions in order to build a compositional and lazily-evaluated Infinite List data structure.

The Infinite List 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 Infinite s together (like pairing every fibonacci number with a prime number, for example).

For these I created lazy-infinite , a more powerful Infinite List structure, that conforms to the Fantasy-Land specification . I’d love for you to take a look on github

本文前端(javascript)相关术语:javascript是什么意思 javascript下载 javascript权威指南 javascript基础教程 javascript 正则表达式 javascript设计模式 javascript高级程序设计 精通javascript javascript教程

分页:12
转载请注明
本文标题:Infinite Data Structures In JavaScript
本站链接:https://www.codesec.net/view/627939.html


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 前端(javascript) | 评论(0) | 阅读(19)