Problem Description

This problem asks you to implement a curry function that transforms a regular function into a curried version.

What is currying? Currying is a technique where a function that takes multiple arguments is transformed into a sequence of functions, each taking a single argument (or partial arguments).

Requirements:

• Given a function fn, return a curried version of it
• The curried function should accept fewer than or equal to the number of parameters as the original function
• If enough arguments are provided, it should return the final result
• If not enough arguments are provided, it should return another function waiting for the remaining arguments

Example behavior: If you have an original function sum(a, b, c) that takes 3 arguments, after currying it to csum, you can call it in multiple ways:

• csum(1)(2)(3) - one argument at a time
• csum(1)(2, 3) - one argument, then two arguments
• csum(1, 2)(3) - two arguments, then one argument
• csum(1, 2, 3) - all three arguments at once

All these different calling patterns should produce the same result as calling the original sum(1, 2, 3).

How the solution works:

1. The curry function returns a new function called curried that collects arguments
2. When curried is called with some arguments, it checks if the total number of arguments collected so far is enough (>= the original function's parameter count via fn.length)
3. If enough arguments are provided, it calls the original function with all the arguments and returns the result
4. If not enough arguments are provided, it returns another function that will accept more arguments and combine them with the previously collected ones using the spread operator ...args, ...nextArgs

Intuition

The key insight is that we need to accumulate arguments across multiple function calls until we have enough to execute the original function.

Think of it like filling a bucket - each time the curried function is called, we add more water (arguments) to the bucket. Once the bucket is full (we have all required arguments), we can pour it out (execute the original function).

To achieve this behavior, we need:

1. A way to remember previously passed arguments - This naturally suggests using closures, where inner functions can access variables from outer scopes
2. A way to check if we have enough arguments - JavaScript functions have a length property that tells us how many parameters they expect
3. A recursive structure - If we don't have enough arguments yet, we need to return another function that continues the same pattern

The elegant solution uses the spread operator (...args) to collect arguments and a recursive approach where curried calls itself. When curried is first called with some arguments, those arguments are captured in its scope. If we need more arguments, we return a new arrow function that:

• Accepts additional arguments (...nextArgs)
• Combines them with the previously collected ones (...args, ...nextArgs)
• Recursively calls curried with the combined arguments

This creates a chain of functions, each holding onto its piece of the argument list, until we finally have enough to call the original function. The beauty of this approach is that it handles any combination of partial applications - whether you pass arguments one at a time or in groups, the recursive structure naturally accumulates them until the requirement is met.

Solution Approach

Let's walk through the implementation step by step:

1. Creating the curry wrapper function:

function curry(fn: Function): Function {
    // Returns a new function that will handle the currying logic
}

2. Implementing the curried function with argument collection:

return function curried(...args) {
    // ...args collects all arguments passed in the current call
}

The curried function uses the rest parameter syntax ...args to collect any number of arguments passed to it. This allows flexible partial application.

3. Checking if we have enough arguments:

if (args.length >= fn.length) {
    return fn(...args);
}

• fn.length gives us the number of parameters the original function expects
• If the current argument count meets or exceeds this requirement, we execute the original function with all collected arguments using the spread operator ...args
• This handles both the case where all arguments are provided at once and when we've accumulated enough through multiple calls

4. Handling partial application:

return (...nextArgs) => curried(...args, ...nextArgs);

When we don't have enough arguments yet:

• We return a new arrow function that accepts additional arguments ...nextArgs
• This arrow function calls curried recursively with the combined arguments from both the current call (args) and the new call (nextArgs)
• The spread operators merge the argument arrays: ...args, ...nextArgs creates a new array containing all arguments collected so far

Key patterns used:

• Closure: The returned arrow function captures args from its parent scope, preserving the arguments between calls
• Recursion: curried calls itself with accumulated arguments, creating a chain of function calls
• Rest/Spread operators: Used for flexible argument handling and array concatenation

Example execution flow for csum(1)(2)(3) where sum takes 3 parameters:

1. csum(1): args = [1], length < 3, returns a function
2. (2): Previous args = [1], new nextArgs = [2], calls curried(1, 2), still < 3, returns another function
3. (3): Previous args = [1, 2], new nextArgs = [3], calls curried(1, 2, 3), length = 3, executes fn(1, 2, 3) and returns the result

Example Walkthrough

Let's walk through a concrete example to understand how the curry function works. We'll use a simple multiply function that takes 3 arguments:

function multiply(a, b, c) {
    return a * b * c;
}

const curriedMultiply = curry(multiply);

Now let's trace through the execution of curriedMultiply(2)(3)(4):

Step 1: First call - curriedMultiply(2)

• The curried function is called with args = [2]
• Check: args.length (1) >= fn.length (3)? No, we need more arguments
• Returns: (...nextArgs) => curried(...[2], ...nextArgs)
• This returned function remembers [2] in its closure

Step 2: Second call - (3) on the returned function

• The arrow function from Step 1 is called with nextArgs = [3]
• It executes: curried(...[2], ...[3]) which becomes curried(2, 3)
• Now curried is called with args = [2, 3]
• Check: args.length (2) >= fn.length (3)? No, still need one more
• Returns: (...nextArgs) => curried(...[2, 3], ...nextArgs)
• This new function remembers [2, 3] in its closure

Step 3: Third call - (4) on the returned function

• The arrow function from Step 2 is called with nextArgs = [4]
• It executes: curried(...[2, 3], ...[4]) which becomes curried(2, 3, 4)
• Now curried is called with args = [2, 3, 4]
• Check: args.length (3) >= fn.length (3)? Yes! We have enough arguments
• Executes: multiply(2, 3, 4) and returns 24

Alternative calling pattern - curriedMultiply(2, 3)(4):

Step 1: curriedMultiply(2, 3)

• curried is called with args = [2, 3]
• Check: args.length (2) >= fn.length (3)? No
• Returns: (...nextArgs) => curried(...[2, 3], ...nextArgs)

Step 2: (4) on the returned function

• The arrow function is called with nextArgs = [4]
• Executes: curried(2, 3, 4)
• Check: args.length (3) >= fn.length (3)? Yes!
• Returns: multiply(2, 3, 4) = 24

The beauty of this solution is that the same recursive pattern handles any combination of partial applications, accumulating arguments until the function can be executed.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of currying calls needed before the function executes.

• Each call to the curried function involves:
  • Checking args.length >= fn.length: O(1)
  • Spreading and combining arguments: O(k) where k is the number of accumulated arguments
  • Since arguments accumulate across calls, in the worst case with n calls, the total time is O(1) + O(2) + ... + O(n) = O(n²/2) = O(n²) for spreading operations across all calls
• However, in practical usage where each call typically adds a fixed small number of arguments, the amortized time complexity is O(n)

Space Complexity: O(n * m) where n is the number of partial application calls and m is the average number of arguments per call.

• Each returned function closure maintains:
  • A reference to the accumulated arguments array: O(k) where k is the number of accumulated arguments so far
  • The closure scope with references to the outer function
• In the call stack during nested calls: O(n) for the depth of recursive closures
• Total space used for storing all accumulated arguments across the chain: O(n * m)
• The space is released once the final function executes and returns

Common Pitfalls

1. Functions with Default Parameters or Variable Arguments

The Problem: The curry implementation relies on fn.length (JavaScript) or fn.__code__.co_argcount (Python) to determine when enough arguments have been collected. However, these properties don't account for:

• Functions with default parameters (they're not counted in the length)
• Functions using rest parameters (...args in JS or *args in Python)
• Functions with keyword-only arguments in Python

Example of the issue:

// JavaScript
function greet(name, greeting = "Hello") {
    return `${greeting}, ${name}!`;
}
console.log(greet.length); // Returns 1, not 2!

const curriedGreet = curry(greet);
curriedGreet("Alice"); // Executes immediately with undefined greeting
curriedGreet("Alice")("Hi"); // Never executes, returns a function instead

# Python
def greet(name, greeting="Hello"):
    return f"{greeting}, {name}!"

# greet.__code__.co_argcount returns 2, but only 1 is required
curriedGreet = curry(greet)
curriedGreet("Alice")  # Waits for second argument unnecessarily

Solution: For functions with default parameters, you can:

1. Create a wrapper that explicitly specifies the expected argument count:

function curry(fn, arity = fn.length) {
    return function curried(...args) {
        if (args.length >= arity) {
            return fn(...args);
        }
        return (...nextArgs) => curried(...args, ...nextArgs);
    };
}

// Usage with explicit arity
const curriedGreet = curry(greet, 1); // Specify it needs minimum 1 argument

2. Or handle optional parameters separately by checking if the function can be executed:

function curry(fn) {
    return function curried(...args) {
        // Try to execute if we have at least the minimum required arguments
        if (args.length >= fn.length) {
            return fn(...args);
        }
      
        // For safety, you could also add a maximum argument check
        if (args.length > fn.length + 5) { // arbitrary buffer for optional params
            return fn(...args);
        }
      
        return (...nextArgs) => curried(...args, ...nextArgs);
    };
}

2. Methods and Context (this binding) Loss

The Problem: When currying object methods, the this context gets lost because the curried function creates new function scopes.

Example of the issue:

const calculator = {
    base: 10,
    add: function(a, b) {
        return this.base + a + b;
    }
};

const curriedAdd = curry(calculator.add);
curriedAdd(5)(3); // Error or unexpected result - 'this' is undefined or global

Solution: Preserve the context by binding it or accepting it as a parameter:

function curry(fn, context = null) {
    return function curried(...args) {
        if (args.length >= fn.length) {
            // Apply with preserved context
            return context ? fn.apply(context, args) : fn(...args);
        }
        return (...nextArgs) => curried(...args, ...nextArgs);
    };
}

// Usage
const curriedAdd = curry(calculator.add, calculator);
// Or use bind before currying
const curriedAdd = curry(calculator.add.bind(calculator));

3. Functions with No Parameters

The Problem: Functions that take zero parameters will immediately execute when curried, which might not be the expected behavior.

Example of the issue:

function getCurrentTime() {
    return new Date().toISOString();
}

const curriedTime = curry(getCurrentTime);
// This executes immediately and returns the time, not a function
const result = curriedTime(); // 'result' is a timestamp, not callable

Solution: Handle zero-parameter functions as a special case:

function curry(fn) {
    // Special case for zero-parameter functions
    if (fn.length === 0) {
        return fn; // Return the function as-is, or wrap it differently
    }
  
    return function curried(...args) {
        if (args.length >= fn.length) {
            return fn(...args);
        }
        return (...nextArgs) => curried(...args, ...nextArgs);
    };
}

These pitfalls highlight the importance of understanding the specific requirements and edge cases of the functions you're currying, and potentially creating more sophisticated curry implementations for production use.