背景：惰性求值？

來看一個(gè) lazy.js 主頁提供的示例：

var people = getBigArrayOfPeople();
var results = _.chain(people)
  .pluck('lastName')
  .filter(function(name) { return name.startsWith('Smith'); })
  .take(5)
  .value();

上例中，要在非常非常多的人里面巧颈，找出 5 個(gè)以 Smith 開頭的 lastName。如果在上面的 pluck() 和 filter() 的過程中袖扛，每一步都產(chǎn)生了臨時(shí)數(shù)組砸泛，也就是說對(duì)上一步返回的數(shù)據(jù)執(zhí)行了一次循環(huán)、處理的過程蛆封，那么整個(gè)查找的過程可能會(huì)花費(fèi)很長的時(shí)間唇礁。

不采用上面的這種寫法，單純?yōu)榱诵阅芸紤]惨篱，可以這樣處理：

var results = [];
for (var i = 0; i < people.length; ++i) {
  var lastName = people[i].lastName;
  if (lastName.startsWith('Smith')) {
    results.push(value);
    if (results.length === 5) {
      break;
    }
  }
}

首先盏筐，對(duì)于原始數(shù)據(jù)，只做一次循環(huán)砸讳，單次循環(huán)中完成所有的計(jì)算琢融。其次，由于只需要 5 個(gè)最終結(jié)果簿寂，所以漾抬，一旦得到了 5 個(gè)結(jié)果，就終止循環(huán)常遂。

采取這種處理方法纳令，對(duì)于比較大的數(shù)組，在計(jì)算性能上應(yīng)該會(huì)有明顯的提升烈钞。

不過泊碑，如果每次遇到這種類似的情形，為了性能毯欣，都要手寫這樣的代碼馒过，有點(diǎn)麻煩，而且代碼不清晰酗钞，不便于理解腹忽、維護(hù)。第一個(gè)例子中的寫法要好些砚作，明顯更易讀一些窘奏，但是對(duì)于性能方面有些擔(dān)憂。

所以葫录，如果可以結(jié)合第一個(gè)例子中的寫法着裹，但又能有第二個(gè)例子中的性能提升，豈不是很好米同？

接下來再說說“惰性求值”了骇扇。

Lazy evaluation - wikipedia
https://en.wikipedia.org/wiki/Lazy_evaluation

In programming language theory, lazy evaluation, or call-by-need is an evaluation strategy which delays the evaluation of an expression until its value is needed (non-strict evaluation) and which also avoids repeated evaluations (sharing).

用我的話來表達(dá)摔竿，惰性求值就是：對(duì)于一個(gè)表達(dá)式，在不需要值的時(shí)候不計(jì)算少孝，需要的時(shí)候才計(jì)算继低。

JavaScript 并非從語言層面就支持這樣的特性，而是要通過一些技術(shù)來模擬稍走、實(shí)現(xiàn)袁翁。

首先，不能是表達(dá)式婿脸，表達(dá)式在 JS 中是立即求值的粱胜。所以，要像第一個(gè)例子中的那樣盖淡，將求值的過程包裝為函數(shù)年柠，只在需要求值的時(shí)候才調(diào)用該函數(shù)。

然后褪迟，延遲計(jì)算還需要通過“精妙的”設(shè)計(jì)和約定來實(shí)現(xiàn)冗恨。對(duì)于第一個(gè)例子，pluck()味赃、filter()掀抹、take() 方法在調(diào)用時(shí)，不能直接對(duì)原始數(shù)據(jù)進(jìn)行計(jì)算心俗，而是要延遲到類似 value() 這樣的方法被調(diào)用時(shí)再進(jìn)行傲武。

在分析 Lazy.js 的惰性求值實(shí)現(xiàn)前，先總結(jié)下這里要討論的借助惰性求值技術(shù)來實(shí)現(xiàn)的目標(biāo)：

• 良好的代碼可讀性
• 良好的代碼執(zhí)行性能

而對(duì)于 Lazy.js 中的惰性求值實(shí)現(xiàn)城榛，可以總結(jié)為：

• 收集計(jì)算需求
• 延遲并優(yōu)化計(jì)算的執(zhí)行過程

分析：Lazy.js 的惰性求值實(shí)現(xiàn)

與 Underscore揪利、Lo-Dash 不同，Lazy.js 只提供鏈?zhǔn)降暮莩帧⒍栊郧笾档挠?jì)算模式疟位，這也使得其惰性求值實(shí)現(xiàn)比較“純粹”，接下來就進(jìn)入 Lazy.js 的實(shí)現(xiàn)分析了喘垂。

