摘要：以前的編程任務(wù)多數(shù)是要求打印出序列前項(xiàng)的值，接口往往像這樣然后我們巴拉巴拉用一個(gè)循環(huán)搞定，而這次重點(diǎn)在于接口，需要實(shí)現(xiàn)一個(gè)斐波那契序列發(fā)生器。

本次我領(lǐng)到的任務(wù)如下：

任務(wù)：

你正在打造一個(gè)斐波那契世界，這是一個(gè)函數(shù)式的世界，
在這個(gè)世界中每個(gè)生命都是一個(gè)函數(shù)

root是這個(gè)世界的祖先
root.value; // 1

在這樣的世界，生孩子特別容易：

const child = root(); // 創(chuàng)建下一代 
child.value // 1

const child_of_child = child(); // 孫子
child_of_child.value // 2

child_of_child().value // 3
child_of_child()().value // 5

const xxx = root()()()()()... // 子子孫孫無窮盡也
xxx.value // 已經(jīng)不知道是多少了

請(qǐng)創(chuàng)建這個(gè)世界的祖先 root

任務(wù)
完成這個(gè)斐波那契世界代碼

這個(gè)任務(wù)的本意是探索原型(prototype based)編程的，這樣可以領(lǐng)略一個(gè)更加精簡的javascript，不過在編寫示例代碼過程中沒收住，使用了流和函數(shù)式編程去搞定了，實(shí)現(xiàn)過程中偶爾的一些想法也值得記錄，所以這次先聊聊函數(shù)式編程，下次再專門探索原型編程。

關(guān)于斐波那契算法本身，及其在自然界中神奇的存在這里就略過了，知乎中有很專業(yè)的回答，公式很專業(yè)，尤其是里面的圖片真不錯(cuò)。

以前的編程任務(wù)多數(shù)是要求打印出序列前n項(xiàng)的值，接口往往像這樣

function fibs(n) {
 ...
}

然后我們巴拉巴拉用一個(gè)循環(huán)搞定， 而這次重點(diǎn)在于接口，需要實(shí)現(xiàn)一個(gè)斐波那契序列發(fā)生器。

我快速實(shí)現(xiàn)了第一個(gè)版本：

class Fibs {
  constructor() {
    this.prev = 0;
    this.cur = 1;
  }
  
  next() {
    const value = this.prev;
    [this.prev, this.cur] = [this.cur, this.prev + this.cur];
    return value;
  }
}

然后用一段平凡的for語句打印一下，看看有沒有弄對(duì)。

const fib = new Fibs();
for (let i = 0; i < 10; i++) {
  const value = fib.next();
  console.log(value);
}

還沒寫完時(shí)就想到了還可以使用生成器函數(shù)來解決：

function* fibs() {
  let [prev, cur] = [0, 1];
  while (true) {
    yield prev;
    [prev, cur] = [cur, prev + cur];
  }
}

對(duì)于生成器，我們可以使用for of來迭代，為了代碼更優(yōu)雅，先提供兩個(gè)工具方法。

一個(gè)用于打印：

function p(...args) {
  console.log(...args);
}

再寫一個(gè)take，用于從迭代器中截取指定數(shù)量的元素。

function take(iter, n) {
  const list = [];
  for (const value of iter) {
    list.push(value);
    if (list.length === n) {
      break;
    }
  }
  return list;
}

然后就可以輸出fib序列的前20個(gè)元素了

p(take(fibs(), 20));

不知不覺走遠(yuǎn)了，回到題目才發(fā)現(xiàn)有點(diǎn)搞不定。

雖然題目中存在著迭代結(jié)構(gòu)，但數(shù)據(jù)本質(zhì)是immutable的，而上面兩個(gè)版本的實(shí)現(xiàn)，第一個(gè)是采用普通的面向?qū)ο髞韺?shí)現(xiàn)，每次調(diào)用方法得到結(jié)果的同時(shí)，也修改了對(duì)象的狀態(tài)，為下一次調(diào)用做好準(zhǔn)備。
第二個(gè)是生成器函數(shù)，依靠它產(chǎn)生的迭代器不斷迭代得到結(jié)果， 但迭代的同時(shí)也會(huì)修改其內(nèi)部狀態(tài)。

這種依靠維護(hù)對(duì)象狀態(tài)變化來解決問題是面向?qū)ο缶幊痰奶攸c(diǎn)，學(xué)習(xí)面向?qū)ο缶幊叹褪翘接懭绾胃玫靥幚砗脿顟B(tài)的變化，如何把狀態(tài)以一種更合理的方式劃分到不同的對(duì)象中，如何合理地處理好各對(duì)象之間的關(guān)系，使它們的連接更加清晰簡單，這是面向?qū)ο笤瓌t和模式所追求的。

