函数式编程（Functional Programming）

一、函数式编程思维

1.1 前言

范畴论Category Theory

函数式编程是范畴论的数学分支，认为世界上所有概念体系都可以抽象成一个个范畴
彼此之间存在某种关系概念、事务、对象等等，都构成范畴。任何事物只要找出他们之间的关系，就能定义
箭头表示范畴成员之间的关系，正式的名称叫做”态射“（morphism）。范畴论认为，同一个范畴的所有成员，就是不同状态的”变形“（transformation）。通过”态射“，一个成员可以”变形“成另一个成员。

1.2 基础理论

理论

知乎上的一个回答很好，内容太多就不一一复制了

JS中理解

数学中的函数书写如下形式\(f(x)=y\) . 一个函数F，以X作为参数，并返回输出Y。要求：
- 函数必须总是接受一个参数
- 函数必须返回一个值
- 函数只依赖于参数（X）而不是外部环境运行、对于给定的X只会输出唯一的Y
函数式编程不是用函数来编程，也不是传统的面向过程编程。主旨在于将复杂的函数转换成简单的函数（计算理论，或者递归论，或者\(\lambda\)演算）。运算过程尽量写成一系列嵌套的函数调用
通俗写法 function xx(){}区别开函数和方法。方法要与指定的对象绑定、函数可以直接调用
JS是披着C外衣的Lisp （OO是用function的prototype来实现的）
真正的火热是随着React的高阶函数而逐步升温

FP特征

函数式”第一等公民“，可以赋值给其他变量，也可以作为参数传入其他函数，或者作为别的函数的返回值
只用”表达式“，不用”语句“
没有”副作用“
不修改状态
引用透明（函数运行只靠参数且相同的输入总是获得相同的输出）

二、函数式编程常用核心概念

2.1 纯函数

纯函数特征

对于相同的输入，永远得到相同的输出
没有任何可观察的副作用，也不依赖于外部环境的状态

例如Array.slice是纯函数，而Array.splice不是

优缺点

优点：降低系统复杂度，并因为输出是可预测的，因此能做缓存，以lodash为例

import _ from 'lodash';
var sin = _.memorize(x => Math.sin(x));

// First time can be slower
var a = sin(1);

// with session, it can run faster
var b = sin(1);

缺点：可能造成hard code，拓展性比较差

// not a Pure Function
var min = 18;
var checkage = age => age > min;

// Pure Function
var checkage = age => age > 18;

对于缺点，可以考虑用柯里化（curried function）

2.2 纯度和幂等性

幂等性是指执行无数次后还具有相同的效果，同样的参数运行一次函数应该与连续两次结果一致。幂等性在函数式编程中与纯度相关，但又不一致。

例如 \(Math.abs(Math.abs(-42))\)

2.3 偏应用（partial application）函数

定义

传递给函数一部分参数来调用它，让它返回一个函数去处理剩下的参数
偏函数之所以”偏“，就在于其职能处理那些能与至少一个case语句匹配的输入，而不能处理所有

实现

const partial = (fn, ...args) => (...moreArgs) => 
fn(...args, ...moreArgs)

使用

const add = (a, b, c) => a + b + c
const add5 = partial(add, 2, 3)
add5(4) // output: 9

其实bind也是一种FAP

const add5 = add.bind(null 2, 3)

2.4 柯里化

柯里化（Curried）通过PAF实现，它是把一个多参数函数转换为一个嵌套一元函数的过程。传递给函数一部分参数来调用它，让它返回一个函数去处理剩下的函数

const curry = (fn, args=[]) => (...moreArgs) => (arg => (arg.length === fn.length ? fn(...arg) : curry(fn, arg)))([...args, ...moreArgs])

let curryTest = curry((a,b,c,d) => a + b + c + d);
curryTest(1,2,3)(4); // 10
curryTest(1,2)(3)(4); // 10
curryTest(1,2)(3,4); // 10

有柯里化就有反柯里化，柯里化是固定部分参数，创建针对性更强的函数，而反柯里化则相反，为了扩大适用范围，使本来只有特定对象才适用的方法，拓展到更多的对象

