2632. Curry
Problem Description
In this problem, you are given a function fn
. The task is to create a curried version of this function. The concept of currying comes from functional programming and involves transforming a function that takes multiple arguments into a sequence of functions, each taking a single argument.
For instance, if you have a function sum
that adds three numbers like sum(1,2,3)
, a curried version csum
should allow you to call csum(1)(2)(3)
, csum(1)(2,3)
, csum(1,2)(3)
, or csum(1,2,3)
. Each of these calls should produce the same result as the original sum
.
The point of currying is that you can hold ('freeze') some parameters while passing the remaining ones later. This process is useful for creating more specific functions from general-purpose ones and can be a powerful technique in many programming scenarios.
Intuition
The intuition behind creating a curried function starts with understanding that we need to return a function that can take any number of arguments and hold them until we have enough arguments to call the original function fn
. Our curried function should return another function if it doesn't have all the necessary arguments, or call the original function with all the available arguments if it does.
To implement this, we:
- Define a function
curry
that accepts a functionfn
, which is the one we want to transform. - The
curry
function returns a new function namedcurried
, utilizing closures to keep track of the arguments given so far. - The
curried
function checks if the number of arguments it has received (args.length
) is at least the number of arguments thatfn
needs (fn.length
). - If we have enough arguments, we call
fn
directly with those arguments. - If we do not yet have all the arguments,
curried
returns a new function that accepts the next set of arguments (nextArgs
). This new function, when called, will concatenate the new arguments to the existing ones and callcurried
again. - This process continues recursively until
curried
receives enough arguments to call the original functionfn
.
This approach allows us to partially apply arguments to the function and call it multiple times with different arguments until all the necessary arguments are provided.
Solution Approach
The implementation of the curry function uses the concepts of closures and recursion in JavaScript, allowing us to progressively accumulate arguments until we are ready to apply them all to the original function. The critical aspects of the solution are as follows:
-
Closure: A closure is a function that remembers the environment in which it was created. In the
curry
implementation, thecurried
function forms a closure overargs
, which allows it to remember the arguments passed to it across multiple calls. -
Recursion: The
curried
function is recursive, as it can return itself with partially applied arguments until it has enough arguments to apply tofn
.
Here's a step-by-step breakdown of the algorithm used in the solution:
-
The
curry
function takes a functionfn
as its argument and returns another functioncurried
. -
The
curried
function can receive multiple arguments each time it is called (...args
in the parameter list is a rest parameter that collects all arguments into an array). It checks if the received arguments are sufficient to call the original function by comparingargs.length
(the length of the accumulated arguments) withfn.length
(the number of parameters expected byfn
). -
If enough arguments are provided (
args.length >= fn.length
),curried
immediately callsfn
with those arguments using the spread syntax...args
, which expands the array contents as separate arguments to the function call. -
If there are not enough arguments yet,
curried
returns a new function. This new function takes additional arguments (...nextArgs
) and again callscurried
, this time with both the previously accumulated arguments and the new ones concatenated together (...args, ...nextArgs
). This is where the recursion happens. -
This process continues until the call to
curried
has enough arguments to call the original functionfn
, at which point the final value is returned.
By using these techniques, the implementation supports creating a curried function that is flexible in its invocation style.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
To illustrate the solution approach for creating a curried function, let's use a straightforward sum
function that adds two numbers:
function sum(a, b) {
return a + b;
}
Now, let's go through the process of using the provided solution approach to create a curried version of this function:
- First, we define the
curry
function that converts any given function into a curried function. Assume that it does all the things mentioned in the solution approach.
function curry(fn) {
// Returns the curried function.
return function curried(...args) {
// If the arguments are sufficient, call the original function.
if (args.length >= fn.length) {
return fn.apply(this, args);
} else {
// If not, return a new function waiting for the rest of the arguments.
return function (...nextArgs) {
// Combine the already given args with the new ones and retry.
return curried.apply(this, args.concat(nextArgs));
};
}
};
}
- We transform the
sum
function into its curried equivalent:
let curriedSum = curry(sum);
- Let's use our new
curriedSum
in different ways, which shows the flexibility of currying:
console.log(curriedSum(1)(2)); // Outputs: 3 - as it's a curried function.
console.log(curriedSum(1, 2)); // Also outputs: 3 - it works even if we pass all arguments in one go.
In the first instance, curriedSum(1)
doesn't have enough arguments to call sum
, so it returns a new function that takes the second argument. Then, when we call this new function with (2)
, we fulfill the number of arguments, and sum
is called with both values.
In the second instance, even though curriedSum
is a curried function, we provide all required arguments at once, so it just applies those to sum
immediately and returns the result.
This example demonstrates the concept of creating a curried function using closures to maintain state across multiple function calls and recursion to continue gathering arguments until the original function can be called with all of them.
Solution Implementation
1# Function that curries another function
2def curry(fn):
3 # The curried function
4 def curried(*args):
5 # If the number of provided arguments is sufficient, call the original function
6 if len(args) >= fn.__code__.co_argcount:
7 return fn(*args)
8 # Otherwise, return a function that awaits the rest of the arguments
9 else:
10 def curried_more(*more_args):
11 return curried(*(args + more_args))
12 return curried_more
13 return curried
14
15# Example of usage:
16# A simple function that adds two numbers
17def sum(a, b):
18 return a + b
19
20# Curry the 'sum' function
21curried_sum = curry(sum)
22
23# Call the curried 'sum' function with one argument at a time
24result = curried_sum(1)(2) # Returns 3
25
26# Now 'result' variable holds the result of calling 'curried_sum'
27print(result) # Output will be 3
28
1import java.util.function.BiFunction;
2import java.util.function.Function;
3
4// Interface for a curried function that can accept one argument
5interface CurriedFunction<T, U> {
6 Function<U, T> apply(T t);
7}
8
9public class CurryExample {
10 // Method that curries another BiFunction
11 public static <T, U, R> CurriedFunction<R, U> curry(BiFunction<T, U, R> biFunction) {
12 // The curried function
13 return (T t) -> (U u) -> biFunction.apply(t, u);
14 }
15
16 // Example of usage:
17 public static void main(String[] args) {
18 // A simple function that adds two numbers
19 BiFunction<Integer, Integer, Integer> sum = (a, b) -> a + b;
20
21 // Curry the 'sum' function
22 CurriedFunction<Integer, Integer> curriedSum = curry(sum);
23
24 // Call the curried 'sum' function with one argument at a time
25 Function<Integer, Integer> addToOne = curriedSum.apply(1);
26 Integer result = addToOne.apply(2); // Returns 3
27
28 // Output the result
29 System.out.println(result); // Prints: 3
30 }
31}
32
1#include <functional>
2#include <iostream>
3
4// Curries another function
5template <typename Function, typename... Args>
6auto curry(Function&& fn, Args&&... args) {
7 // Check if the number of arguments is sufficient to call the function
8 if constexpr (sizeof...(args) >= fn.length) {
9 // If enough arguments are provided, call the original function
10 return std::bind(std::forward<Function>(fn), std::forward<Args>(args)...);
11 } else {
12 // If not enough arguments, return a lambda that takes the rest of the arguments
13 return [=](auto&&... rest) {
14 // Capture current arguments and call `curry` with all of them
15 return curry(fn, args..., std::forward<decltype(rest)>(rest)...);
16 };
17 }
18}
19
20// Example of usage:
21// A simple function that adds two numbers
22int sum(int a, int b) {
23 return a + b;
24}
25
26// Deduction guide for the curry function, to help the compiler deduce the return type
27template <typename Function, typename... Args>
28auto curry(Function&& fn, Args&&... args) -> decltype(auto);
29
30int main() {
31 // Curry the 'sum' function
32 auto curriedSum = curry(sum);
33
34 // Call the curried 'sum' function with one argument at a time
35 auto addOne = curriedSum(1);
36 int result = addOne(2);
37 std::cout << result; // Outputs 3
38
39 return 0;
40}
41
1// Function that curries another function
2function curry(fn: (...args: any[]) => any): (...args: any[]) => any {
3 // The curried function
4 return function curried(...args: any[]): any {
5 // If the number of provided arguments is sufficient, call the original function
6 if (args.length >= fn.length) {
7 return fn(...args);
8 }
9 // Otherwise, return a function that awaits the rest of the arguments
10 return (...nextArgs: any[]) => curried(...args, ...nextArgs);
11 };
12}
13
14// Example of usage:
15// A simple function that adds two numbers
16function sum(a: number, b: number): number {
17 return a + b;
18}
19
20// Curry the 'sum' function
21const curriedSum = curry(sum);
22
23// Call the curried 'sum' function with one argument at a time
24curriedSum(1)(2); // Returns 3
25
Time and Space Complexity
Time Complexity
The time complexity of the curry
function itself is O(1)
, as it's simply returning another function. However, the returned curried
function can be called multiple times, depending on how many arguments it receives each time. When the final curried
function is executed with sufficient arguments, it calls the original function fn
.
Assuming fn
takes n
arguments and has a time complexity of O(f(n))
, where f(n)
is the complexity of function fn
, each partial application of curried
is a constant time operation O(1)
. If a curried function is invoked sequentially for each argument, the overall time complexity for all the calls until fn
is invoked with all n
arguments would be O(n)
. Therefore, provided that the function fn
has a linear number of arguments, and ignoring the complexity of fn
itself, the time complexity of making the series of calls until fn
's execution completes would be O(n)
.
Space Complexity
The space complexity is associated with the closures created for each partial application. Since each call to curried
potentially returns a new closure that holds the given arguments, up to n
closures could be created where n
is the number of arguments fn
requires.
Therefore, if there are n
arguments, the space complexity would be O(n)
due to the n
closures that store the accumulated arguments until all are provided.
A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".
What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!