堂堂面向?qū)ο缶透悴欢ㄟ@活？

呃，不變(Immutable)也可以啦：

class Fib {
  constructor(prev = 0, cur = 1) {
    this.prev = prev;
    this.cur = cur;
  }
  
  get value() {
    return this.prev;
  }
  
  next() {
    return new Fib(this.cur, this.prev + this.cur);
  }
}

然后看看成果：

const r0 = new Fib();
p(r0.value);

const r1 = r0.next();
p(r1.value);

const r5 = r1.next().next().next().next();
p(r5.value);

let r = new Fib();
for (let i = 0; i < 19; i++) {
  r = r.next();
}
p(r.value);   // r20

真是披著OO的皮，操著FP的心，算是接近題目的答案了。

再加點(diǎn)語法糖就搞定了：

function funlike(o) {
  const fn = () => funlike(o.next());
  fn.value = o.value;
  return fn;
}

結(jié)果在這里：

const root = funlike(new Fib());
p("root", root.value);

const c1 = root();
p("c1", c1.value);

const c2 = c1();
p("c2", c2.value);

const c3 = c2();
p("c3", c3.value);

const c10 = c3()()()()()()();
p("c10", c10.value);
p("c3", c3.value);
p("root", root.value);

感覺不是很簡潔呀，通過一個(gè)class兜了一大圈，
重構(gòu)精簡一下不過5句話：

function fibworld([prev, cur] = [0, 1]) {
  const fn = () => fibworld([cur, prev + cur]);
  fn.value = prev;
  return fn;
}

這樣使用：

const d0 = fibworld();
p("d0", d0.value);

const d1 = root();
p("d1", d1.value);

const d2 = d1();
p("d2", d2.value);

const d3 = d2();
p("d3", d3.value);

const d10 = d3()()()()()()();
p("d10", d10.value);
p("d3", d3.value);
p("d0", d0.value);

答案太簡單，下面嘗試把問題復(fù)雜化， 學(xué)習(xí)時(shí)我們要把簡單問題復(fù)雜化，如此才能在工作中把復(fù)雜問題簡單化。

上面我們實(shí)現(xiàn)了一個(gè)函數(shù)，使用這個(gè)函數(shù)可以源源不斷地產(chǎn)生斐波那契數(shù)，我們經(jīng)常需要源源不斷地產(chǎn)生一些東西， 為此我們定義一個(gè)標(biāo)準(zhǔn)的對(duì)象來表示這種可以源源不斷地產(chǎn)生東西的行為，給它一個(gè)很酷的名字：無窮流。

{
  value: {any}      // 值
  next: {function}  // 產(chǎn)生下一個(gè)對(duì)象
}

比如我們寫一個(gè)一直輸出1的流

function ones() {
  return {
    value: 1,
    next: () => ones()
  };
}

這還用了遞歸呀，還好問題本身比較簡單，應(yīng)該不會(huì)繞暈。

為了能更好地觀察無窮流產(chǎn)生的元素，也需要一個(gè)take:

function take(stream, n) {
  return n > 0 ? [stream.value].concat(take(stream.next(), n - 1)) : [];
}

啊哦，這回的遞歸可真的繞暈了， 其實(shí)寫成迭代也可以，主要是因?yàn)橄旅鏁?huì)不斷用到遞歸所以先習(xí)慣一下：

function take(stream, n) {
  const list = [];
  for (let i = 0; i < n; i++) {
    list.push(stream.value);
    stream = stream.next();
  }
  return list;
}

然后嘗試打印一下：

log(take(ones(), 10));
// [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

這有點(diǎn)無聊，我們?cè)賮硪粋€(gè)自然數(shù)：

function ints(n = 0) {
  return {
    value: n,
    next: () => ints(n + 1)
  };
}

log(take(ints(), 10));
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

重點(diǎn)來了，關(guān)鍵是我們可以像操作數(shù)據(jù)一下操作這個(gè)流。

比如把兩個(gè)流相加：

function add(a, b) {
  return {
    value: a.value + b.value,
    next: () => add(a.next(), b.next())
  };
}

然后我們就可以計(jì)算1+1=2

function twos() {
  return add(ones(), ones());
}

一個(gè)2到底的流：

log(take(twos(), 10));
// [2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

