JavaScript 函数式编程

2017-09-27

写作

fp1

函数式编程概念
- 编程范式
- 纯函数 (Purity)
高阶函数
由函数构建函数
- 函数组合 (Function Composition)
- 柯里化(Currying)
- 部分应用 (Partial Application)
递归
- 相互递归
- 尾递归(Tail Calls)
- 蹦床原理(Trampolines)
流行的类库

什么是函数式编程

编程范式
面向数学的抽象(面向函数的编程)
函数作为一等公民(可以像任何其他数据类型一样对待)
Functional Programming Hurts?
纯函数
此函数在相同的输入值时，总是产生相同的输出。函数的输出和当前运行环境的上下文状态无关。
此函数运行过程不影响运行环境，比如不会触发事件、更改环境中的对象、终端输出值等。
相同的输入，永远会得到相同的输出，而且没有任何可观察的副作用

函数式编程的好处

引用透明(Referential transparency)
- 一个表达式能够被它的值替代而不改变程序的行为成为引用透明。
No Side Effect(基于状态不可变性)
易于测试(上下文无关)
可并行计算(时序无关,即不依赖外部的状态也不修改外部的状态，函数调用的结果不依赖调用的时间和位置)
bug自限性(问题不会扩散)

高价函数(HOF)

定义
- 以一个函数作为参数
- 以一个函数作为返回值
应用
- ajax异步回调
- Array的一些方法sort, map,filter,reduce等
- 惰性加载函数,函数节流,实现AOP等

惰性加载函数

var addEvent = function(elem, type, handler) {
    if (window.addEventListener) {
        addEvent = function(elem, type, handler) {
            elem.addEventListener(type, handler, false);
        }
    } else if (window.attachEvent) {
        addEvent = function(elem, type, handler) {
            elem.attachEvent('on' + type, handler);
        }
    }
    addEvent(elem, type, handler);
};
```    
### once
<a class="jsbin-embed" href="//code.h5jun.com/zeco/1/embed?js,console,output">JS Bin on jsbin.com</a><script src="https:////code.h5jun.com/js/embed.min.js?3.40.2"></script>

### throttle(截流函数)

<a class="jsbin-embed" href="//code.h5jun.com/xixo/1/embed?js,console,output">JS Bin on jsbin.com</a><script src="https:////code.h5jun.com/js/embed.min.js?3.40.2"></script>

### 函数组合(compose)
接收多个函数作为参数，从右到左，一个函数的输入为另一个函数的输出。
![compose](https://user-images.githubusercontent.com/16514704/30249905-3dc48152-9678-11e7-807e-b30a5419cacf.png)

### compose

```javascript
const compose = (f, g) => (a) => f(g(a))//结合律
//f 和 g 都是函数，a 是在它们之间通过“管道”传输的值
const floorAndToString = compose((val) => val.toString(), Math.floor) // 使用
floorAndToString(12.12)   //=> '12'

function reducer(state, action){
  return action(state);
}
function reverse(str){
  return str.split('').reverse().join('');
}
function upperCase(str){
  return str.toUpperCase();
}
let str = [reverse, upperCase].reduce(reducer, "hello world!");//=>!DLROW OLLEH

柯里化

将一个多元函数转变为一元函数的过程。每当函数被调用时，它仅仅接收一个参数并且返回带有一个参数的函数，直到传递完所有的参数

//柯里化函数逐渐返回消耗参数的函数，直到所有参数耗尽
const sum = (a, b) => a + b
const curriedSum = (a) => (b) => a + b
curriedSum(3)(4)         // 7
const add2 = curriedSum(2)
add2(10)     // 12

自动柯里化

lodash，understore 和 ramda 有 curry 函数可以自动完成柯里化。

JS Bin on jsbin.com

curry

function curry(fn){
  return function(arg){
    return fn(arg)
  }
}
// 接受一个函数
//返回一个只接受一个参数的函数
//似乎是一个没用的函数?
parseInt(11);//=>11
parseInt(11,2);//=>3
['11','11','11','11'].map(parseInt);//=>[11,NaN,3,4]
['11','11','11','11'].map(curry(parseInt));//=>[11,11,11,11]
//显示控制接受固定以及可选的参数的函数行为

