编程任务之：打造斐波那契世界

摘要：以前的编程任务多数是要求打印出序列前项的值，接口往往像这样然后我们巴拉巴拉用一个循环搞定，而这次重点在于接口，需要实现一个斐波那契序列发生器。

本次我领到的任务如下：

任务：

你正在打造一个斐波那契世界，这是一个函数式的世界，
在这个世界中每个生命都是一个函数

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

通过探索流这种数据结构，我们知道数据不仅可以代表一时，而且可以代表一世。
在面向对象领域，对象的状态随着时间的变化而变化，任何某一时刻只代表当时的状态，而流这种结构能够让我们同时拥有所有状态，因为它描述的是产生状态的规则。
就像三维生命只能拥有当下，而更高维的生命可以去往任何时刻。