不过多介绍柯里化的定义和应用场景,直接看实现。


柯里化实现

如果我们有以下加法函数:

1
const add = (a, b) => a + b

要怎么实现柯里化呢?


手工柯里化

我们可以选择直接手写柯里化的 add:

1
2
3
4
5
6
7
// 手工柯里化 
const curryingAdd = a => b => a + b

// 使用
const inc = curryingAdd(1)
inc(1) // 2

通过闭包的嵌套,我们可以实现每次只接受一个参数的手工柯里化的函数。

但是这种方式,对于每个需要柯里化的函数,都需要侵入其实现,非常麻烦。因此并没有什么实用价值。我们需要能一种通用的方案来自动化做这个事情。


自动柯里化

柯里化的实现,核心在于根据参数数量选择返回接受剩余参数的新函数,或者返回最终结果。

在 JavaScript 中,具备实现这一切的条件,我们可以通过函数的 length 得知形参的数量,通过 arguments 对象得知实参的信息,通过闭包返回新函数也不在话下。下面开始尝试实现,先从简单的两个参数的情况开始:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// 单一参数函数的柯里化
const curry1 = (fn) => {
  // 生成一个柯里化的版本
  return function currying(a) {
    // 检查实参数量
    // 此处不能简单地用 undefined 判断,
    // 因为 fn 本身可能也能接受并处理 undefined
    switch (arguments.length) {
      // 没有传入任何参数,返回柯里化后的函数本身
      case 0: return currying

      // 传入了任意大于 0 个数量的参数,则调用应用它们
      default: return fn.apply(void 0, arguments)
    }
  }
}

// 两个参数的函数柯里化
const curry2 = (fn) => {
  // 生成一个柯里化的版本
  return function currying(a,b) {
    // 同 curry1,检查实参数量
    switch (arguments.length) {
      // 没有传入任何参数,返回柯里化后的函数本身
      case 0: return currying
 
      // 传入了 1 个参数,则记录下该参数,
      // 创建一个接受剩余参数的新函数并柯里化
      // 相当于简化了函数的参数规模
      case 1: {
        const arg = arguments[0]
        
        // 自动柯里化接受剩余参数的函数
        // 剩余参数只有 1 个,因此使用 curry1
        return curry1(function() {
          // 合并外层函数已经部分应用的参数          
          const args = [arg]
          args.push.apply(args, arguments)

          return fn.apply(void 0, args)
        })
      }

      // 传入了足够的参数时,直接应用这些参数
      default: return fn.apply(void 0, arguments)
    }
  }
}

// 使用
const add = (a, b) => a + b
const curryingAdd = curry2(add)
curryingAdd(1, 1) // 2
curryingAdd(1)(1) // 2
curryingAdd()(1)()(1) // 2
// ...

以上代码实现了通用的 2 个参数的函数的柯里化。

但如果参数的数量有很多呢,我们不可能也没必要去创建 curry3curry4curryN 等等一大批函数。完全可以定义一个通用的 curryN,指定 N ,返回自动柯里化的函数,例如下面就是一个实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 缓存 slice
const slice = Array.prototype.slice

const curryN = (arity, fn) => {
  // 返回柯里化的版本
  return function currying() {
    // 本次调用的实参个数
    const consumedCount = arguments.length

    // 传入 0 个参数,返回柯里化后的函数本身
    if (consumedCount === 0) return currying

    // 算出剩余参数数量
    const rest = arity - consumedCount
  
    // 如果剩余参数不大于零,意味着提供的实参已经足够了,
    // 可以正式计算并返回结果了
    if (rest <= 0) {
      return fn.apply(void 0, arguments)
    }
    
    // 如果提供的实参,只是部分应用,则记录下它们
    // 后续用于合并参数
    const consumedArgs = slice.call(arguments)

    // 检查剩余参数数量,进行不同的递归处理
    switch (rest) {
      // 快速路径,如果只有一个参数,curry1 处理剩余参数
      case 1:
        return curry1(function(a) {
          // 合并外层函数的实参
          consumedArgs.push.apply(consumedArgs, arguments)
          return fn.apply(void 0, consumedArgs)
        })

      // 快速路径,同上
      case 2:
        return curry2(function(a, b) {
          consumedArgs.push.apply(consumedArgs, arguments)
          return fn.apply(void 0, consumedArgs)
        })
        
      // 剩余参数更多,则递归 curryN 处理剩余参数
      default: {
        return curryN(rest, function() {
          consumedArgs.push.apply(consumedArgs, arguments)
          return fn.apply(void 0, consumedArgs)
        })
      }
    }
  }
}