curryN

function curry2(fn){
    return function(secondArg){
        return function(firstArg){
            return fn(firstArg, secondArg)
        }
    }
}
function curry3(fn){
    return function(last){
        return function(middle){
            return function(first){
                return fn(first, middle, last);
            }
        }
    }
}
function curryN(fn){
    //...
}

部分应用(Partial Application)

部分应用也叫偏函数应用是指使用一个函数并将其应用一个或多个参数，但不是全部参数，在这个过程中创建一个新函数。


    //partical application 
    function apply(fn /* partial arguments... */ ) {
    var args = [].slice.call(arguments, 1);
    return function () {
        var _args = [].slice.call(arguments);
        return fn.apply(this, args.concat(_args));
    }
    }
    //es6
    function apply(fn, ...args) {
    return (..._args) => {
        return fn(...args, ..._args);
    };
    }

Partial

// 创建偏函数，固定一些参数
const partical = (f, ...args) =>
// 返回一个带有剩余参数的函数
(...moreArgs) =>
    // 调用原始函数
    f(...args, ...moreArgs)
const add3 = (a, b, c) => a + b + c
// (...args) => add3(2, 3, ...args)
// (c) => 2 + 3 + c
const fivePlus = partical(add3, 2, 3)

fivePlus(4)  // 9

对比

fp3

递归

如果一个函数在内部调用自身本身，这个函数就是递归函数
递归函数的优点是定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。
使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。

相互递归

function isOdd(v) {
	if (v === 0) return false;
	return isEven( Math.abs( v ) - 1 );
}
function isEven(v) {
	if (v === 0) return true;
	return isOdd( Math.abs( v ) - 1 );
}
isOdd( 33333 );	// RangeError: Maximum call stack size exceeded

尾调用(Tail Calls)

指某个函数的最后一步是调用另一个函数

function f(x){
  return g(x);
}
// case1 不属于
function f(x){
  let y = g(x);
  return y;
}
// case2 不属于
function f(x){
  return g(x) + 1;
}

尾递归

尾调用自身，就称为尾递归。
解决递归调用栈溢出的方法是通过尾递归优化(技术上)
在函数返回的时候，调用自身本身，并且，return语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。
ES6标准规定了尾调用不会创建额外的调用帧。在严格模式下尾调用不会造成调用栈溢出。
递归本质上是一种循环操作。纯粹的函数式编程语言没有循环操作命令，所有的循环都用递归实现，这就是为什么尾递归对这些语言极其重要.

求自然数阶乘

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}//复杂度 O(n) 

factorial(5) // 120

//尾递归
function factorial(n, total) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}//复杂度 O(1) 

factorial(5, 1) // 120

求斐波那契数值

function fibonacci (n) {
    return n <= 1 ? 1 : fibonacci(n - 1) + fibonacci(n - 2);
}
fibonacci(40); // 165580141
//经过尾调优化后
function fibonacci (n, ac1, ac2) {
    (ac1 = ac1 || 1), (ac2 = ac2 || 1);
    return n <= 1 ? ac2 :fibonacci(n - 1, ac2, ac1 + ac2);
}
fibonacci(100); // 573147844013817200000
fibonacci(1000); // 7.0330367711422765e+208
fibonacci(10000); // Infinity

递归优化的实现

//转化成while循环
function factorial (n) {
    var fact = 1;
    while (n > 1) {
        fact *= n--;
    }
    return fact;
}

function fibonacci (n) {
    var ac1, ac2, tmp,
        i = ac2 = ac1 = 1;
    while(n > i++) {
        (tmp = ac2),
        (ac2 = ac1 + ac2),
        (ac1 = tmp);
    }
    return ac2;
}

蹦床函数

顾名思义，蹦床函数就是随着递归执行的开始和结束，调用栈会出现入栈、出栈效果，就像是在弹蹦床。

//utility
function trampoline(fun /*, args */) {
  var result = fun.apply(fun, _.rest(arguments));
  while (_.isFunction(result)) {
    result = result();
  }
  return result;
}

trampoline