先看下使用 Lazy.js 的代碼（來自 simply-lazy - demo）：

Lazy([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
  .map(i => i * 2)
  .filter(i => i <= 10)
  .take(3)
  .each(i => print(i))

// output:
// 2
// 4
// 6

注：為了書寫方法甜刻，函數(shù)定義采用 ES6 的 “=>” 語法。

這是一個(gè)有點(diǎn)無聊的例子正勒，對(duì) 1 - 10 先進(jìn)行乘 2 運(yùn)算得院，然后過濾出小于 10 的值，再取前 3 個(gè)結(jié)果值輸出章贞。

如果對(duì)上述代碼的執(zhí)行進(jìn)行監(jiān)測(cè)（參考：借助 Proxy 實(shí)現(xiàn)回調(diào)函數(shù)執(zhí)行計(jì)數(shù)）祥绞，會(huì)得到以下結(jié)果：

demo - simply-lazy

map() 和 filter() 的過程都只執(zhí)行了 3 次。

先關(guān)注 map() 調(diào)用，顯然蜕径，這里沒有立即執(zhí)行計(jì)算怪蔑，因?yàn)檫@里的代碼還不能預(yù)知到后面的 filter() 和 take(3)，所以不會(huì)聰明地知道自己只需要執(zhí)行 3 次計(jì)算就可以了丧荐。如果沒有執(zhí)行計(jì)算，那么這里做了什么喧枷，又返回了什么呢虹统？

先說答案：其實(shí)從 Lazy() 返回的是一個(gè) Sequence 類型的對(duì)象，包含了原始的數(shù)據(jù)隧甚；map() 方法執(zhí)行后车荔，又生成了一個(gè)新的 Sequence 對(duì)象，該對(duì)象鏈接到上一個(gè) Sequence 對(duì)象戚扳，同時(shí)記錄了當(dāng)前步驟要執(zhí)行的計(jì)算（i => i * 2）忧便，然后返回新的 Sequence 對(duì)象。后續(xù)的 filter() 和 take() 也是類似的過程帽借。

上面的代碼也可以寫成：

var seq0 = Lazy([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
var seq1 = seq0.map(i => i * 2)
var seq2 = seq1.filter(i => i <= 10)
var seq3 = seq2.take(3)

// 求值
seq3.each(i => print(i))

在最后一個(gè)求值時(shí)珠增，已經(jīng)有一個(gè) Sequence 鏈了：

seq0 <- seq1 <- seq2 <- seq3

在 seq3 調(diào)用 each() 方法執(zhí)行求值前，這些鏈上的 seq 都還沒有執(zhí)行計(jì)算砍艾。那么計(jì)算的過程是怎樣的呢蒂教？其實(shí)就類似于最前面第二個(gè)例子那樣，在一個(gè)循環(huán)中脆荷，由鏈上的最后一個(gè) seq 開始凝垛，依次向前面一個(gè) seq 獲取值，再將值返回給調(diào)用方（也就是下一個(gè) seq）前蜓谋，會(huì)應(yīng)用當(dāng)前 seq 的計(jì)算梦皮。

獲得第一個(gè)最終結(jié)果值的過程為：

[1] seq3 調(diào)用 seq2 獲取第 1 個(gè)值
[2] seq2 調(diào)用 seq1 獲取第 1 個(gè)值
[3] seq1 直接從 seq0 的 source 屬性對(duì)應(yīng)的原始數(shù)值取值（第 1 個(gè)值為  1）
[4] seq1 得到 1，應(yīng)用計(jì)算（i => i * 2）桃焕，得到 2剑肯，返回給調(diào)用方（seq2）
[5] seq2 得到 2，應(yīng)用計(jì)算（i => i < 10）覆旭，滿足條件退子，將 2 返回給調(diào)用方（seq3）
[6] seq3 得到 2，應(yīng)用計(jì)算（已返回值數(shù)目是否小于 3）型将，滿足條件寂祥，將 2 返回給調(diào)用方（seq3.each）

最終，seq3.each() 得到第 1 個(gè)值（2）七兜，應(yīng)用計(jì)算（i => print(i)）丸凭，將其輸出。然后繼續(xù)獲取下一個(gè)值，直到在某個(gè)過程中調(diào)用終止（這里是 take() 計(jì)算中已返回 3 個(gè)值時(shí)終止）惜犀。

除了 map()铛碑、filter()、take()虽界，Lazy.js 還提供了更多的計(jì)算模式汽烦，不過其惰性計(jì)算的過程就是這樣了，總結(jié)為：

• Lazy() 返回初始的 Sequence 對(duì)象
• 惰性計(jì)算方法返回新的 Sequence 對(duì)象莉御，內(nèi)部記錄上一個(gè) Sequence 對(duì)象以及當(dāng)前計(jì)算邏輯
• 求值計(jì)算方法從當(dāng)前 Sequence 對(duì)象開始撇吞，依次向上一個(gè) Sequence 對(duì)象獲取值
• Sequence 對(duì)象在將從上一個(gè) Sequence 對(duì)象獲得的值返回給下一個(gè) Sequence 前，應(yīng)用自身的計(jì)算邏輯

Lazy.js 的 Sequence 的設(shè)計(jì)礁叔，使得取值和計(jì)算的過程形成一個(gè)長鏈牍颈，鏈條上的單個(gè)節(jié)點(diǎn)只需要完成上傳、下達(dá)琅关，并且應(yīng)用自身計(jì)算邏輯就可以了煮岁，它不需要洞悉整體的執(zhí)行過程。每個(gè)節(jié)點(diǎn)各司其職涣易，最終實(shí)現(xiàn)了惰性計(jì)算画机。

代碼有時(shí)候勝過萬語千言，下面通過對(duì)簡(jiǎn)化版的 Lazy.js（simply-lazy）的源碼分析新症，來更進(jìn)一步展示 Lazy.js 惰性計(jì)算的原理色罚。

實(shí)現(xiàn)：簡(jiǎn)化版的 Lazy.js

Lazy.js 可以支持進(jìn)行計(jì)算的數(shù)據(jù)，除了數(shù)組账劲，還有字符串和對(duì)象戳护。simply-lazy 只提供了數(shù)組的支持，而且只支持三種惰性求值方法：

• map()
• filter()
• take()

分別看這個(gè)三個(gè)方法的實(shí)現(xiàn)瀑焦。

（一）map

Lazy() 直接返回的 Sequence 對(duì)象是比較特殊的腌且，和鏈上的其他 Sequence 對(duì)象不同，它已經(jīng)是根節(jié)點(diǎn)榛瓮，自身記錄了原始數(shù)據(jù)铺董，也不包含計(jì)算邏輯。所以禀晓，對(duì)這個(gè)對(duì)象進(jìn)行遍歷其實(shí)就是遍歷原始數(shù)據(jù)精续，也不涉及惰性計(jì)算。

simple-lazy 中保留了 Lazy.js 中的命名方式粹懒，盡管只支持?jǐn)?shù)組重付，還是給這個(gè)類型取名為 ArrayWrapper：

function ArrayWrapper(source) {
  var seq = ArrayLikeSequence()
  seq.source = source
  seq.get = i => source[i]
  seq.length = () => source.length
  seq.each = fn => {
    var i = -1
    var len = source.length
    while (++i < len) {
      if (fn(source[i], i) === false) {
        return false
      }
    }
    return true
  }
  seq.map = mapFn => MappedArrayWrapper(seq, mapFn)
  seq.filter = filterFn => FilteredArrayWrapper(seq, filterFn)
  return seq
}

simple-lazy 為了簡(jiǎn)化代碼，并沒有采用 Lazy.js 那種為不同類型的 Sequence 對(duì)象構(gòu)造不同的類的模式凫乖，Sequence 可以看作普通的對(duì)象确垫，只是按照約定弓颈，需要支持幾個(gè)接口方法而已。像這里的 ArrayWrapper()删掀，返回的 seq 對(duì)象盡管來自 ArrayLikeSequence()翔冀，但自身已經(jīng)實(shí)現(xiàn)了大多數(shù)的接口。

Lazy 函數(shù)其實(shí)就是返回了這樣的 ArrayWrapper 對(duì)象：

function Lazy(source) {
  if (source instanceof Array) {
    return ArrayWrapper(source);
  }
  throw new Error('Sorry, only array is supported in simply-lazy.')
}

如果對(duì)于 Lazy() 返回的對(duì)象之間進(jìn)行求值披泪，可以看到纤子，其實(shí)就是執(zhí)行了在 ArrayWrapper 中定義的遍歷原始數(shù)據(jù)的過程。

下面來看 seq.map()款票。ArrayWrapper 的 map() 返回的是 MappedArrayWrapper 類型的 Sequence 對(duì)象：

function MappedArrayWrapper(parent, mapFn) {
  var source = parent.source
  var length = source.length
  var seq = ArrayLikeSequence()
  seq.parent = parent
  seq.get = i => (i < 0 || i >= length) ? undefined : mapFn(source[i])
  seq.length = () => length
  seq.each = fn => {
    var i = -1;
    while (++i < length) {
      if (fn(mapFn(source[i], i), i) === false) {
        return false
      }
    }
    return true
  }
  return seq
}

這其實(shí)也是個(gè)特殊的 Sequence（所以名字上沒有 Sequence）计福，因?yàn)樗雷约荷弦患?jí) Sequence 對(duì)象是不包含計(jì)算邏輯的原始 Sequence 對(duì)象，所以它直接通過 parent.source 就可以獲取到原始數(shù)據(jù)了徽职。

