2632. 柯里化 🔒

🟠   🔗 力扣 LeetCode

题目

Given a function fn, return a curried version of that function.

A curried function is a function that accepts fewer or an equal number of parameters as the original function and returns either another curried function or the same value the original function would have returned.

In practical terms, if you called the original function like sum(1,2,3), you would call the curried version like csum(1)(2)(3), csum(1)(2,3) , csum(1,2)(3), or csum(1,2,3). All these methods of calling the curried function should return the same value as the original.

Example 1:

Input:

fn = function sum(a, b, c) { return a + b + c; }

inputs = [[1],[2],[3]]

Output: 6

Explanation:

The code being executed is:

const curriedSum = curry(fn);

curriedSum(1)(2)(3) === 6;

curriedSum(1)(2)(3) should return the same value as sum(1, 2, 3).

Example 2:

Input:

fn = function sum(a, b, c) { return a + b + c; }

inputs = [[1,2],[3]]

Output: 6

Explanation:

curriedSum(1, 2)(3) should return the same value as sum(1, 2, 3).

Example 3:

Input:

fn = function sum(a, b, c) { return a + b + c; }

inputs = [[],[],[1,2,3]]

Output: 6

Explanation:

You should be able to pass the parameters in any way, including all at once or none at all.

curriedSum()()(1, 2, 3) should return the same value as sum(1, 2, 3).

Example 4:

Input:

fn = function life() { return 42; }

inputs = [[]]

Output: 42

Explanation:

currying a function that accepts zero parameters should effectively do nothing.

curriedLife() === 42

Constraints:

• 1 <= inputs.length <= 1000
• 0 <= inputs[i][j] <= 10^5
• 0 <= fn.length <= 1000
• inputs.flat().length == fn.length
• function parameters explicitly defined
• If fn.length > 0 then the last array in inputs is not empty
• If fn.length === 0 then inputs.length === 1

题目大意

请你编写一个函数，它接收一个其他的函数，并返回该函数的 柯里化 后的形式。

柯里化 函数的定义是接受与原函数相同数量或更少数量的参数，并返回另一个 柯里化 后的函数或与原函数相同的值。

实际上，当你调用原函数，如 sum(1,2,3) 时，它将调用 柯里化 函数的某个形式，如 csum(1)(2)(3)， csum(1)(2,3)， csum(1,2)(3)，或 csum(1,2,3) 。所有调用 柯里化 函数的方法都应该返回与原始函数相同的值。

提示：

• 1 <= inputs.length <= 1000
• 0 <= inputs[i][j] <= 10^5
• 0 <= fn.length <= 1000
• inputs.flat().length == fn.length
• 函数参数需要被显式定义
• 如果 fn.length > 0 则最后一个数组 inputs 不为空
• 如果 fn.length === 0 则 inputs.length === 1

解题思路

柯里化（Currying）是一种关于函数的高阶技术，它是指将一个函数从可调用的 f(a, b, c) 转换为可调用的 f(a)(b)(c)。柯里化不会调用函数，只是对函数进行转换。

柯里化的目的是什么？

可以从一个实际中的例子中，了解柯里化的好处。

例如，有一个用于格式化和输出信息的日志（logging）函数 log(date, importance, message)：

function log(date, importance, message) {
	alert(`[${date.getHours()}:${date.getMinutes()}] [${importance}] ${message}`);
}

将它柯里化：

log = _.curry(log);

柯里化之后，log 仍正常运行：

log(new Date(), "DEBUG", "some debug"); // log(a, b, c)

但是也能以柯里化形式运行：

log(new Date())("DEBUG")("some debug"); // log(a)(b)(c)

现在，可以轻松地为当前日志创建便捷函数：

// logNow 会是带有固定第一个参数的日志的部分应用函数
let logNow = log(new Date());

// 使用它
logNow('INFO', 'message'); // [HH:mm] INFO message

现在，logNow 是具有固定第一个参数的 log，换句话说，就是更简短的“部分应用函数（partially applied function）”或“部分函数（partial）”。

可以更进一步，为当前的调试日志（debug log）提供便捷函数：

let debugNow = logNow('DEBUG');

debugNow('message'); // [HH:mm] DEBUG message

因此，柯里化让我们能够更容易地获取部分应用函数。就像在日志记录示例中看到的那样，普通函数 log(date, importance, message) 在被柯里化之后，当调用它的时候传入一个参数（如 log(date)）或两个参数（log(date, importance)）时，它会返回部分应用函数。

实现柯里化函数的思路：

1. 函数参数处理：

   • 输入的函数 fn 可能接受多个参数。
   • 使用 fn.length 来获取函数期望的参数数量。

2. 递归调用：

   • 定义一个内部函数 curried，用于处理传入的参数。
   • 检查当前收到的参数数量 args.length 是否达到 fn 所需的参数数量：
     • 如果达到了，则直接调用 fn 并返回结果。
     • 如果未达到，则返回一个新函数，这个新函数接收更多参数（nextArgs）并将之前的参数（args）与新参数合并。

3. 返回合成的函数：

   • 通过递归调用 curried，允许继续接收参数直到满足条件。

复杂度分析

• 时间复杂度：O(1)，每次调用柯里化函数的开销是常数级的，因为只是处理参数和函数调用。
• 空间复杂度：O(n)，在最坏情况下需要存储所有传入的参数，直到达到期望数量的参数。

代码

var curry = function (fn) {
	return function curried(...args) {
		// 如果参数数量满足要求，调用原始函数
		if (args.length >= fn.length) {
			return fn(...args);
		}
		// 否则，返回一个新函数继续接收参数
		return (...nextArgs) => curried(...args, ...nextArgs);
	};
};

相关题目

题号	标题	题解	标签	难度
2623	记忆函数	[✓]
2630	记忆函数 II	[✓]