Infinite Sequences with Generators: Grunge.js  

My introduction to javascript began, like many other people, with jQuery. For a while, javascript and the DOM seemed like the same thing. Later, as I learnt what javascript really was, I started to use and appreciate tools such as Underscore.

Soon, I discovered Lazy.js which seemed like a much better way to do things. Still, Underscore, Low-Dash and Lazy were essentially tools for dealing with existing collections. The Range Class from Ruby seemed like a breadth of fresh air in comparison.

Wouldn’t it be better if instead of storing actual values in a collection, we could just store a formula (or function) that could generate those values. Wouldn’t it be even better if we didn’t have to have a limit on the number elements we could generate.

Using my new love, Generators, I tried to solve the problem of dealing with infinite sequences with a library I call Grunge.js

Grunge.js is part Underscore, part Lazy.js and part Range Class. It doesn’t try to completely replace any of the three tools, but it does take inspiration. At the same time, it lets you accomplish certain tasks that are usually much harder, or sometimes impossible with the aforementioned libraries.

For example, Grunge.js lets you create infinite sequences, and call map, filter, and step on them without breaking a sweat. Grunge accomplishes this by using the expressive power of generators.

instead of storing values, and then mapping each of the values into a new collection the way underscore does, Grunge, merely creates a new formula (read generator function) from the old one.

As a result, dealing with complex infinite sequences such as fibonacci numbers, primes of the form 2n -1 etc. become much easier.

An example where Grunge can be useful is to generate prime numbers:

var fibinacciSquaredFiltered = Grunge(function*(){
  var first = 1;
  var second = 1;
  yield first;
  yield second;
  while(true){
    let elem = first + second;
    yield elem;
    first = second;
    second = elem;
  }
}).map(function(n){return n*n;}).filter(function(n){return n%2 !== 0;}).step(3).take(100).toArray();

Here we can feed a generator function into Grunge which generates a sequence of numbers, we can map and filter over the sequence just like a regular array, and get a certain number of values from that array.

The Goal of Grunge is to give you the basic most important set of tools needed to deal with sequences, but be as flexible as possible.

As a result a certain design decision were made:
Grunge can accept a start and step value, an existing array (a la Underscore) or a generator function that generates finite or infinite number of values.

Moreover, to keep things functional and flexible, the step method can take a number or a function. For example one way to use the step function could be to generate a set of even numbers

Grunge(2,1).step(2).

But a more interesting sequence is where you want to skip the number of elements as the last element you just received.

//sequence of natural numbers
Grunge(1,1)
  .step(function(num){return num})
  .take(10)
  .toArray();
//=> [1, 3, 7, 15, 31, 63, 127, 255, 511, 1023]

Again, such unconventional sequences are possible to write with ES5, but Grunge makes it more expressive and explicit. We are taking a set of natural numbers, and for every number x, we get we skip the next x numbers in the set. This can be taken to the extreme by chaining multiple map, filter and step functions.

//sequence of natural numbers
Grunge(1,1)
  .step(function(num){return num})
  .step(3)
  .take(5)
  .toArray();
//=> [1, 31, 511, 8191, 131071]

It’s early days for Grunge. I hope it can be a valuable tool in the future for people dealing with mathematical (and other sequences). I’m looking for ways to add functionality and improve performance.

I also plan to add tests, and make it accessible to older browsers through transpilers.

Check out the repo at https://github.com/naman34/Grunge, and help me take it further.

 
22
Kudos
 
22
Kudos

Now read this

Going semi-colon-less. OR why I’m considering the NPM Style Guide.

The semi-colons in Javascript debate is probably decades old. (Which is quite a lot considering that the language itself is less that 2 decades old) Most javascript developers are taught to always use semi-colons. The ASI in javascript... Continue →