Function.prototype.uncurring = function(){
    var self = this;
    return function() {
        var obj = Array.prototype.shift.call(arguments);
        return self.apply(obj, arguments);
    };
};

// 假设上例中的curryTest已存在
var ucTest = curryTest.uncurring();
ucTest(null, 1,2,3,4); // 10

var push = Array.prototype.push.uncurring();
var a = {};
push(a,1,2,3,4,5);
console.log(a); // [1,2,3,4,5]

柯里化是一种”预加载“函数的方法，也可以当做对参数的缓存，是一种非常高效的编写函数的方法

柯里化 VS 偏应用

柯里化的参数列表是从左向右的，如果使用setTimeout类似的函数就得做额外的封装

// curry vs PAF
// 对于setTimeout需要将timeout和fn反置的函数，就不适合采用从左向右的curry，而适合使用偏函数PAF
const delayMS = (timeout, fn) => setTimeout(fn, timeout);

const setTimeoutWrapper = (timeout, fn) => {
	setTimeout(fn, timeout);
}

var delayTenMS = curry(setTimeoutWrapper)(10);
delayTenMS(() => {console.log('code guy')});

需要setTimeoutWrapper，显得臃肿，如果用PAF则会比较简洁

const partial = (fn, ...args) => (...moreArgs) => fn(...moreArgs, ...args);
var delayTenMS = partial(setTimeout, 10);
delayTenMS(() => {console.log('code guy')});

2.5 函数组合

compose处理洋葱代码h(g(f(x)))，

compose(f, compose(g,h))
compose(compose(f,g),h)
compose(f,g,h)

compose只能组合接受一个参数的函数，类似于filter、map（投影函数：总是在应用转换操作，通过传入高阶参数后返回数组），不能被直接组合的可以借助偏函数包裹后继续组合。

我们需要函数组合子交换compose的执行方向，使得compose类似于管道pipe，组合子可以组合其他函数（或其他组合子），并作为逻辑控制单元的高阶函数，组合子通常不声明任何变量，也不包含任何业务逻辑，他们旨在管理函数程序执行流程，并在链式调用中对中间结果进行操作

常见组合子：

辅助组合子: nothing, identity, defaultTo, always
函数组合子: gather, spread, reverse, partial, partialRight, curry, tap, alt, tryCatch, seq, converge, map, useWith, reduce, compose
谓语组合子: filter, group, sort
其他: juxt

上述均属于SKI组合子

2.6 Point Free

Point Free即把一些对象自带的方法转化为纯函数

例如下面这个函数

const f = str => str.toUpperCase().split('');

写成point free则拆分为，从而使得split和toUpperCase不局限于str的调用

var toUpperCase = word => word.toUpperCase();
var split = x => (str => str.split(x));

var f = compose(split(' '), toUpperCase);
f("abcd efgh");

这种风格能够帮助我们减少不必要的命名，让代码保持简洁和通用

2.7 惰性链、惰性求值、惰性函数

lazyChain即，一个链式调用上，到最后一个函数上才执行操作

当输入很大但只有一个小的子集有效时，避免不必要的函数调用就是所谓的惰性求值

惰性求值、多形函数和惰性链相似，只是赋值过程中可能有很多判断，而一旦达到某个分支，就可以把函数同名替换，从而避免之后执行该函数还要走很多不必要的判断

三、更加专业术语

3.1 高阶函数HOC

函数当参数，返回一个封装的函数，达到更高程度的抽象

3.2 尾调用优化PTC

return相同函数，即尾递归调用（Tail Call）
使得尾递归调用不开启新的函数栈，只return function，称为尾递归优化（Proper Tail Call）
浏览器到现在没有实现PTC，V8官方解释主要有2点原因：
- PTC隐式优化，并不知道是否是开发者所想要的行为
- PTC隐藏了函数调用stack，难以debug
如果要强制开启PTC，有以下3种方法（STC）：
1. return continue fn;
2. !return fn;
3. #function

也可以使用蹦床函数（trampoline）解决尾递归为题，思想是转换为while循环

function trampoline(f) {
  while(f && f instanceof Function) {
    f = f();
  }
  return f;
}

3.3 闭包