此時(shí)執(zhí)行的求值，則是直接在原始數(shù)據(jù)上應(yīng)用傳入的 mapFn佩厚。

而如果是先執(zhí)行了其他的惰性計(jì)算方法姆钉，對(duì)于得到的結(jié)果對(duì)象再應(yīng)用 map() 呢， 這個(gè)時(shí)候就要看具體的情況了抄瓦，simply-lazy 中還有兩種相關(guān)的類型：

• MappedSequence
• IndexedMappedSequence

MappedSequence 是更通用的類型潮瓶，對(duì)應(yīng) map() 得到 Sequence 的類型：

function MappedSequence(parent, mapFn) {
  var seq = new Sequence()
  seq.getIterator = () => {
    var iterator = parent.getIterator()
    var index = -1
    return {
      current() { return mapFn(iterator.current(), index) },
      moveNext() {
        if (iterator.moveNext()) {
          ++index
          return true
        }
        return false
      }
    }
  }
  seq.each = fn => parent.each((e, i) => fn(mapFn(e, i), i))
  return seq
}

來看這里的求值（each）過程，是間接調(diào)用了其上級(jí) Sequence 的 each() 來完成的钙姊。同時(shí)還定義了 getIterator() 接口毯辅，使得其下級(jí) Sequence 可以從這里得到一個(gè)迭代器，對(duì)于該 Sequence 進(jìn)行遍歷煞额。迭代器在 Lazy.js 中也是一個(gè)約定的協(xié)議思恐，實(shí)現(xiàn)該協(xié)議的對(duì)象要支持 current() 和 moveNext() 兩個(gè)接口方法。從迭代器的邏輯中膊毁，可以看到胀莹，當(dāng) MappedSequence 對(duì)象作為其他 Sequence 的上級(jí)時(shí)，如果實(shí)現(xiàn)“上傳下達(dá)”婚温。

