高阶函数（High-order functions）

[yaofly2012]

一、什么是高阶函数

1.1 一等类函数(First-class Functions)

函数也是对象。

1.2 函数式编程（Functional Programming）

用最简单的话来说，函数式编程就是将函数作为另外一个函数的参数或者返回值。
在函数式编程的世界里面，我们用函数的方式进行思考和编码。

JS里函数就是对象，可以实现函数式编程。

1.3 高阶函数

wiki关于高阶函数的定义：在数学和计算机科学中，高阶函数是至少满足下列一个条件的函数：

1. 接受一个或多个函数作为输入；
2. 输出一个函数。

通俗点说就是高阶函数是那些操作其他函数的函数。
高阶函数就是函数式编程的实现。

1.4 内置的高阶函数

JS内置对象的好多方法都是高阶函数：

1. Array.prototype.map/filter/forEach/reduce/every/some/find/findIndex;
2. Function.prototype.bind;
3. 等等

二、underscore/lodash高阶函数实现分析

1. 防抖（debounce）

2. 节流（throttle）

3. 记忆（memorize）

4. 组合函数（Compose）

是什么是组合函数

函数嵌套调用扁平化处理。有点类似管道，把上一个函数处理结果作为输入传给下一个函数。

相当于嵌套调用split(lowerCase(trim("a,B,C)))

实现-初版

function compose() {
  var funcs = Array.prototype.slice.call(arguments);
  return function composed(result) {
    result = funcs.reduce(function(result, func) {
      result = typeof func === 'function' ? func(result) : result;
      return result;
    }, result);
    
    return result;
  }
}

function add2(a) {
  return a + 2;
}

function multi3(a) {
  return a * 3;
}

var composed = compose(add2, multi3);
var result = composed(1);
console.log(result);

1. 利用Array.prototype.reduce实现的；
2. 各个功能函数从左到右方向执行，即compose(add2, multi3)相当于multi3(add2())；
3. 限制：每个参与组合的功能函数最多只能有一个参数。
   因为上一个函数的返回值只有一个。

underscorejs实现

function compose() {
  var args = arguments;
  var start = args.length - 1; // 缓存了长度，good
  return function() {
    var i = start;
    // 特殊处理初始调用，实参全部透传，故采用`apply`
    var result = args[start].apply(this, arguments);
    // 剩下的功能函数参数固定，统一采用`call`
    while (i--) result = args[i].call(this, result);
    return result;
  };
}

1. 从右到左方向执行，跟嵌套调用的执行顺序保持一致，即compose(add2, multi3)相当于add2(multi3())；
   至于执行方向选择哪种都都道理，不过还是跟明星库保持一致吧。
2. 特殊处理初始调用，实参全部透传组合函数的实参【Nice】；
3. 各个组合函数的调用保留跟组合函数相同的this【Nice】；
   这样组合函数可以通过apply/call方式动态修改this调用了。

lodash实现

Lodash居然没有compose函数。

实现-优化

借鉴underscore和这个博客JS高阶编程技巧--compose函数重新优化下实现：

function compose() {
  var funcs = arguments;
  var funcsCount = arguments.length;

  return function composed() {
    // 参数判断
    if(funcsCount === 0) {
      return;
    }
    var start = funcsCount - 1;
    // 第一个功能函数特殊处理
    var result = typeof funcs[start] === 'function' 
      ? funcs[start].apply(this, arguments)
      : result;

    // 剩下的轮询调用
    while(--start >= 0) {
      result = typeof funcs[start] === 'function' 
        ? funcs[start].call(this, result)
        : result;
    }
   
    return result;
  };
}

1. 增加的参数判断；

redux compose实现

无意中看到Redux库的compose实现，简直简洁到爆炸：

export default function compose(...funcs: Function[]) {
  if (funcs.length === 0) {
    // infer the argument type so it is usable in inference down the line
    return <T>(arg: T) => arg
  }

  if (funcs.length === 1) {
    return funcs[0]
  }

  return funcs.reduce((a, b) => (...args: any) => a(b(...args)))
}

简直炸裂！相较于underscore的实现就少了this透传。但提前转成了函数嵌套调用，执行的时候没有循环了。

参考这个又修改了下之前的实现：

function compose() {
  var funcs = Array.prototype.slice.call(arguments);
  var funcsCount = funcs.length;

  // 参数判断
  if(funcsCount === 0) {
    return function() {};
  }

  // 参数判断
  if(funcsCount === 1) {
    return funcs[0];
  }
  
  return funcs.reduce(function(a, b) {
    return function() {
      return a(b.apply(null, arguments));
    }
  })
}

虽然提前转成嵌套调用，但是实参函数列表有一半的函数都是利用apply方式调用，很难说性能谁的更好。

npm p-pipe

5. 柯里化（Currying）

什么是柯里化

来自wiki定义

是把接受多个参数的函数变换成接受一个单一参数（最初函数的第一个参数）的函数，并且返回接受余下的参数而且返回结果的新函数的技术。

var foo = function(a) {
  return function(b) {
    return a * a + b * b;
  }
}

可以foo(3)(4)方式调用上面的函数。

不过现实中可不用受每次只能传单个参数的限制。

实现-初版

function curry(func) {
  var slice = Array.prototype.slice;
  var initArgs = slice.call(arguments, 1);
  var initArgsCount = initArgs.length;

  return function curried() {
    var args = initArgs.concat(slice.call(arguments));
    
    // 参数还不够，返回新的柯里化方法
    if(args.length < func.length) {
      args.unshift(func);    
      return curry.apply(this, args);
    }
    
    // 参数够了，执行目标函数
    return func.apply(this, args);
  }
}

function disArr(a, b, c, d) {
  return [a, b, c, d];
}

var curryDisArr = curry(disArr, 10, 12);
console.log(curryDisArr(1)(2))

var curryDisArr2 = curry(disArr);
console.log(curryDisArr2(1)(2)(1)(2))

underscore实现

underscore居然没有柯里化函数。

lodash实现

6. 偏函数（Partial Function）

什么是偏函数

偏函数应用（Partial Application）是指固定一个函数的某些参数，然后产生另一个更小元的函数。

跟柯里化的区别

两者概念比较类似，但是存在区别的。

1. 偏函数：偏函数应用是固定一个函数的一个或多个参数，并返回一个可以接收剩余参数的函数；
   一次性给函数降维
2. 柯里化：将函数转化为多个嵌套的一元函数，也就是每个函数只接收一个参数；
   根据调用情况逐步降维

比较有名的内置偏函数Object.prototype.bind。之前一直把它视为柯里化函数。

实现-初版

function partial(func) {
  var slice = Array.prototype.slice;
  var initArgs = slice.call(arguments, 1);

  return function () {
    var args = initArgs.concat(slice.call(arguments));         
    return func.apply(this, args);
  }
}

function disArr(a, b, c, d) {
  return [a, b, c, d];
}

var partialDisArr = partial(disArr, 10, 12);
console.log(partialDisArr(1, 2))

实现上就像个简化版的Object.prototype.bind。
这个实现存在一个问题就是只能对左边的参数依次进行固定。

underscore和lodash实现

逻辑差不多，不过增加占位符（placeholder）的概念，用于处理对任意位置的参数进行固化。

实现-增加占位符

function partial(func) {
  var slice = Array.prototype.slice;
  var initArgs = slice.call(arguments, 1);

  return function () {
    var position = 0;
    var args = [];
    for(var i = 0 ; i < initArgs.length; ++i) {
        args[i] = initArgs[i] === partial.placehoder ? arguments[position++] : initArgs[i];
    }
    while(position < arguments.length) {
        args.push(arguments[position++]);
    }        
    return func.apply(this, args);
  }
}

partial.placehoder = "_"

感觉用处不大，尽量使用Object.prototype.bind吧。

7. 时间分片（Time Slicing）/分时函数

什么是时间分片

当一个任务（事件处理函数，回调函数）执行时间过长时，Chrome会有个warn:

[Violation] 'requestIdleCallback' handler took 50ms

1. 根据W3C性能的介绍，超过50ms的任务就是长任务
   

2. 针对超长任务有两种解决方案：

• Web Worker
• 时间切片（Time Slicing）

时间分片

参考了这个文章JavaScript中的时间分片（Time Slicing）：

时间分片的核心思想是：如果任务不能在50毫秒内执行完，那么为了不阻塞主线程，这个任务应该让出主线程的控制权，使浏览器可以处理其他任务。让出控制权意味着停止执行当前任务，让浏览器去执行其他任务，随后再回来继续执行没有执行完的任务

实现

1. 基于时间分割，每隔delay执行一批；
2. 利用生成器函数，yield天生就是让出主线程执行权啊，然后在适当的时候通过生成器对象next方法获取执行权。

注意：
分片的大小要适度，不能太小，EventLoop任务调度也是要花费时间的，分片太小反而影响性能。

let list = document.querySelector('.list')
let total = 100000;
console.time('add')
function* loop() {
    for (let i = 0; i < total; ++i) {
        let item = document.createElement('li')
        item.innerText = `我是${i}`
        list.appendChild(item)                            
        yield                            
    }
    console.timeEnd('add')
}
runTask(loop);

function runTask(genFunc) {
    var gen = genFunc();
    function step() {

        setTimeout(() => {
            var value = gen.next();
            if(value.done) {
                return;
            }
            step();
        })
    }
    step();            
}                  

这个就属于分片太小了（每插入一个标签就setTimeout），估计很久还没插入100000个li标签。利用requestIdleCallback优化：

function runTask(genFunc) {
    var gen = genFunc();
    function step() {
        requestIdleCallback(idleDeadline => {
            do {
                var value = gen.next();
                if(value.done) {
                    return;
                }
            } while(idleDeadline.timeRemaining() > 0)

            step();
        })
    }
    step();            
}

大概8s就搞定了。

参考

1. 这些高阶的函数技术，你掌握了么
2. 【译】理解JavaScript的高阶函数
3. 通过定时器、时间分片、Web Worker优化长任务