摘要：以前的編程任務多數是要求打印出序列前項的值，接口往往像這樣然后我們巴拉巴拉用一個循環搞定，而這次重點在于接口，需要實現一個斐波那契序列發生器。

本次我領到的任務如下：

任務：

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

root是這個世界的祖先
root.value; // 1

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

const child = root(); // 創建下一代 
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 // 已經不知道是多少了

請創建這個世界的祖先 root

任務
完成這個斐波那契世界代碼

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

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

以前的編程任務多數是要求打印出序列前n項的值，接口往往像這樣

function fibs(n) {
 ...
}

然后我們巴拉巴拉用一個循環搞定， 而這次重點在于接口，需要實現一個斐波那契序列發生器。

我快速實現了第一個版本：

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語句打印一下，看看有沒有弄對。

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

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

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

對于生成器，我們可以使用for of來迭代，為了代碼更優雅，先提供兩個工具方法。

一個用于打印：

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

再寫一個take，用于從迭代器中截取指定數量的元素。

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

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

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

不知不覺走遠了，回到題目才發現有點搞不定。

雖然題目中存在著迭代結構，但數據本質是immutable的，而上面兩個版本的實現，第一個是采用普通的面向對象來實現，每次調用方法得到結果的同時，也修改了對象的狀態，為下一次調用做好準備。
第二個是生成器函數，依靠它產生的迭代器不斷迭代得到結果， 但迭代的同時也會修改其內部狀態。

這種依靠維護對象狀態變化來解決問題是面向對象編程的特點，學習面向對象編程就是探討如何更好地處理好狀態的變化，如何把狀態以一種更合理的方式劃分到不同的對象中，如何合理地處理好各對象之間的關系，使它們的連接更加清晰簡單，這是面向對象原則和模式所追求的。

堂堂面向對象就搞不定這活？

呃，不變(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的心，算是接近題目的答案了。

再加點語法糖就搞定了：

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

結果在這里：

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);

感覺不是很簡潔呀，通過一個class兜了一大圈，
重構精簡一下不過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);

答案太簡單，下面嘗試把問題復雜化， 學習時我們要把簡單問題復雜化，如此才能在工作中把復雜問題簡單化。

上面我們實現了一個函數，使用這個函數可以源源不斷地產生斐波那契數，我們經常需要源源不斷地產生一些東西， 為此我們定義一個標準的對象來表示這種可以源源不斷地產生東西的行為，給它一個很酷的名字：無窮流。

{
  value: {any}      // 值
  next: {function}  // 產生下一個對象
}

比如我們寫一個一直輸出1的流

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

這還用了遞歸呀，還好問題本身比較簡單，應該不會繞暈。

為了能更好地觀察無窮流產生的元素，也需要一個take:

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

啊哦，這回的遞歸可真的繞暈了， 其實寫成迭代也可以，主要是因為下面會不斷用到遞歸所以先習慣一下：

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]

這有點無聊，我們再來一個自然數：

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]

重點來了，關鍵是我們可以像操作數據一下操作這個流。

比如把兩個流相加：

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

然后我們就可以計算1+1=2

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

一個2到底的流：

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

自然數流也可以使用add得到：

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

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

現在你覺得什么是自然數呢？

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

function fibs() {
  return {
    value: 0,        // 第1個元素是0
    next: () => ({
      value: 1,      // 第2個元素是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]

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

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

結果就產生了另一個斐波那契世界：

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);

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

流同時還兼具過程式for循環語句節儉的特性，只進行必要的計算。

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

假設現在實現一個需求：

從斐波那契序列出找出>1000的2個素數。

如果是過程式的方法，實現起來也不難，就是幾段實現細節的代碼會揉在一起，要是再添點邏輯就會糊了。
而如果采用組合的方式，我們可以這樣：

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

查找素數，所以得實現一個filter用于過濾，接下來會做

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

前2項，使用已實現的take即可

素數值，這個小時候寫過很多次，應該也不難。

根據目前的分析，我們只需要實現一個filter和一個isPrime即可。

先回憶小時候的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;
}

我做了點優化：

偶數就不檢測了

只整除到平方根之前的數，因為更大的數沒必要除。

下面是我們關心的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]

這里有兩個問題，第一個是組合的語句是倒裝句形式，可惜js中沒有管道操作符，只能依靠鏈式操作優化一些，第二個是素數的計算有點慢，卡了1s鐘。

實現一個函數，用于支持鏈式操作。

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();

至于素數檢測慢的問題，可以利用費馬小定理來解決。

定理指出，對于任意一個素數p，滿足以下等式：

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

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

這里主要的邏輯是乘法除模運算，需要點技巧，因為正常算數字太大了會越界。

使用邊取模邊乘的方式來解決越界問題，因為： a * b % c === ((a % c) * (b % c)) % c

對于偶數 pow(base, exp) --> square(pow(base, exp / 2))

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

這就把計算復雜度降到對數級。

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;
}

接下來的實現就比較直接

function quickCheck(p) {
  if (p === 2) {
    return true;
  }
  if (p % 2 === 0) {
    return false;
  }
  if (p > 2) {
    // 隨機選擇10個數作為底，使用以上公式進行驗證，全都通過則判定為素數
    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);
}

簡單寫個函數比較一下兩者的執行速度差異：

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

選兩個比較大的素數測試下

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

在我的機子上輸出：

isPrime cost 6ms
quickCheck cost 1ms

最后總結一下：

在面向對象編程中，我們通過構建一個個具有狀態的對象來描述問題域，這些對象的狀態會隨著系統的運行而變化，這些狀態被封裝在對象內部，原則上對外界不可見。對象和對象之間會建立各種連接（包含、引用、繼承等），然后通過消息（方法調用）互動和協作。
所以在面向對象編程中，我們需要關注對象的劃分是否合理，對象和對象之間的連接方式是否經得起折騰。

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

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

通過探索流這種數據結構，我們知道數據不僅可以代表一時，而且可以代表一世。
在面向對象領域，對象的狀態隨著時間的變化而變化，任何某一時刻只代表當時的狀態，而流這種結構能夠讓我們同時擁有所有狀態，因為它描述的是產生狀態的規則。
就像三維生命只能擁有當下，而更高維的生命可以去往任何時刻。