而 IndexedMappedSequence 的實(shí)現(xiàn)要簡(jiǎn)單些描焰，它的主要功能都來源于“繼承” ：

  function IndexedMappedSequence(parent, mapFn) {
    var seq = ArrayLikeSequence()
    seq.parent = parent
    seq.get = (i) => {
      if (i < 0 || i >= parent.length()) {
        return undefined;
      }
      return mapFn(parent.get(i), i);
    }
    return seq
  }

IndexedMappedSequence 只提供了獲取特定索引位置的元素的功能，其他的處理交由 ArrayLikeSequence 來實(shí)現(xiàn)栅螟。

而 ArrayLikeSequence 則又“繼承”自 Sequence：

function ArrayLikeSequence() {
  var seq = new Sequence()
  seq.length = () => seq.parent.length()
  seq.map = mapFn => IndexedMappedSequence(seq, mapFn)
  seq.filter = filterFn => IndexedFilteredSequence(seq, filterFn)
  return seq
}

Sequence 中實(shí)現(xiàn)的是更一般意義上的處理荆秦。

上面介紹的這些與 map 有關(guān)的 Sequence 類型，其實(shí)現(xiàn)各有不同力图，的確有些繞步绸。但無論是怎樣進(jìn)行實(shí)現(xiàn)，其核心的邏輯沒有變吃媒，都是要在其上級(jí) Sequence 的值上應(yīng)用其 mapFn靡努，然后返回結(jié)果值給下級(jí) Sequence 使用坪圾。這是 map 計(jì)算的特定模式。

（二）filter

filter 的計(jì)算模式與 map 不同惑朦，filter 對(duì)上級(jí) Sequence 返回的值應(yīng)用 filterFn 進(jìn)行判斷兽泄，滿足條件后再傳遞給下級(jí) Sequence，否則繼續(xù)從上級(jí) Sequence 獲取新一個(gè)值進(jìn)行計(jì)算漾月，直到?jīng)]有值或者找到一個(gè)滿足條件的值病梢。

