如何用 JavaScript 实现一个数组惰性求值库

gjah9729 8年前
   <p><img src="https://simg.open-open.com/show/59b617f04369a4dad7cc06692495ede4.png"></p>    <p>在编程语言理论中,惰性求值(英语:Lazy Evaluation),又译为惰性计算、懒惰求值,也称为传需求调用(call-by-need),是一个计算机编程中的一个概念,它的目的是要最小化计算机要做的工作。它有两个相关而又有区别的含意,可以表示为“延迟求值”和“最小化求值”,除可以得到性能的提升外,惰性计算的最重要的好处是它可以构造一个无限的数据类型。</p>    <p>看到函数式语言里面的惰性求值,想自己用 JavaScript 写一个最简实现,加深对惰性求值了解。用了两种方法,都不到 80 行实现了基本的数组的惰性求值。</p>    <h3>怎么实现</h3>    <p>惰性求值每次求值的时候并不是返回数值,而是返回一个包含计算参数的求值函数,每次到了要使用值得时候,才会进行计算。</p>    <p> </p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/bc137c482740398e98f8da35a37d5a1f.png"></p>    <p style="text-align:center">当有多个惰性操作的时候,构成一个求值函数链,每次求值的时候,每个求值函数都向上一个求值函数求值,返回一个值。最后当计算函数终止的时候,返回一个终止值。 <img src="https://simg.open-open.com/show/e22710cfd435e344fb6c993cb2821213.png" alt="如何用 JavaScript 实现一个数组惰性求值库" width="550" height="198"> 当有多个惰性操作的时候,构成一个求值函数链,每次求值的时候,每个求值函数都向上一个求值函数求值,返回一个值。最后当计算函数终止的时候,返回一个终止值。 <img src="https://simg.open-open.com/show/f86e1adfb0371bc496e538ea6be4142e.png"> <img src="https://simg.open-open.com/show/e3237f1f76334e7d75c72bc30102747c.png" alt="如何用 JavaScript 实现一个数组惰性求值库" width="550" height="435"></p>    <h3>具体实现</h3>    <ul>     <li> <p><strong>判断求值函数终止</strong></p> </li>    </ul>    <p>每次求值函数都会返回各种数据,所以得使用一个独一无二的值来作为判断流是否完成的标志。刚好 Symbol() 可以创建一个新的 symbol ,它的值与其它任何值皆不相等。</p>    <pre>  <code class="language-javascript">const over = Symbol();    const isOver = function (_over) {    return _over === over;  }</code></pre>    <ul>     <li> <p><strong>生成函数 range</strong></p> </li>    </ul>    <p>range 函数接受一个起始和终止参数,返回一个求值函数,运行求值函数返回一个值,终止的时候返回终止值。</p>    <pre>  <code class="language-javascript">const range = function (from, to) {    let i = from;    return function () {      if (i < to) {        i++        console.log('range\t', i);        return i      }      return over;    }  }</code></pre>    <ul>     <li> <p><strong>转换函数 map</strong></p> </li>    </ul>    <p>接受一个求值函数和处理函数,获取求值函数 flow 中的数据,对数据进行处理,返回一个流。</p>    <pre>  <code class="language-javascript">const map = function (flow, transform) {    return function () {      const data = flow();      console.log('map\t', data);      return isOver(data) ? data : transform(data);    }  }</code></pre>    <ul>     <li> <p><strong>过滤函数 filter</strong></p> </li>    </ul>    <p>接受一个求值函数,对求值函数 flow 中数据进行过滤,找到符合的数据并且返回。</p>    <pre>  <code class="language-javascript">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;        }      }    }  }</code></pre>    <ul>     <li> <p><strong>中断函数 stop</strong></p> </li>    </ul>    <p>接受一个求值函数,当达到某个条件时中断,可以用闭包函数加上 stop 函数接着实现一个 take 函数。</p>    <pre>  <code class="language-javascript">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;    });  }</code></pre>    <ul>     <li> <p><strong>收集函数 join</strong></p> </li>    </ul>    <p>因为返回的都是一个函数,最后得使用一个 join 函数来收集所有的值并且返回一个数组。</p>    <pre>  <code class="language-javascript">const join = function (flow) {    const array = [];    while(true) {      const data = flow();      if (isOver(data)) {        break;      }      array.push(data);    }    return array;  }</code></pre>    <p>测试:</p>    <pre>  <code class="language-javascript">const nums = join(take(filter(map(range(0, 20), n => n * 10), n => n % 3 === 0), 2));  console.log(nums);    /* 输出    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      [ 30, 60 ]  */</code></pre>    <h3>更优雅的实现</h3>    <p>上面使用 函数 + 闭包 实现了惰性求值,但是还是不够优雅,绝大部分代码都放到迭代和判断求值是否完成上面去了。其实 es6 中还有更好方法来实现惰性求值,就是使用 generator,generator 已经帮我们解决了迭代和判断流是否完成,我们就可以专注于逻辑,写出更简洁易懂结构清晰的代码。</p>    <pre>  <code class="language-javascript">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);  }</code></pre>    <p>还得加上链式调用才算是完成了。</p>    <pre>  <code class="language-javascript">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();  }</code></pre>    <p>最后再测试一下:</p>    <pre>  <code class="language-javascript">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');  }  /* 输出    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  */</code></pre>    <p>好了,大功告成。</p>    <h2>总结</h2>    <p>这样我们就完成了一个最简的数组惰性求值的库,这里只是简单实现了惰性求值,要放到工程中还需要添加很多细节。因为代码不过 80 行,可以很清楚的了解惰性求值原理,还能加深对生成器的理解。</p>    <p> </p>    <p> </p>    <p>来自:https://zhuanlan.zhihu.com/p/26535479</p>    <p> </p>