算法 - 函数柯里化 (Currying)

Posted on

1. 题目

实现一个通用柯里化函数 curry(fn)，把一个「需要 n 个参数」的函数，转换成可以一次传一部分参数、持续返回自身、直到收集够 n 个参数后才真正调用原函数的函数。

示例:

1
2
3
4
5
6
const add = (a, b, c) => a + b + c;
const curried = curry(add);

curried(1)(2)(3);      // 6
curried(1, 2)(3);      // 6
curried(1)(2, 3);      // 6

进阶要求：支持占位符 curry._，允许跳过某参数稍后再填：

1
2
3
const _ = curry._;
curried(_, 2)(1)(3);   // 6
curried(1, _, 3)(2);   // 6

2. 解题思路

柯里化的本质是闭包累积参数。

2.1 基础版（按 arity 触发）

  1. 用 fn.length 得到原函数所需参数个数 n。
  2. 返回一个 acc 函数，每次调用把新参数并入已累积的 args（闭包持有）。
  3. 若 args.length >= n，用 fn.apply(this, args) 真正执行；否则返回一个把新参数继续累积的函数（保持链式）。

判断「够了就执行、没够就返回函数」是核心。为了让 curried(1) 后还能 curried(1)(2)，返回的必须是函数——用 function () { return acc(...args.concat(...arguments)); } 包一层。

2.2 占位符版

在累积参数后，做两步清洗：

  • 记录本次调用是否以「尾部实参」结束，用于决定何时可执行。
  • 只有当「非占位符参数数量 >= n」时才执行；执行前把参数按先前逻辑压缩（去掉多余的前导 _），保证位置对应。

这部分逻辑较绕，面试能写基础版 + 口头讲清占位符思路已足够。

  • 时间复杂度：每次调用 O(已收集参数)。

3. TypeScript 实现

3.1 基础版

1
2
3
4
5
6
7
8
9
10
11
12
13
function curry(fn: Function) {
    return function curried(this: any, ...args: any[]): any {
        if (args.length >= fn.length) {
            return fn.apply(this, args);
        }
        return (...rest: any[]) => curried.apply(this, [...args, ...rest]);
    };
}

const add = (a: number, b: number, c: number) => a + b + c;
const curriedAdd = curry(add);
console.log(curriedAdd(1)(2)(3));   // 6
console.log(curriedAdd(1, 2)(3));   // 6

3.2 支持占位符版

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
const _ = Symbol("placeholder");

function curryWithPlaceholder(fn: Function): any {
    const judge = (...args: any[]): any =>
        // 非占位符参数足够时执行
        args.length >= fn.length &&
        args.slice(0, fn.length).every((a) => a !== _)
            ? fn(...args.filter((a) => a !== _))
            : (arg: any, ...rest: any[]) => judge(...replace(args, arg), ...rest);

    // 用新传入的 arg 填补 args 中第一个占位符；没有则追加
    function replace(args: any[], arg: any): any[] {
        const idx = args.indexOf(_);
        if (idx !== -1 && arg !== _) {
            const copy = [...args];
            copy[idx] = arg;
            return copy;
        }
        return [...args, arg];
    }

    return judge;
}

const sum3 = (a: number, b: number, c: number) => a + b + c;
const c3 = curryWithPlaceholder(sum3);
console.log(c3(_, 2)(1)(3));   // 6
console.log(c3(1, _, 3)(2));   // 6
console.log(c3(1)(2)(3));      // 6

// 暴露占位符
curryWithPlaceholder._ = _;

4. 面试延伸

  • 柯里化 vs 部分应用（partial）：柯里化把「多元函数」拆成「一连串一元函数」；部分应用是一次固定若干参数。JS 里 bind 天然就是部分应用：fn.bind(null, 1)。
  • 实战价值：参数复用、延迟执行、函数组合（compose/pipe 需要一元函数）、创建更专用的小函数（如把通用的 log(date, level, msg) 柯里化成 errorLog = log(now, 'error')）。
  • TS 类型级柯里化是炫技加分项：用递归条件类型 Curry<F> 依据 Parameters<F> 推导出重载签名，展示你对类型体操的掌握。
  • 常见追问：为什么判断用 >= 而非 ===？（箭头函数/默认参数会让 fn.length 变小，容错用 >= 更稳）；fn.length 与 arguments.length 的区别是什么。

难度：中等 | 函数式入门必考 | 闭包与参数复用