LeetCode 2632 - Curry

LeetCode Problem 2632

Difficulty: 🟡 Medium
Topics: —

Solution

Problem Understanding

The problem is asking us to implement currying for a given function. Currying is a functional programming technique where a function with multiple parameters is transformed into a sequence of functions, each accepting a subset of the original parameters. Essentially, instead of calling a function with all its arguments at once, you can call it multiple times with fewer arguments, and once all arguments are provided, it returns the final result.

The input to this problem is a function fn with a fixed number of parameters, which can be obtained using fn.length. The expected output is a curried version of fn that can be called with any combination of arguments until all required arguments are supplied. Once the arguments are complete, the curried function returns the same result as the original function. For example, a function sum(a, b, c) can be called as curriedSum(1)(2)(3) or curriedSum(1, 2)(3) or even curriedSum()(1, 2, 3).

The constraints tell us that the number of inputs is reasonable (1 <= inputs.length <= 1000), the number of function parameters is manageable (0 <= fn.length <= 1000), and all parameters are integers (0 <= inputs[i][j] <= 10^5). We are guaranteed that the total number of arguments in inputs matches the arity of fn, which simplifies validation. Edge cases include zero-parameter functions, which should return the result immediately, and functions called with empty arrays, which should still accumulate arguments until the function is ready to execute.

Key observations: the function may be called multiple times with varying numbers of arguments. A naive implementation that does not accumulate arguments will fail for calls like curriedSum(1)(2, 3). Another potential pitfall is calling the function with empty arguments multiple times, which should not disrupt argument accumulation.

Approaches

The brute-force approach would attempt to handle each specific calling pattern explicitly by checking the number of arguments received each time and manually deciding whether to return a result or a nested function. This approach is cumbersome and error-prone because it requires accounting for every combination of argument splits, making the code complex and difficult to maintain.

The optimal approach leverages closure and argument accumulation. We define a recursive function that collects arguments every time it is called. If the total collected arguments are fewer than the original function's arity, the function returns a new function that accepts more arguments. If the collected arguments match the arity, the original function is executed with all collected arguments. This approach is elegant because it naturally handles any combination of argument calls, including empty calls.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Would attempt to enumerate all splits of arguments; inefficient for large n
Optimal	O(1) per call	O(n)	Uses closures to accumulate arguments; executes fn only once when all arguments are collected

Algorithm Walkthrough

1. Start by defining a function curry that accepts the original function fn.
2. Inside curry, define a helper function curried that maintains a list of args accumulated so far.
3. Each time curried is called, append the new arguments to the existing list of arguments.
4. Check if the total number of accumulated arguments is less than the arity of fn (i.e., fn.length). If it is, return a new function that will continue accumulating arguments.
5. If the number of accumulated arguments is equal to or exceeds the arity of fn, call fn with all collected arguments and return the result.
6. Return the initial curried function from curry.

Why it works: The invariant is that curried always keeps track of all arguments supplied so far. Since JavaScript and Python functions can be called with any number of arguments, we can accumulate them incrementally. Once the total arguments match the original function's expected count, we know it is safe to execute the function. This guarantees correct results for any valid sequence of function calls.

Python Solution

from typing import Callable, Any

def curry(fn: Callable) -> Callable:
    def curried(*args_so_far):
        if len(args_so_far) >= fn.__code__.co_argcount:
            return fn(*args_so_far)
        return lambda *next_args: curried(*args_so_far, *next_args)
    return curried

The curry function defines an inner function curried that takes a variable number of arguments. It checks if the total number of accumulated arguments is at least equal to the original function's arity. If so, it executes the original function. Otherwise, it returns a new lambda function that continues to accumulate arguments. The use of *args allows the curried function to accept any number of arguments at each call, including zero.

Go Solution

package main

import "reflect"

func Curry(fn interface{}) interface{} {
    fnValue := reflect.ValueOf(fn)
    fnType := fnValue.Type()
    arity := fnType.NumIn()

    var curried func([]reflect.Value) reflect.Value
    curried = func(argsSoFar []reflect.Value) reflect.Value {
        if len(argsSoFar) >= arity {
            result := fnValue.Call(argsSoFar)
            return result[0]
        }
        return reflect.MakeFunc(reflect.FuncOf(fnType.In(len(argsSoFar):), fnType.Out(), fnType.IsVariadic()), func(newArgs []reflect.Value) []reflect.Value {
            return []reflect.Value{curried(append(argsSoFar, newArgs...))}
        })
    }

    return curried([]reflect.Value{})
}

In Go, we use the reflect package to handle functions generically, since Go is statically typed and does not natively support variadic currying. The curried function accumulates arguments in a slice of reflect.Value. When the required number of arguments is collected, it calls the original function using Call. Otherwise, it returns a new function using reflect.MakeFunc that continues accumulating arguments.

Worked Examples

Example 1: sum(a, b, c)

Call	Accumulated Args	Result
curriedSum(1)	[1]	returns function
(2)	[1, 2]	returns function
(3)	[1, 2, 3]	returns 6

Example 2: curriedSum(1, 2)(3)

Call	Accumulated Args	Result
curriedSum(1, 2)	[1, 2]	returns function
(3)	[1, 2, 3]	returns 6

Example 3: curriedSum()()(1, 2, 3)

Call	Accumulated Args	Result
curriedSum()	[]	returns function
()	[]	returns function
(1, 2, 3)	[1, 2, 3]	returns 6

Example 4: life()

Call	Accumulated Args	Result
curriedLife()	[]	returns 42

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) per call	Each curried call only appends arguments and may return a lambda; execution of fn occurs once
Space	O(n)	Accumulates arguments in a closure until execution; requires space proportional to function arity

The complexity is efficient because argument accumulation is lightweight, and the function executes only once. The recursion depth corresponds to the number of times the curried function is called, but this is bounded by fn.length.

Test Cases

def test_curry():
    def sum3(a, b, c):
        return a + b + c
    csum = curry(sum3)
    assert csum(1)(2)(3) == 6  # sequential calls
    assert csum(1, 2)(3) == 6  # partial arguments
    assert csum()(1, 2, 3) == 6  # empty calls
    def life():
        return 42
    clife = curry(life)
    assert clife() == 42  # zero-parameter function
    def add4(a, b, c, d):
        return a + b + c + d
    cadd4 = curry(add4)
    assert cadd4(1, 2)(3, 4) == 10
    assert cadd4()(1)(2)(3)(4) == 10
    assert cadd4(1)(2, 3, 4) == 10
test_curry()

Test	Why
csum(1)(2)(3)	Checks sequential currying with one argument at a time
csum(1, 2)(3)	Checks partial arguments at each step
csum()(1, 2, 3)	Checks empty calls before providing arguments
clife()	Checks zero-parameter function handling
cadd4(1, 2)(3, 4)	Checks multiple arguments at different steps