// 使用:

const add = (a, b) => a + b
curryN(2, add)(1, 1) // 2
curryN(2, add)(1)(1) // 2

以上就是通用 curryN 的实现代码,只要传入了正确的元数,就可以柯里化任何参数数量的函数了。

有了上面的实现代码后,我们就可以提供一个简单的 curry 函数作为对外的 API 了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const curry = (fn, arity) => {
  // 如果没有指定元数,
  // 则通过 length 属性获取
  arity = arity || fn.length

  switch (arity) {
    case 0: return fn
    case 1: return curry1(fn)
    case 2: return curry2(fn)
    default: return curryN(arity, fn)
  }
}

// 使用

const add = (a, b) => a + b
curry(add)(1)(1) // 2

curry 可以处理所有参数都用形参定义了的函数。而默认参数、不定义形参直接处理 arguments 等情况的函数,则无法正确处理,只能使用传入第二个参数来手工提供元数。例如:

1
2
3
4
5
6
7
8
const add = (a, b = 10) => a + b
add.length // 1

curry(add)(1) // 11
curry(add)(1)(1) // TypeError

// 传入第二个参数指定元数
curry(add, 2)(1)(1) // 2

元数信息丢失

以上实现的 curry1curry2curryN 函数,都存在一个问题,就是生成出来的柯里化后的函数,都会丢失掉元数的信息:

1
2
3
4
5
const add = (a, b) => a + b

add.length // 2

curry(add).length // 0

这在一些需要判断参数数量的场景会导致 bug,因此,有必要对该问题进行修复。

而修复的一个可行的方法为,柯里化时候,根据元数,返回一个对应形参数量的函数,以下按照该思路进行改写:

1
2
3
4
5
6
7
8
9
10
const curry1 = (fn) => {
  // 注意此处,我们为函数提供了一个 `a` 作为形参,
  // 用于 “撑开” 函数的元数
  return function currying(a) {
    switch (arguments.length) {
      case 0: return currying
      default: return fn.apply(void 0, arguments)
    }
  }
}

同理,我们可以改写 curry2 ,使用两个形参 “撑开” 函数。但是,对于 curryN,因为元数本身是不确定数量的,我们就没办法这么处理了。 这时候,我们可以设计一个辅助函数 _arity(n, fn),专门用于生成指定数量形参的函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
function _arity(n, fn) {
  // 对于数量比较少的情况,直接暴力枚举处理
  switch (n) {
    case 1: return function(a) {
      return fn.apply(void 0, arguments)
    }
    case 2: return function(a, b) {
      return fn.apply(void 0, arguments)
    } 
    case 3: return function(a,b,c) {
      return fn.apply(void 0, arguments)
    }
    case 4: return function(a,b,c,d) {
      return fn.apply(void 0, arguments)
    } 
    case 5: return function(a,b,c,d,e) {
      return fn.apply(void 0, arguments)
    } 
    case 6: return function(a,b,c,d,e,f) {
      return fn.apply(void 0, arguments)
    }
    case 7: return function(a,b,c,d,e,f,g) {
      return fn.apply(void 0, arguments)
    }
    case 8: return function(a,b,c,d,e,f,g,h) {
      return fn.apply(void 0, arguments)
    }
    case 9: return function(a,b,c,d,e,f,g,h,i) {
      return fn.apply(void 0, arguments)
    } 
    case 10: return function(a,b,c,d,e,f,g,h,i,j) {
      return fn.apply(void 0, arguments)
    }
    // 元数很多时,使用另一种方法
    default: return arityMany(n, fn)
  }
}

我们首先假设,正常的使用过程中,形参应该不会大于 10 个,各种情况,逐个简单粗暴返回一个包裹函数即可。

而对于超过 10 个形参的情况,我们无法也没必要一一枚举了,直接调用另一个辅助函数,aritiMany,实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
function arityMany(n, fn) {
  let params = []
  params.push('fn')
  let ret = `return function(`
  let index = -1
  while (++index < n) {
    ret += index === 0 ? `_${index}` : `,_${index}`
  }
  ret += `){return fn.apply(void 0,arguments)}`
  params.push(ret)
  const newFn = new Function(...params)
  return newFn(fn)
}

利用了 new Function 的方式,动态生成一个指定元数的包裹函数。

有了以上辅助函数后,我们就可以改写 curryN 的实现了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const curryN = (arity, fn) => {
  function currying() {
    // ...实现代码同上文
  }
 
  // 注意此处,
  // 使用 wrapper 包裹,以确保 length 正确
  const wrapper = _arity(arity, currying)
  // 返回包裹后的函数
  return wrapper
}

// 检查
const add = (a, b) => a + b
add.length // 2
curry(add).length // 2

至此,元数问题解决。

TS 类型

自动柯里化的 TS 类型写法比较绕,核心有以下部分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
type Cast<X, Y> = X extends Y ? X : Y
type Length<T extends any[]> = T['length']
type Drop<N extends number, T extends any[], I extends any[] = []> = {
  0: Drop<N, Tail<T>, Prepend<any, I>>
  1: T
}[Length<I> extends N ? 1  : 0]

type Arity1<A, R> = (a: A, ...rest: any[]) => R
type Arity2<A, B, R> = (a: A, b: B, ...rest: any[]) => R
type ArityN<P extends any[], R> = (...args:P)=>R

interface Curry1<A, R> {
  (): Curry1<A, R>
  (a: A, ...rest: any[]): R
}

interface Curry2<A, B, R> {
  (): Curry2<A, B, R>
  (a: A, ...rest: any[]): Curry1<B, R>
  (a: A, b: B, ...rest: any[]): R
}

type Currying<P extends any[], R> = <T extends any[]>(...args: Cast<T, Partial<P>>) =>
  // 没有剩余参数可消耗,则返回最终结果
  Drop<Length<T>, P> extends [] ? R
  // 剩余 1
  : Drop<Length<T>, P> extends [infer A] ? Curry1<A, R>
  // 剩余 2
  : Drop<Length<T>, P> extends [infer A, infer B] ? Curry2<A, B, R>
  // 剩余更多,走 curryN
  : Drop<Length<T>, P> extends [any, ...any[]] ? Currying<Drop<Length<T>, P> extends infer REST ? Cast<REST, any[]> : never, R> : never

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function curry1<A, R>(fn: Arity1<A, R>) {
  // 重载
  function curried(): Curry1<A, R>
  function curried(a: A): R
  function curried(a: A, ...rest: any): R
  // 实现
  return function curried(a?) {/**/}
}

function curry2<A, B, R>(fn: Arity2<A, B, R>) {
  // 重载
  function curried(): Curry2<A, B, R>
  function curried(a: A): Curry1<B, R>
  function curried(a: A, b: B): R
  function curried(a: A, b: B, ...rest: any): R
  // 实现
  return function curried(a?, b?) {/**/}
}

function curryN<P extends any[], R>(
  arity: number,
  fn: (...args: P) => R
): Currying<P, R> | ArityType<P, R> {
  // 实现...
}

function curry<P extends any[], R>(fn: (() => R)): typeof fn
function curry<A, R>(fn: ((a: A) => R)): Curry1<A, R>
function curry<A, B, R>(fn: ((a: A, b: B) => R)): Curry2<A, B, R>
function curry<P extends any[], R>(fn: ((...args: P) => R)): Currying<P, R>
// 传入了 arity,则需要手动传入 P,不能使用 fn 的类型来推断,因为参数长度和手工指定的 arity 不一定一致
function curry<P extends any[], R>(fn: ((...args) => R), arity: number): Currying<P, R>
// 可以传入 arity 指定元数,
// 以支持默认值参数 & rest 参数(目前这么做会失去 TS 类型信息)
// 另外,指定元数后,参数默认值不会被使用
function curry(fn, arity?: number) {/**/}

完整和性能优化的 typescript 实现,等我不那么懒了,再发布到 github 上。

性能优化

由于柯里化过程中,需要创建大量的闭包,还有大量的操作 arguments 对象,因此性能会有比较大幅度的下降。有些实现中,还支持使用占位符,性能更是感人。所以作为一个基础工具函数,适当的压榨性能,还是存在意义的。

比较简单的优化方向可以有:

  1. 枚举处理常见的参数长度,而不是简单粗暴地 apply arguments
  2. 参数拼接方法的选择,例如 pushconcat,ES6 的 ... 运算符等等
  3. 根据需要处理的函数参数数量,提供 curry1, curry2, curry3 等快捷方式

不过许多优化都针对引擎的实现,会随着引擎的发展变化,所以是否优化也需要权衡取舍。


全文完