Writing LINQ in JavaScript from scratch

What for


Once, while developing a graph component for a web browser, we ran into the problem of processing sequences in JavaScript.

C # developers have been using extension methods for sequence processing for many years. And although this technology is not without pitfalls, it allows in many cases to avoid the tedious writing of routine code for processing arrays, lists, etc.

Naturally, I would like to have similar features in JavaScript.

At the moment, there are many LINQ implementations for JavaScript, for example, linq.js , $ linq. These implementations provide a wide range of features comparable to a C # implementation. The flip side is the considerable size of the code from which only a small part can be used in a particular application. For example, we only need the distinct function, and we are forced to add kilobytes of third-party library code.

Again, it’s curious to figure out how a particular library works, and disassembling the source code of a large library is often tedious. Or in our case, we already have our own library for JavaScript and we just want to complement it compactly with the functionality of working with sequences.

How JavaScript is suitable for implementation


Let's decide on the JavaScript elements that are necessary for the implementation of the plan. We have arrays, there are lambda functions, there are objects, inheritance is possible with some caveats. We want to perform operations represented by lambda functions on the data contained in arrays and we want to group these operations in an object. Everything is good.

Let's try it yourself


Let's start by defining the necessary entities.
Obviously, the iterator is the most basic object for working with sequences. All that is required of him is three methods:
  • moveNext () moves the pointer to the next element and returns true if successful and false if there is no next element (end of sequence has been reached);
  • current () returns the current element or null if there is no such element (the end of the sequence is reached);
  • reset () moves the pointer to the first element of the sequence.

So, we need a method that constructs an iterator from a base sequence (for example, from a JS array).

Next, we need an object that will contain a set of methods for working with sets (where, select, etc.). Since I wanted to have a name that reflects the essence of the functional rather than “hint” at analogues, the word Walkable was chosen (the essence is such that you can “walk” / iterate over its elements). Each method of this object must also return a Walkable object in order to support the ability to combine several calls in one chain (in other words, so that the result of the previous method can be transmitted to the next one).

Secondly, we need a data source. I would not want to be limited to the built-in JS array as the only source. This is where the above iterator comes in handy. All we need from the sequence is the only method that returns an iterator (of course, each time a new instance so that it can be used without changing the state of other iterators). In the next step, you can “mix” Walkable methods onto such an object, and as a result, you can call any Walkable methods on the result and cascade them into arbitrary chains.

We illustrate the theory with code. Here is a method that creates a Walkable from a JS array:

var arrayWalkable = function(arr) {
      var walker = function() { .// внутрення функция-конструктор итератора
        var idx = -1; // состояние итератора
        // далее классические методы итератора
        this.reset = function() { idx = -1; };
        this.moveNext = function() { return (++idx < arr.length); };
        this.current = function() { return (idx < 0 || idx >= arr.length) ? null : arr[idx]; }; 
      };
      // создаём обёртку над массивом, возвращающую итератор
      var walkable = { getWalker: function() { return new walker(); },};
      // расширяем обёртку методами объекта Walkable
      // WAVE.extend - базовая функция нашей библиотеки, при желании можно реализовать/скопировать         
      //свою
      WAVE.extend(walkable, WAVE.Walkable); 
      return walkable;
    }

Next, let's take a look at the Walkable object itself. It must contain methods for working with sequences, each of which must return a new Walkable object in its turn.

So, we implement the Walkable object and the most popular where method. Since we chose walkable as the name, we call all extension methods with the letter “w”:

wWhere: function(filter) {
                	var srcWalkable = this;
                	var walkable = {
                  	  getWalker: function() {
                      	    var walker = srcWalkable.getWalker();
                    	    return {
                      	      reset: function() { walker.reset(); },
                      	      moveNext: function() {
                        	  while (walker.moveNext()) {
                          	    var has = filter(walker.current());
                          	    if (has) return true;
                        	  }
                        	  return false;
                      	      },
                      	      current: function() { return walker.current(); }
                    	    };
                  	  }  
                	}
                	WAVE.extend(walkable, WAVE.Walkable);
                	return walkable;
    	}, //wWhere

As an argument for wWhere, we take the filter function, which in turn takes an element of the sequence as an input and returns true or false (whether or not to include the element in the result). Next, remember this in the srcWalkable variable (classic JS trick).

In the next step, by analogy with the arrayWalkable method described above, we define the base walkable object with the key getWalker method. With each call, we get a new iterator of the current object, so as not to affect other iterators. And return the object.

Then we redefine the iterator methods in accordance with the logic of the where operation:
  • reset: simply calls reset the source of the sequence (for example, it may be an object produced by the WAVE.arrayWalkable method described above;
  • moveNext: calls moveNext of the source of the sequence until it finds an element that matches the filter criteria, or until it reaches the end of the original sequence;
  • current: calls the current source of the sequence.

Usage example


Fragments of unit tests can be cited as simple examples of use.

Let's demonstrate the work of the iterator itself and Walkable:

It is easy to see that such a design allows you to build arbitrary functions that return Walkable in chains of arbitrary length.

By analogy with wWhere, the remaining functions of our library are implemented, for example, wSelect, wDistinct, etc.

function() {
          var a = [1, 2, 3, 4, 5]; 
          var aw = WAVE.arrayWalkable(a);
          var walker = aw.getWalker(), i=0;
          while(walker.moveNext()) {
            assertTrue(a[i] === walker.current());
            i++;
          }
          assertFalse(walker.moveNext());
          assertTrue(null === walker.current());
     }

Now use wWhere by lining them up in a chain:

function() {
          var a = [1, 2, 3, 4, 5]; 
          var aw = WAVE.arrayWalkable(a);
          var wWhere1 = aw.wWhere(function(e) { return e > 1; });
          var wWhere2 = wWhere1.wWhere(function(e) { return e < 5; });
          var result2 = wWhere2.wToArray();
          for(var i in result2) log(result2[i]);
          assertTrue( 3 === result2.length);
     }

The code used for the wrapper function testing included in wv.js .

conclusions


Implementing your own LINQ-like JavaScript library is not a difficult task, and anyone with minimal programming knowledge can handle it.

Nevertheless, in our experience, such a library makes it very cool to write logic based on work with data series, while taking up as much space in the code as we need functions from it.

The source code of the library can be obtained here , unit tests are here .
PS:
I decided to add a complete list of Walkable functions:
wSelect, wSelectMany, wWhere, wAt, wFirst, wFirstIdx, wCount, wDistinct, wConcat, wExcept, wGroup, wGroupIntoObject, wGroupIntoArray, wGroupAggregate, wOrder, wTake, wTakeWhile, wAin, wAm, wMin, wmink, wamk, wamk, wmk, wmk, wg wToArray, wEach, wWMA (moving average), wHarmonicFrequencyFilter (our own filter, the concept has proved to be excellent, for example, here ), wConstLinearSampling, wSineGen, wSawGen, wSquareGen, wRandomGen,

Also popular now: