資訊專欄INFORMATION COLUMN
摘要：在某些不定長度的列表操作上，惰性列表會讓代碼和結(jié)構(gòu)更靈活。方法本身是立即執(zhí)行的，如果滿足條件，這里的方法會執(zhí)行兩次。結(jié)語和是帶給我們的非常強大的語言層面的能力，它本身的求值可以看作是惰性的。
初識 Lazy List
如果有了解過 Haskell 的朋友，對下面的這些表達一定不陌生
repeat 1 -- => [1, 1, 1, 1, 1,...] cycle "abc" -- => "abcabcabc..." [1, 3..] -- => [1, 3, 5, 7, ...]
上面的幾個表達式產(chǎn)生的都是無限列表。對于習(xí)慣了主流編程語言的朋友可能感到困惑，在有限的內(nèi)存里面如何能表達無限的概念。主要的原因就是 Haskell 是一門默認(rèn)采用惰性求值策略的語言，沒有用到的部分，在內(nèi)存里面只是一個表達式，并不會真正的去做計算。
如果只看上面的幾個表達式，很多朋友可能會說，也沒感覺到有什么神奇的地方，似乎并沒有什么作用。我們再看看下面的代碼。
Haskell 中的 fibonacci 數(shù)列：
fibonacci = 1 : 1 : zipWith (+) fibonacci (tail fibonacci)
這里 fibonacci 本身是一個惰性結(jié)構(gòu)，所以在計算的時候，會先算出列表前面的兩個1，得到 1 : 1... 這樣的結(jié)構(gòu)，然后怎么表達 fibonacci 的 fib(n) = fib(n - 1) + fib(n - 2) 特性呢？我們可以注意到，n - 1和 n - 2 剛好在數(shù)列中相差一位，所以 n 可以看作是該數(shù)列錯位的相加的結(jié)果。
我們再來看一則篩法求素數(shù)。不熟悉篩法的可以先點開 wiki 去看一下該算法的思路。下面這段代碼是 Haskell 的一個簡單實現(xiàn)。
primes = 2 : filter isPrime [3, 5..]
where
isPrime x = all (p -> x `mod` p > 0) (takeWhile (p -> p * p <= x) primes)
So, Why Lazy?
在某些不定長度的列表操作上，惰性列表會讓代碼和結(jié)構(gòu)更靈活。用上面的 primes 列表舉個例子好了，在傳統(tǒng)的 C 語言或者 Java 的實現(xiàn)里面，我們一般要先聲明一個最大長度或者一個最大的取值范圍，比如 10000 以內(nèi)的素數(shù)。如果后面的計算要用到超過這個范圍，我們就不得不重新調(diào)用生成函數(shù)，重新生成一份更長的列表。這里面的問題是：一、要主動去調(diào)用這個工廠函數(shù)，二、如果要復(fù)用已經(jīng)計算出來的數(shù)據(jù)，手動去維護一個cache列表，勢必增加代碼的復(fù)雜度。另外一個可能的情況是，我們預(yù)先生成了一份很長的列表，后面的計算中只用到了列表頭部的一丟丟數(shù)據(jù)，這也是極大的浪費。
惰性列表的使用增加了我們編程的表達能力，讓我們可以更關(guān)注數(shù)據(jù)結(jié)構(gòu)本身的特性，而不是浪費時間在如何去管理堆棧上面。因為，惰性求值特性保證我們在需要一個值的時候才會去計算，所以可以自動地最小化我們的計算量，節(jié)約資源。
比如我們可以通過 lazy byteString 去讀、寫文件，它本身不會把整個文件加載到我們的內(nèi)存里面，而是按需的讀取。有的時候我們讀一個大文件，可能只篩選出需要的前幾十條數(shù)據(jù)，卻確不得不把幾百 M 甚至上 G 的大文件整個的放到內(nèi)存里面。
這里也找到一篇14年的文章 How to Speed Up Lo-Dash ×100? Introducing Lazy Evaluation，感興趣的可以點開看看。
在 JavaScript 中實現(xiàn) Lazy List在 JavaScript 有沒有惰性結(jié)構(gòu)呢？先看下面這個例子。
let fetchSomething = fetch("/some/thing");
if (condition) {
fetchSomething = fetch("/some/thing/condition");
}
fetchSomething.then(() => {
// TODO
});
fetch 方法本身是立即執(zhí)行的，如果滿足條件，這里的 fetch 方法會執(zhí)行兩次。這并不是我們期待的行為，這里需要讓這個 fetch 的動作在我們需要的時候才去執(zhí)行，而不是聲明的時候就開始執(zhí)行的話，通常的做法是把它改成下面的樣子。
let fetchSomething = () => fetch("/some/thing");
if (condition) {
fetchSomething = () = fetch("/some/thing/condition");
}
fetchSomething.then(() => {
// TODO
});
由此啟發(fā)，我們大致可以實現(xiàn)如下的結(jié)構(gòu)。
class List{ head: T | () => T tail: List | () => List constructor(head: T, tail: () => List ) { this.head = () => head; this.tail = tail; } }
List
這種方式看起來似乎已經(jīng)解決了我的問題，但是這種結(jié)構(gòu)在和普通的 Array 做互相轉(zhuǎn)換的時候，存在大量不必要的額外開銷。
那 JavaScript 中有沒有更天然的結(jié)構(gòu)，可以讓我們免于去構(gòu)造這樣一個復(fù)雜的對象，簡化代碼的同時，讓我們的代碼更具有普適性呢？
初識 IterableES6 的新特性給了我想要的答案，Iteration Protocols。如果嫌MDN的描述太長，可以直接看下面等價的類型聲明。
interface Iterable{ [Symbol.iterator](): Iterator ; } interface Iterator { next(): IteratorResult ; } interface IteratorResult { done: Boolean; value?: T; } interface IterableIterator { [Symbol.iterator](): Iterator ; next(): IteratorResult ; }
所有實現(xiàn)一個Iterable接口的對象都可以通過諸如 for...of...、...itor 以及 Array.from 來訪問，當(dāng)next方法的返回值中done為true時，迭代結(jié)束。而且只有我們訪問next方法時，才會進入下一步迭代，是理想的Lazy結(jié)構(gòu)。
這時候我們看一下我們的 fibonacci 該怎么寫？
class Fibonacci implements IterableIterator{ private prev = 1; private next = 1; public next() { let current = this.prev; this.prev = this.next; this.next = current + this.prev; return { done: false, value: current } } [Symbol.iterator]() { return this; } } const fib = new Fibonacci(); fib.next() // => { done: false, value: 1 } fib.next() // => { done: false, value: 1 } fib.next() // => { done: false, value: 2 } // etc
到這里，我們已經(jīng)可以表達一個惰性的無限數(shù)列了。但是上面的代碼畢竟過于繁瑣，好在 ES6 同時給我們提供了 Generator, 可以讓我們很方便地書寫 IterableItorator，從某種意義上來講，Generator 可以說是上面代碼的語法糖。
使用Generator，上面的代碼可以簡化成下面的樣子。
export function* fibonacci() {
let prev = 1;
let next = 1;
while (true) {
yield prev;
const temp = prev;
prev = next;
next = temp + prev;
}
}
const fib = fibonacci();
// etc
這里不再去花段落介紹 Generator 的語法，不了解的同學(xué)可以先去閱讀下這篇文章 A Simple Guide to Understanding Javascript (ES6) Generators。
定義 Infinite List接著上面的代碼往下寫，下面的代碼分別實現(xiàn)了文章開頭的 repeat, cycle, iterate, range 等方法。
export function* repeat(item: T) { while (true) { yield item; } } export function* cycle (items: Iterable ) { while (true) { yield* [...items]; } } export function* iterate (fn: (value: T) => T, initial: T) { let val = initial; while (true) { yield val; val = fn(val); } } export function* range(start: number, end = Infinity, step = 1) { while (start <= end) { yield start; start += step; } }
可以看到，代碼是非常直觀且易于理解的。
定義 Operator有了列表之后，我們需要在列表之上進行操作，下面的代碼分別實現(xiàn)了 map/filter/take/takeWhile 方法。
