[JavaScript知识库]函数式编程

1.函数柯里化

1.1 函数柯里化的理解

1. (概念) 函数柯里化指将一个接收多个参数的函数转换成一系列只接收一个参数的函数的技术。
2. 柯里化表现在这几个方面：
   • 函数返回嵌套
   • 函数都接收一个参数

1.2 函数柯里化的实现

// 压缩写法
function curry(func, ...args) {
   if(args.length === func.length)
      return func(...args)
   return function(arg) {
      return curry(func, ...[...args, arg])
   }
}

// 压缩程度更高的反人类写法
let curry = (func, ...args) => args.length === func.length ? func(...args) : arg => curry(func, ...[...args, arg])

设计流程：

1. 模拟过程： 想要实现柯里化，那么就是不断地嵌套函数，这些嵌套的函数不关心函数体，只关心函数参数。我们先模拟一下函数柯里化的过程。

   function add(a, b, c, d) {
      return a + b + c + d
   }
   
   function curry(func) {
      return function(a) {
         return function(b) {
            return function(c) {
               return function(d) {
                  return func(a, b, c, d)
               }
            }
         }
      }
   }
   
   let res = curry(add)
   console.log(res(1)(2)(3)(4))   
   

2. 确定需求： 实现一个curry函数，能够接收1个参数，这个参数是函数，经过curry函数处理后，这个函数可以进行柯里化调用，要求curry作为递归函数。

   function curry(func) {
   
   }
   

3. 设计递归边界——1： 需求中提到curry作为递归函数，在递归调用中要接收参数，就像“模拟过程”中每次接收一个参数一样。所以curry函数不能只接收传入的参数，还应该接收一个参数，就像模拟过程中每次调用只接收一个参数一样，参考模拟过程可以得出递归的中间状态。

   function curry(func, arg) {
       
   }
   

4. 设计递归边界——2： 发现上述设计接收一个参数作为每次递归中间态所接收的参数是没问题的，但是这样不好表示递归边界。递归边界应该是接收到的参数的总数量和func函数参数的总数量相等，所以我们把参数arg修改一下，改成已经接收到的所有参数。

   function curry(func, ...args) {
       if(func.length === args.length)
           func(...args)
   }
   

5. 设计递归中间态： 中间态结合“模拟过程”来看应该是每次都返回一个函数，这个函数只接收一个参数。而且在中间态中必须调用递归函数curry。很容易想到，能不能直接返回curry这样就满足了我们设计的关于中间态的两个条件。返回curry必须是要调用curry，否则无法递归，如果调用curry，我们不清楚到底要给curry传递什么参数，因为在调用阶段实参必须确定。所以直接返回curry不可行，但是要递归就必须要调用curry，关键要让curry执行时接收动态的参数，这时就想到了之前总结“函数闭包机制”时提到的，闭包的特性，利用作用域可以进行运行中动态传值。所以可以在curry外面再包裹一层函数。

   function curry(func, ...args) {
       if(func.length === args.length)
           func(...args)
       return function (arg) {
           return curry(func, ...[...args, arg])
       }
   }
   

1.3 更灵活的函数柯里化

函数柯里化的定义比较严格，要求每一次调用都只能传递一个参数。但是实际应用中可能是这样一种情况，可能是一个函数中某些参数是固定的，我只需要传递几个会改变的参数，举上面“模拟过程”的例子来说，add(a, b, c, d)中假如a和b始终是固定值。这时如果用严格的函数柯里化来表示这种情况应该是"let res = curry(add)(a)(b)"res表示柯里化处理后的函数。虽然可以实现，但是我们可以对上述代码稍作改变来更好贴合这种情况。这实际上就是偏函数

// 压缩写法
function curry(func, ...args) {
   if(args.length === func.length)
      return func(...args)
   // 修改位置
   return function(...arg) {
      return curry(func, ...[...args, ...arg])
   }
}

// 压缩程度更高的反人类写法
let curry = (func, ...args) => args.length === func.length ? func(...args) : (...arg) => curry(func, ...[...args, ...arg])

// 修改后以下调用都是合法的
let res = curry(add)
console.log(res(1)(2)(3)(4))
console.log(res(1, 2)(3, 4))
console.log(res(1, 2, 3)(4))

// 修改前只有以下调用是合法的
console.log(res(1)(2)(3)(4))

修改的是中间态函数，修改效果是每次调用函数时不要求一定只传一个参数。其它要求和柯里化一样，也是将函数分成了一系列函数来调用。这样我们就能随意控制传参数量。如果此时我们认为这种宽松的定义也是属于函数柯里化的话，那么之前总结的“函数绑定”中的bind函数也是采用了函数柯里化相同的思想，bind是将函数分成了两个函数来延迟执行。