自然數(shù)流也可以使用add得到：

function ints() {
  return {
    value: 0,
    next: () => add(ones(), ints())
  }
}

log(take(ints(), 10));
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

現(xiàn)在你覺得什么是自然數(shù)呢？

真正的重點(diǎn)來了，我們可以使用類似的方法產(chǎn)生斐波那契流：

function fibs() {
  return {
    value: 0,        // 第1個(gè)元素是0
    next: () => ({
      value: 1,      // 第2個(gè)元素是1
      next: () => add(fibs(), fibs().next())   // 相加。。。
    })
  };
}

這真的能工作！

log(take(fibs(), 20));
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

我們又不知不覺接近題目的答案，只是這次換了一種方法， 同樣也要加點(diǎn)語法糖：

function funlike(stream) {
  const fn = () => funlike(stream.next());
  fn.value = stream.value;
  return fn;
}

結(jié)果就產(chǎn)生了另一個(gè)斐波那契世界：

const root = funlike(fibs());
log("root", root.value);

const c1 = root();
log("c1", c1.value);

const c2 = c1();
log("c2", c2.value);

const c3 = c2();
log("c3", c3.value);

const c10 = c3()()()()()()();
log("c10", c10.value);
log("c3", c3.value);
log("root", root.value);

我們可以像操作數(shù)據(jù)一樣操作流，這意味著除了普通的add, 我們還可以filter, map, reduce，于是所有原本只對(duì)列表操作的美好東西都可以使用到流身上。

流同時(shí)還兼具過程式for循環(huán)語句節(jié)儉的特性，只進(jìn)行必要的計(jì)算。

除此之外，更重要的是它還可以自由組合。

假設(shè)現(xiàn)在實(shí)現(xiàn)一個(gè)需求：

從斐波那契序列出找出>1000的2個(gè)素?cái)?shù)。

如果是過程式的方法，實(shí)現(xiàn)起來也不難，就是幾段實(shí)現(xiàn)細(xì)節(jié)的代碼會(huì)揉在一起，要是再添點(diǎn)邏輯就會(huì)糊了。
而如果采用組合的方式，我們可以這樣：

斐波那契序列，我們已搞定

查找素?cái)?shù)，所以得實(shí)現(xiàn)一個(gè)filter用于過濾，接下來會(huì)做

查找>1000的數(shù)，使用第2步的filter即可。

前2項(xiàng)，使用已實(shí)現(xiàn)的take即可

素?cái)?shù)值，這個(gè)小時(shí)候?qū)戇^很多次，應(yīng)該也不難。

根據(jù)目前的分析，我們只需要實(shí)現(xiàn)一個(gè)filter和一個(gè)isPrime即可。

先回憶小時(shí)候的isPrime:

function isPrime(n) {
  if (n < 2 || n % 2 === 0) {
    return false;
  }
  
  const len = Math.sqrt(n)
  for (let i = 2; i <= len; i++) {
    if (n % i === 0) {
      return false;
    }
  }
  return true;
}

我做了點(diǎn)優(yōu)化：

偶數(shù)就不檢測了

只整除到平方根之前的數(shù)，因?yàn)楦蟮臄?shù)沒必要除。

下面是我們關(guān)心的filter:

function filter(stream, fn) {
  const {value} = stream;
  if (fn(value)) {
    return {value, next: () => filter(stream.next(), fn)};
  }
  return filter(stream.next(), fn);
}

接下來就可以直接搞定了：

log(take(filter(filter(fibs(), n => n > 1000), isPrime), 2))
// [1597, 28657]

這里有兩個(gè)問題，第一個(gè)是組合的語句是倒裝句形式，可惜js中沒有管道操作符，只能依靠鏈?zhǔn)讲僮鲀?yōu)化一些，第二個(gè)是素?cái)?shù)的計(jì)算有點(diǎn)慢，卡了1s鐘。

實(shí)現(xiàn)一個(gè)函數(shù)，用于支持鏈?zhǔn)讲僮鳌?/p>

function chainable(fns) {
  return init => {
    const ret = {value: init};
    for (const k in fns) {
      ret[k] = (...args) => {
        args.unshift(ret.value);
        ret.value = fns[k](...args);
        return ret;
      };
    } 
    return ret;
  };
}

const $ = chainable({ log, take, filter, fibs, isPrime });

然后上面的語句就可以改寫成：

$()
.fibs()
.filter(n => n > 1000)
.filter(isPrime)
.take(2)
.log();