闭包会造成内存泄露，外层的函数执行完毕后，栈上的调用帧被释放，但是堆上的作用域并不释放。需要用weekmap

3.4 容器、Functor

我们可以把”范畴“想象成是一个容器，里面包含两样东西。值（value）、值的变形关系，也就是函数。

范畴论使用函数表达范畴之间的关系。

伴随着范畴论的发展，就发展处一整套函数的运算方法。这套方法起初只用于数学运算，后来有人将它在计算机上实现了，就编程了今天的Functional Programming。

本质上，函数式编程只是范畴论的运算方法，跟数理逻辑、微积分、行列式是同一类东西，都是数学方法，只是碰巧它能用来写程序。

函数不仅可以用于同一个范畴之中值的转换，还可以用于将一个范畴转换成另一个范畴。这就涉及到了函子（Functor）。

函子是函数式编程里面最重要的数据类型，也是基本的运算单位和功能单位。它首先是一种范畴，也就是说，是一个容器，包含了值和变性关系。比较特殊的事，它的变形关系可以依次作用于每一个值，将当前容器变形成另一个容器。

用Redux解释容器和函子，就是state为容器，action为转换function，reducer为map函数，从而Redux能够更新state容器，所以Redux就是一个函子

常见的函子有

Pointed
Maybe
Either
AP
IO（脏）
Monad（pipe）

下面以代码为例，详细介绍每一个函子

3.4.1 Container

var Container = function(x) {
  this.__value = x;
}
// FP assumes that Functor contains a function named 'of'
Container.of = x => new Container(x);
//Container.of('abcd');
// Generally, Functor is just a Container with map function, this map function will map each value in the Container into another Container
Container.prototype.map = function(f) {
  return Container.of(f(this.__value));
}
Container.of(3)
	.map(x => x + 1)	// return Container(4)
	.map(x => 'Result is ' + x) // return Container('Result is 4')

3.4.2 Functor

class Functor {
  constructor(val) {
    this.val = val;
  }
  
  map(f) {
    return new Functor(f(this.val))
  }
}
(new Functor(2)).map((v) => v + 2); // Functor(4)

3.4.3 Pointed

Pointed是Functor的子集，上述Functor生成新的函子的时候，用了new命令，仿佛是OO，因此FP一般约定，函子有一个of方法，用于生成新的Container

Functor.of = function(val) {
  return new Functor(val);
}
// Exp: Array.of("")

// Functor的例子可以改为
Functor.of(2).map((v) => v + 2); // Functor(4)

3.4.4 Maybe

Maybe用于处理错误和异常。由于容器内部的值可能是null，undefined等空值，而外部函数未必有相应的错误处理机制，从而导致错误。

Functor.of(null).map(s => s.toUpperCase());

class Maybe extends Functor {
  map(f) {
    return this.val ? Maybe.of(f(this.val)) : Maybe.of(null);
  }
}

Maybe.of(null).map(s => s.toUpperCase()); // Maybe(null)

Maybe function implements way

var Maybe = function(x) {
  this.__value = x;
}
Maybe.of = function(x) {
  return new Maybe(x);
}
Maybe.prototype.map = function(f) {
  return this.isNothing() ? Maybe.of(null) : Maybe.of(f(this.__value));
}
Maybe.prototype.isNothing = function() {
  return (this.__value === null || this.__value === undefined);
}
// 原型来自Haskell

3.4.5 Either

Functor能做的事太少了，try/catch/throw并不是”纯“的，因为它从外部接管了我们的函数，并且在这个函数出错时抛弃了它的返回值。

例如Promise是可以调用catch来集中处理错误的

事实上Either并不只是用来做错误处理的，它表示了逻辑或，范畴学里的coproduc

class Either extends Functor {
  constructor(left, right) {
    this.left = left;
    this.right = right;
  }
  
  map(f) {
    return this.right?
      Either.of(this.left, f(this.right)) :
    	Either.of(f(this.left), this.right);
  }
}

Either.of = function(left, right) {
  return new Either(left, right);
}

// Example
var addOne = function(x) {
  return x + 1;
}

Either.of(5, 6).map(addOne); // Either(5, 7);
Either.of(1, null).map(addOne); // Either(2, null);
Either.of({address: 'xxx'}, currentUser.address).map(updateField)

