How to implement an array lazy evaluation library in JavaScript

Overview

In programming language theory, lazy evaluation (English: Lazy Evaluation), also translated as lazy calculation, lazy evaluation, also known as call-by-need, is a concept in computer programming. Its purpose is to minimize the work the computer has to do. It has two related but distinct meanings, which can be expressed as "delayed evaluation" and "minimized evaluation". In addition to performance improvements, the most important benefit of lazy evaluation is that it can construct an infinite data type.

After seeing lazy evaluation in functional languages, I wanted to write a simplest implementation in JavaScript to deepen my understanding of lazy evaluation. Two methods are used, both of which take less than 80 lines to implement basic array lazy evaluation.

How to achieve it

Lazy evaluation does not return a value each time it is evaluated, but instead returns an evaluation function containing calculation parameters. The calculation is performed each time the value is to be used.

When there are multiple lazy operations, a chain of evaluation functions is formed. Each time an evaluation is performed, each evaluation function evaluates the previous evaluation function and returns a value. Finally, when the calculation function terminates, a termination value is returned.

Specific implementation

Determine the termination of the evaluation function

Each evaluation of the function will return various data, so a unique value must be used as a marker to determine whether the flow is complete. It just so happens that Symbol() can create a new symbol whose value is not equal to any other value.

const over = Symbol();

const isOver = function (_over) {
  return _over === over;
}

Generating function range

The range function accepts a start and end parameter, returns an evaluation function, runs the evaluation function to return a value, and returns the end value when it terminates.

const range = function (from, to) {
  let i = from;
  return function () {
    if (i < to) {
      i++
      console.log('range\t', i);
      return i
    }
    return over;
  }
}

Transformation function map

Accepts an evaluation function and a processing function, obtains the data in the evaluation function flow, processes the data, and returns a flow.

const map = function (flow, transform) {
  return function () {
    const data = flow();
    console.log('map\t', data);
    return isOver(data) ? data : transform(data);
  }
}

filter

Accepts an evaluation function, filters the data in the evaluation function flow, finds the matching data and returns it.

const filter = function (flow, condition) {
  return function () {
    while(true) {
      const data = flow();
      if (isOver(data)) {
        return data;
      }
      if(condition(data)) {
        console.log('filter\t', data);
        return data;
      }
    }
  }
}

Interrupt function stop

Accepts an evaluation function and interrupts when a certain condition is reached. You can use a closure function plus a stop function and then implement a take function.

const stop = function (flow, condition) {
  let _stop = false;
  return function () {
    if (_stop) return over;
    const data = flow();
    if (isOver(data)) {
      return data;
    }
    _stop = condition(data);
    return data;
  }
}

const take = function(flow, num) {
  let i = 0;
  return stop(flow, (data) => {
    return ++i >= num;
  });
}

Collection function join

Since everything returned is a function, we have to use a join function at the end to collect all the values ​​and return an array.

const join = function (flow) {
  const array = [];
  while(true) {
    const data = flow();
    if (isOver(data)) {
      break;
    }
    array.push(data);
  }
  return array;
}

test:

const nums = join(take(filter(map(range(0, 20), n => n * 10), n => n % 3 === 0), 2));
console.log(nums);

Output:

range 1

map 1

range 2

map 2

range 3

map 3

filter 30

range 4

map 4

range 5

map 5

range 6

map 6

filter 60

A more elegant implementation

The lazy evaluation is implemented using functions + closures above, but it is still not elegant enough. Most of the code is put into iteration and judging whether the evaluation is completed. In fact, there is a better way to achieve lazy evaluation in es6, which is to use generators. Generators have helped us solve iteration and determine whether the flow is complete. We can focus on logic and write more concise, easy-to-understand and clearly structured code.

const range = function* (from, to) {
  for(let i = from; i < to; i++) {
    console.log('range\t', i);
    yield i;
  }
}

const map = function* (flow, transform) {
  for(const data of flow) {
    console.log('map\t', data);
    yield(transform(data));
  }
}

const filter = function* (flow, condition) {
  for(const data of flow) {
    console.log('filter\t', data);
    if (condition(data)) {
      yield data;
    }
  }
}

const stop = function*(flow, condition) {
  for(const data of flow) {
    yield data;
    if (condition(data)) {
      break;
    }
  }
}

const take = function (flow, number) {
  let count = 0;
  const _filter = function (data) {
    count++
    return count >= number;
  }
  return stop(flow, _filter);
}

It is completed by adding chain calls.

class _Lazy{
  constructor() {
    this.iterator = null;
  }

  range(...args) {
    this.iterator = range(...args);
    return this;
  }

  map(...args) {
    this.iterator = map(this.iterator, ...args);
    return this;
  }

  filter(...args) {
    this.iterator = filter(this.iterator, ...args);
    return this;
  }

  take(...args) {
    this.iterator = take(this.iterator, ...args);
    return this;
  }

  [Symbol.iterator]() {
    return this.iterator;
  }

}

function lazy () {
  return new _Lazy();
}

Finally, test it again:

const nums = lazy().range(0, 100).map(n => n * 10).filter(n => n % 3 === 0).take(2);

for(let n of nums) {
  console.log('num:\t', n, '\n');
}

Output:

range 0

map 0

filter 0

num: 0

range 1

map 1

filter 10

range 2

map 2

filter 20

range 3

map 3

filter 30

num: 30

Okay, it's done.

Summarize

In this way, we have completed a simplest array lazy evaluation library. Here we only simply implement lazy evaluation. Many details need to be added to put it into the project. Because the code is only 80 lines, you can clearly understand the principle of lazy evaluation and deepen your understanding of generators.

The above is the details of how to implement an array lazy evaluation library with JavaScript. For more information about JavaScript implementing an array lazy evaluation library, please pay attention to other related articles on 123WORDPRESS.COM!