1.4 函数柯里化的应用

1. 延迟执行： 通过柯里化函数将一个函数划分成一系列待执行函数，我们就可以通过控制传入函数的参数来控制函数具体的执行时间。例如bind函数就是使用了柯里化思想将函数延迟执行。

2. 参数复用： 上文也提到了这个概念，假如有一个已经经过柯里化的函数，那么我们可以传入这个函数不变的参数来获取一个新的函数。这个新函数的参数一定不是固定不变的，这样就解决了重复参数被屡次使用的问题。

3. 函数体复用： 虽然说函数柯里化只关心参数，并不会影响函数内容。但是可能会有函数嵌套的情景，如果对嵌套函数中的内层函数使用柯里化，那么可能会避免某些代码重复执行。

<!--一个关于IE兼容的例子，为了兼容IE8以下的版本，必须考虑attachEvent-->
<script>
     function addEvent(el, event, callback, capture) {
         if("addEventListener" in window)
             el.addEventListener(event, callback, capture)
         else
             el.attachEvent("on" + event, callback)
     }
</script>

上述代码的弊端在于，不论何时创建事件监听器都要进行判断，看当前浏览器是否支持addEventListenr方法。当然，如果将判断写在外面，写在全局中也是一样每次创建时都要判断。下面采用函数柯里化进行优化。

<script>
     function curry(func, ...args) {
         if(args.length === func.length)
             return func(...args)
         return function(...arg) {
             return curry(func, ...[...args, ...arg])
         }
     }
   
     function addEvent(el, event, callback, capture) {
         if("addEventListener" in window)
             el.addEventListener(event, callback, capture)
         else
             el.attachEvent("on" + event, callback)
     }
   
     let addEvent = curry(addEvent)
     let docEventAdder = addEvent(document)
     let windowEventAdder = addEvent(window)
     
     // 在document上注册事件只会进行一次判断，以后注册的事件都不会经过if语句
     docEventAdder("DOMContentLoaded", () => console.log("DOM加载完成"), false)
     docEventAdder("readyStateChange", () => console.log("readyState发生了变化"), false)
    
     // 在window上注册事件只会进行一次判断，以后注册的事件都不会经过if语句
     windowEventAdder("load", () => console.log("页面渲染已完成"), false)
     windowEventAdder("beforeunload", () => console.log("页面即将刷新"), false)
</script>

上述代码使用柯里化进行了包裹，可以针对某些元素进行柯里化调用，上面举了document和window对象的例子，在它们身上再注册事件监听器就不会再经过if判断语句了。

2.函数绑定

2.1 call实现

Function.prototype.$call = function(context, ...args) {
    // 调用者检查
    if(typeof this !== "function")
        throw new TypeError("必须使用函数调用$call方法")

    // 上下文检查
    context = context || globalThis

    // 给调用者绑定this，并且避免覆盖上下文的属性
    let property = "Danny" + Math.random() * 100
    while(property in context)
        property = "Danny" + Math.random() * 100
    context[property] = this

    // 绑定后执行
    let res = context[property](...args)
    delete context[property]
    return res
}

流程：

1. 检查调用者是否是函数
2. 检查要绑定的上下文是否为空
3. 把调用者作为属性绑定到上下文上
4. 上下文通过该属性调用调用者

注意事项：

1. 给调用者绑定this时，要避免覆盖绑定的上下文的属性，所以这里使用随机数加判断进行避免

2.2 apply实现

Function.prototype.$apply = function(context, arg) {
    // 调用者检查
    if(typeof this !== "function")
        throw new TypeError("必须使用函数调用$apply方法")

    // 上下文检查
    context = context || globalThis

    // 给调用者绑定this
    let property = "Danny" + Math.random() * 100
    while(property in context)
        property = "Danny" + Math.random() * 100
    context[property] = this

    // 绑定后执行
    let res = context[property](arg)
    delete context[property]
    return res
}

流程：

1. 检查调用者是否是函数
2. 检查要绑定的上下文是否为空
3. 把调用者作为属性绑定到上下文上
4. 上下文通过该属性调用调用者

注意事项：

1. 给调用者绑定this时，要避免覆盖绑定的上下文的属性，所以这里使用随机数加判断进行避免

2.3 bind实现

Function.prototype.$bind = function(context, ...args) {
    // 检查调用者
    if(typeof this !== "function")
        throw new TypeError("必须使用函数调用$bind方法")

    // 进行函数绑定，如果有2个参数，使用bind绑定了其中的1个，那么这就是柯里化的情况
    let that = this
    return function() {
        return that.call(context, ...args)
    }
}

流程：