错误处理：如何代替try…catch呢

var Left = function(x) {
  this.__value = x;
}
var Right = function(x) {
  this.__value = x;
}

Left.of = function(x) {
  return new Left(x);
}
Right.of = function(x) {
  return new Right(x);
}

// 这里不同！
Left.prototype.map = function(f) {
  return this;
}
Right.prototype.map = function(f) {
  return Right.of(f(this.__value));
}

Left和Right唯一的区别就在于，Left不对容器做任何事情，只是简单的拿进来又扔出去，这个特性意味着，Left可以用来传递一个错误消息

var getAge = user => user.age ? Right.of(user.age) : Left.of("ERROR!");

getAge({name: 'stark', age: '21'}.map(age => 'Age is ' + age)); // Right('Age is 21')
getAge({name: 'stark'}).map(age => 'Age is ' + age); // Left('ERROR!')

Left可以让调用链中任意一环的错误立刻返回到调用链的尾部，这给我们错误处理带来了很大的方便，再也不用一层层的try/catch了。

3.4.6 AP

函子里面包含的值，完全可能是函数。我们可以想象这样一种情况，一个函子的值是数值，另一个函子的值是函数。而AP函子就是处理这样的转换

class AP extends Functor {
  ap(F) {
    return AP.of(this.val(F.val));
  }
}
AP.of(addTwo).ap(Functor.of(2));

3.4.7 IO

IO的__value是一个函数，它把不纯的操作（比如IO、网络请求、DOM）包裹到一个函数内，从而延迟这个操作的执行。直到最后一步执行，这样讲外部依赖放置一个地方，从而减小副作用。

因此IO也算一个惰性求值

import _ from 'lodash';
var compose = _.flowRight;

var IO = function(f) {
  this.__value = f;
}

IO.of = x => new IO(_ => x);

IO.prototype.map = function(f) {
  return new IO(compose(f, this.__value))
};

class IO extends Monad {
  map(f) {
    return IO.of(compose(f, this.__value))
  }
}

var fs = require('fs');
var readFile = function(filename) {
  return new IO(function(){
    return fs.readFileSync(filename, 'utf-8');
  });
}

readFile('./user.txt')
.flatMap(tail)
.flatMap(print)
//等同于
readFile('./user.txt')
.chain(tail)
.china(print)

3.4.8 Monad

Monad简单来说就是对函子的拆箱装箱，它有一个flatMap方法，与map方法作用相同，唯一的区别是如果生成了一个嵌套函子，它会取出后者内部的值，保证返回的永远是一个单层的容器，不会出现嵌套的情况。

class Monad extends Functor {
  join() {
    return this.val;
  }
  flatMap(f) {
    return this.map(f).join();
  }
}

如果函数f返回的是一个函子，那么this.map(f)就会生成一个嵌套的函子。所以，join方法保证了flatMap方法总是返回一个单层的函子。这意味着嵌套的函子会被铺平（flatten）

四、流行的几大函数式编程库

RxJS：实现函数响应式编程（Functional Reactive Programming，FRP），Observer，流式处理，被各大浏览器引擎引入实现，因此反而没有用武之地。RxJS从函数式编程范式中借鉴了很多东西，比如链式函数调用；惰性求值等等
cycleJS：基于RxJS，它是一个彻彻底底的FRP理念的框架，和React一样支持virtual DOM、JSX语法，但现在似乎没看到大型的应用经验
underscoreJS：underscore是一个js工具库，它提供了一整套函数式编程的实用功能，但是没有拓展任何js内置对象。它解决了这个问题：”如果我面对一个空白的HTML页面，并希望立即开始工作，我需要什么？“它弥补了jQuery没有实现的功能，同时又是Backbone必不可少的部分。Underscore提供了100多个函数，包括常用的：map、filter、invoke…当然还有更多专业的辅助函数，如：函数绑定、js模板功能、创建快速索引、强类型相等测试等等。
lodashJS、lazy（惰性求值）：lodash是一个具有一致接口、模块化、高性能等特性的js工具库，是underscore的fork，其最初目标也是”一致的跨浏览器行为，并改善性能“。lodash采用延迟计算，这意味着lodash可以进行shortcut、fusion这样的优化，通过合并链式大大降低迭代的次数，从而大大提升其执行性能
ramdajs：ramda是一个非常优秀的js工具库，跟同类比更函数式，主要体现在以下几个原则
- Ramda的数据一律放在最后一个参数，理念是”function first，data last“
- ramda里面提供的函数全部都是curry的，也就是说，所有多参数的函数，默认都可以单参数使用
- ramda推崇point free
- ramda有个非常好用的参数占位符R._大大减轻了函数在pointfree过程中参数位置的问题
因此相比underscore/lodash，ramda要干净很多