filter 相關(guān)的 Sequence 類型也有多個(gè)，這里只看其中一個(gè)梁肿，因?yàn)楸M管實(shí)現(xiàn)的方式不同蜓陌，其計(jì)算模式的本質(zhì)是一樣的：

function FilteredSequence(parent, filterFn) {
  var seq = new Sequence()
  seq.getIterator = () => {
    var iterator = parent.getIterator()
    var index = 0
    var value
    return {
      current() { return value },
      moveNext() {
        var _val
        while (iterator.moveNext()) {
          _val = iterator.current()
          if (filterFn(_val, index++)) {
            value = _val
            return true
          }
        }
        value = undefined
        return false
      }
    }
  }
  seq.each = fn => {
    var j = 0;
    return parent.each((e, i) => {
      if (filterFn(e, i)) {
        return fn(e, j++);
      }
    })
  }
  return seq
}

FilteredSequence 的 getIterator() 和 each() 中都可以看到 filter 的計(jì)算模式，就是前面說的吩蔑，判斷上級(jí) Sequence 的值钮热，根據(jù)結(jié)果決定是返回給下一級(jí) Sequence 還是繼續(xù)獲取。

不再贅述烛芬。

（三）take

take 的計(jì)算模式是從上級(jí) Sequence 中獲取值隧期，達(dá)到指定數(shù)目就終止計(jì)算：

function TakeSequence(parent, count) {
  var seq = new Sequence()
  seq.getIterator = () => {
    var iterator = parent.getIterator()
    var _count = count
    return {
      current() { return iterator.current() },
      moveNext() { return (--_count >= 0) && iterator.moveNext() }
    }
  }
  seq.each = (fn) => {
    var _count = count
    var i = 0
    var result
    parent.each(e => {
      if (i < count) { result = fn(e, i++); }
      if (i >= count) { return false; }
      return result
    })
    return i === count && result !== false
  }
  return seq
}

只看 TakeSequence 類型，與 FilteredSequence 類似赘娄，其 getIterator() 和 each() 中都提現(xiàn)了其計(jì)算模式仆潮。一旦獲得了指定數(shù)目的值，就終止計(jì)算（通過 return false）遣臼。

總結(jié)

simply-lazy 中雖然只是實(shí)現(xiàn)了 Lazy.js 的三個(gè)惰性計(jì)算方法（map性置，filter、take）揍堰，但從中已經(jīng)可以看出 Lazy.js 的設(shè)計(jì)模式了鹏浅。不同的計(jì)算方法體現(xiàn)的是不同的計(jì)算模式，而這計(jì)算模式則是通過不同的 Sequence 類型來實(shí)現(xiàn)的屏歹。

具體的 Sequence 類型包含了特定的計(jì)算模式篡石，這從其類型名稱上也能看出來。例如西采，MappedArrayWrapper凰萨、MappedSequence、IndexedMappedSequence 都是對(duì)應(yīng) map 計(jì)算模式械馆。

而求值的過程胖眷，或者說求值的模式是統(tǒng)一的，都是借助 Sequence 鏈霹崎，鏈條上的每個(gè) Sequence 節(jié)點(diǎn)只負(fù)責(zé)：

• 上傳：向上級(jí) Sequence 獲取值
• 下達(dá)：向下級(jí) Sequence 傳遞至
• 求值：應(yīng)用類型對(duì)應(yīng)的計(jì)算模式對(duì)數(shù)據(jù)進(jìn)行計(jì)算或者過濾等操作

由內(nèi)嵌了不同的計(jì)算模式的 Sequence 構(gòu)成的鏈珊搀，就實(shí)現(xiàn)了惰性求值。

當(dāng)然尾菇，這只是 Lazy.js 中的惰性求值的實(shí)現(xiàn)境析，并不意外這“惰性求值”就等于這里的實(shí)現(xiàn)囚枪，或者說惰性求值的全部特性就是這里 Lazy.js 的全部特性。更何況劳淆，本文主要分析的 simply-lazy 也只是從模式上對(duì) Lazy.js 的惰性求值進(jìn)行了說明链沼，也并不包含 Lazy.js 的全部特性（例如生成無限長度的列表）。

不管怎樣沛鸵，還是閱讀過后能夠給你帶來一點(diǎn)有價(jià)值的東西括勺。哪怕只有一點(diǎn)，我也很高興曲掰。

文中對(duì) Lazy.js 的惰性求值的分析僅是我個(gè)人的見解疾捍，如果錯(cuò)漏，歡迎指正栏妖！

最后乱豆，感謝閱讀！