1. 检查调用者是否是函数
2. 用柯里化思想绑定函数并返回

注意事项：

1. bind会把绑定好的函数作为结果返回，不修改原函数

3.尾调用

3.1 尾调用的理解

尾调用是ES6新增的一种内存管理机制。在函数嵌套当中，如果满足如下形式，即内函数的返回值是外函数的返回值，那么JS引擎会做出优化，在执行内函数之前让外函数的上下文提前出栈。

function inner() { // 内函数代码
    return 1
}

function outer() { // 外函数
    return inner() // 内函数，此时内函数的返回值也是外函数的返回值
}

3.2 尾调用的条件

1. (严格模式) 使用严格模式。如果不使用严格模式，在内函数中可以通过outer.call,outer.arguments等属性来引用外函数，会造成外函数不能提前出栈。

2. (返回格式) 外函数的返回值是对内函数的调用。

3. (递归) 递归中外函数返回后不再执行其它逻辑。

4. (闭包) 内函数不会引用外函数中的变量。

注：注意结合<<JavaScript高级程序设计>>给出的例题。目前个人测试和网上查阅资料发现，chrome和firefox，当然还包括node还不支持尾调用优化，但是safari浏览器可以。

3.3 尾调用优化举例

举例—斐波那契数列

// 没有尾调用优化
function fib(n) {
    if(n < 2)
        return n
    return fib(n - 1) + fib(n - 2)
}

// 不使用递归
function f(n) {
    let a = 0, b = 1
    for(let i = 0; i < n; i ++)
        [a, b] = [b, a + b]
    return a
}

"use strict";
// 尾调用优化
function fibStrong(a, b, n) {
    if(n === 0)
        return a
    return fibStrong(b, a + b, n - 1)
}

复杂度分析：
(不使用尾调用优化) 如果使用没有尾调用优化的递归函数，那么空间复杂度会非常大，假如传入了参数n。那么可以想象一下耗费的栈内存，fib(n)是树的根节点，fib(n-1)始终是左子。那么这样的话一直顺着树的左子向下会一直到fib(1)，由此可知这课二叉树的深度是n，则共有(2^n - 1)个节点，相当于空间复杂度是O(2^n)级别。

(使用尾调用优化) 使用尾调用优化的空间复杂度会瞬间减小，假如传入了参数n。在执行到最后return时，发现符合尾调用优化，那么让fibStrong(0, 1, n)直接出栈，然后fibStrong(1, 1, n - 1)入栈，相当于始终只有一个上下文在栈中，相当于空间复杂度降低到了O(1)级别，和不使用递归是一个级别。

举例—求阶乘

// 不使用尾调用优化
function fac(n) {
    if(n === 1)
        return 1
    return n * fac(n - 1)
}

"use strict";
// 使用尾调用优化
function facStrong(res, n) {
    if(n === 1)
        return res
    return facStrong(res * n, n - 1)
}

复杂度分析：
(不使用尾调用优化) 根据斐波那契数列的分析过程可知这个空间复杂度是O(n)。

(使用尾调用优化) 根据斐波那契数列的分析过程可知这个空间复杂度是O(1)。

4.高阶函数

4.1 高阶函数的理解

如果一个函数的参数接收一个或多个函数，最后返回一个新的函数，那么这样的函数就是高阶函数。

4.2 高阶函数举例

举例—函数记忆化

memorize函数是一个记忆化函数，用到了高阶函数和闭包的思想。给memorize传递一个函数，那么它会把这个函数包装成一个记忆化函数。

// 用到了闭包思想和高阶函数思想
function memorize(func) {
    let map = new Map()
    return function(...args) {
        let code = args.join("")
        if(map.has(code)) {
            console.log("当前有记录")
            return map.get(code)
        }
        else {
            let res = func(...args)
            map.set(code, res)
            return res
        }
    }
}

// 递归记忆，递归路径上的值全部记忆
let f = memorize(function fib(n) {
    if(n < 2)
        return n
    return f(n - 1) + f(n - 2)
})

f(10)
// 此时会输出f(5)的值和“当前有记录”，递归记忆不仅仅记住f(10)，还会记住递归路径上的所有值
console.log(f(5))

设计流程：

1. 明确需求： 需要记住递归路径上的所有值。memorize函数包装完后得到一个新函数，只有调用这个新函数，当前值才会被记忆。所以我们的递归函数一定是通过memorize包装的新函数，而不是未包装的函数。
2. 设计递归边界： 递归边界不需要特殊设置，我们在需求中分析只需要关注调用的递归函数是谁。
3. 设计递归中间态： 只需要把之前调用的fib改成包装后的f即可。

5.函数式编程思想总结

注：在这里只是总结了一些思想而已，并没有涉及到实战