五、实际应用场景

5.1 易调试、热部署、并发

函数式编程中的每个符号都是const的，于是没有什么函数会有副作用。谁也不能再运行时修改任何东西，也没有函数可以修改在它的作用域之外的什么值给其他函数使用。因此非常干净。
函数式编程不需要考虑”死锁“（dead lock），因为它不修改变量，不存在锁线程的问题，不必担心一个线程的数据，被另一个线程修改，所以可以放心将工作分摊到多个线程，部署”并发编程“（concurrency）
函数式编程中所有状态就是传给函数的参数，而参数都是存储在栈上的，这一特性让软件的热部署变得十分简单。只要比较一下正在运行的代码以及新的代码获得一个diff，然后用这个diff更新现有的代码，新代码的热部署就完成了。

5.2 单元测试

严格的函数式编程，由于固定的输入会得到固定的输出，因此是单元测试者的梦中仙境（wet dream），不用考虑函数的调用顺序，不必谨慎的设置外部状态。

5.3 总结

函数式编程不是万能的，相反，它应当被视为我们现有工具箱的一个很自然的补充——它带来了更高的可组合型，灵活性以及容错性。现代的JS库已经开始尝试拥抱函数式编程的概念以及获取这些优势。Redux作为一种FLUX的变种实现，核心理念也是状态机和函数式编程。

Software Engineering说没有银弹，因此需要选择场景使用。很多实际应用中是很难用函数式去表达的，选择OOP亦或是其他编程范式或许会更简单。但使用函数式编程也能有效降低系统复杂度，提高系统可读性、可维护性和开发测试效率。

函数式编程与JS

老袁の相声总结2

函数式编程（Functional Programming）

一、函数式编程思维

1.1 前言

1.2 基础理论

二、函数式编程常用核心概念

2.1 纯函数

2.2 纯度和幂等性

2.3 偏应用（partial application）函数

2.4 柯里化

柯里化 VS 偏应用

2.5 函数组合

2.6 Point Free

2.7 惰性链、惰性求值、惰性函数

三、更加专业术语

3.1 高阶函数HOC

3.2 尾调用优化PTC

3.3 闭包

3.4 容器、Functor

3.4.1 Container

3.4.2 Functor

3.4.3 Pointed

3.4.4 Maybe

3.4.5 Either

3.4.6 AP

3.4.7 IO

3.4.8 Monad

四、流行的几大函数式编程库

五、实际应用场景

5.1 易调试、热部署、并发

5.2 单元测试

5.3 总结

CATALOG

FEATURED TAGS

FRIENDS

函数式编程 （Functional Programming）

一、函数式编程思维

1.1 前言

1.2 基础理论

二、函数式编程常用核心概念

2.1 纯函数

2.2 纯度和幂等性

2.3 偏应用（partial application）函数

2.4 柯里化

柯里化 VS 偏应用

2.5 函数组合

2.6 Point Free

2.7 惰性链、惰性求值、惰性函数

三、更加专业术语

3.1 高阶函数HOC

3.2 尾调用优化PTC

3.3 闭包

3.4 容器、Functor

3.4.1 Container

3.4.2 Functor

3.4.3 Pointed

3.4.4 Maybe

3.4.5 Either

3.4.6 AP

3.4.7 IO

3.4.8 Monad

四、流行的几大函数式编程库

五、实际应用场景

5.1 易调试、热部署、并发

5.2 单元测试

5.3 总结

CATALOG

FEATURED TAGS

FRIENDS

函数式编程（Functional Programming）