至于素?cái)?shù)檢測慢的問題，可以利用費(fèi)馬小定理來解決。

定理指出，對(duì)于任意一個(gè)素?cái)?shù)p，滿足以下等式：

Math.pow(base, p - 1) % p === 1

反過來也基本成立，所以我們可以隨機(jī)選一些base，檢測等式是否成立來判斷是否為素?cái)?shù)，
需要說明的是，這是個(gè)概率算法，只能保證在大概率上是素?cái)?shù)，滿足此定理但不是素?cái)?shù)的數(shù)被稱為偽素?cái)?shù)，比如 341 = 11 * 31

這里主要的邏輯是乘法除模運(yùn)算，需要點(diǎn)技巧，因?yàn)檎Ｋ銛?shù)字太大了會(huì)越界。

使用邊取模邊乘的方式來解決越界問題，因?yàn)椋?a * b % c === ((a % c) * (b % c)) % c

對(duì)于偶數(shù) pow(base, exp) --> square(pow(base, exp / 2))

對(duì)于奇數(shù) pow(base, exp) --> base * pow(base, exp - 1) --> base * 偶數(shù)情況

這就把計(jì)算復(fù)雜度降到對(duì)數(shù)級(jí)。

function expmod(base, exp, m) {
  if (exp === 0) {
    return 1;
  }
  if (exp % 2 === 0) {
    return square(expmod(base, exp / 2, m) % m;
  }
  return expmod(base, exp - 1, m) * base % m;
}

function square(x) {
  return x * x;
}

接下來的實(shí)現(xiàn)就比較直接

function quickCheck(p) {
  if (p === 2) {
    return true;
  }
  if (p % 2 === 0) {
    return false;
  }
  if (p > 2) {
    // 隨機(jī)選擇10個(gè)數(shù)作為底，使用以上公式進(jìn)行驗(yàn)證，全都通過則判定為素?cái)?shù)
    return Array(10).fill(1).every(() => {
      let base = rand(p);
      base = base > 1 ? base : 2;
      return expmod(base, p - 1, p) === 1;
    });
  }
  return false;
}

function rand(n) {
  Math.floor(Math.random() * n);
}

簡單寫個(gè)函數(shù)比較一下兩者的執(zhí)行速度差異：

function timing(fn) {
  return (...args) => {
    const now = Date.now();
    fn(...args);
    const cost = Date.now() - now;
    log(`${fn.name} cost ${cost}ms`);
  }
}

選兩個(gè)比較大的素?cái)?shù)測試下

log(timing(isPrime)(100001651));
log(timing(quickCheck)(100001651));

在我的機(jī)子上輸出：

isPrime cost 6ms
quickCheck cost 1ms

最后總結(jié)一下：

在面向?qū)ο缶幊讨校覀兺ㄟ^構(gòu)建一個(gè)個(gè)具有狀態(tài)的對(duì)象來描述問題域，這些對(duì)象的狀態(tài)會(huì)隨著系統(tǒng)的運(yùn)行而變化，這些狀態(tài)被封裝在對(duì)象內(nèi)部，原則上對(duì)外界不可見。對(duì)象和對(duì)象之間會(huì)建立各種連接（包含、引用、繼承等），然后通過消息（方法調(diào)用）互動(dòng)和協(xié)作。
所以在面向?qū)ο缶幊讨校覀冃枰P(guān)注對(duì)象的劃分是否合理，對(duì)象和對(duì)象之間的連接方式是否經(jīng)得起折騰。

在函數(shù)式編程中，我們讓數(shù)據(jù)暴露在陽光下，而不是隱藏在對(duì)象內(nèi)部；我們讓這些數(shù)據(jù)流過一個(gè)個(gè)簡潔的轉(zhuǎn)換器最終得到我們需要的樣子，而不是直接修改它。即：

1. Explicit state instead of implicit state
2. transformation instead of mutation

通過探索流這種數(shù)據(jù)結(jié)構(gòu)，我們知道數(shù)據(jù)不僅可以代表一時(shí)，而且可以代表一世。
在面向?qū)ο箢I(lǐng)域，對(duì)象的狀態(tài)隨著時(shí)間的變化而變化，任何某一時(shí)刻只代表當(dāng)時(shí)的狀態(tài)，而流這種結(jié)構(gòu)能夠讓我們同時(shí)擁有所有狀態(tài)，因?yàn)樗枋龅氖钱a(chǎn)生狀態(tài)的規(guī)則。
就像三維生命只能擁有當(dāng)下，而更高維的生命可以去往任何時(shí)刻。