2797. Partial Function with Placeholders
Problem Description
The challenge is to create a function called partialFn
which modifies the behavior of an existing function fn
. This modification involves pre-filling certain arguments of the fn
function with values provided in an array called args
, before the partialFn
function is actually called. This concept is known as partial application or currying.
The args
array may contain placeholders, represented by the underscore character "_"
. When partialFn
is later called with additional arguments (restArgs
), these placeholders should be replaced in order with the provided restArgs
. Moreover, if there are more values left in restArgs
after filling all placeholders, these values should be appended to the args
array.
In simple terms, when partialFn
is eventually called, it should call the original fn
function with a new list of arguments. This list starts with any specific values from args
, with placeholders substituted by restArgs
, and ends with any additional restArgs
values appended.
Intuition
The solution to this problem centers around the concept of closures in programming. A closure is a function that captures the scope in which it was defined so that it can access variables from that scope even after the scope execution has finished.
With that in mind, the partial
function does two key things:
- It returns a new function,
partialFn
, that 'remembers' the original functionfn
and the pre-filledargs
array via a closure. - When
partialFn
is called, it replaces each placeholder ("_"
) inargs
with the corresponding element fromrestArgs
. Then, if there are additionalrestArgs
left, it appends them to the end ofargs
.
The intuition behind replacing placeholders and appending additional restArgs
is similar to merging two lists with the twist that some elements in the first list are explicitly marked for replacement.
When all arguments are in place, the final step is to call the original function fn
using the spread operator ...
, which allows us to pass the arguments as separate values even though they are contained in an array.
This implementation provides a flexible way to re-use functions by pre-filling some of their arguments and deciding others at a later point in time.
Solution Approach
The reference solution provided is an implementation of the partial function application using JavaScript (or TypeScript in this case) closures and the spread operator.
Here's a step-by-step breakdown of the implementation:
-
Creating the Closure: The function
partial
takes a functionfn
and an arrayargs
as parameters. It returns a new functionpartialFn
that creates a closure overfn
andargs
. -
Using the Spread Operator: Within the body of
partialFn
, we use the rest parameter syntax (...restArgs
) to collect all additional arguments supplied topartialFn
into an array calledrestArgs
. -
Replacing Placeholders: We then iterate over
args
and replace any placeholders ("_"
) with the corresponding values fromrestArgs
. We use a variablei
to keep track of the current index ofrestArgs
from which we need to take the next value.for (let j = 0; j < args.length; ++j) { if (args[j] === '_') { args[j] = restArgs[i++]; } }
-
Appending Additional Arguments: After all placeholders are replaced, we check if there are still any unused arguments left in
restArgs
. If there are, they are appended to the end ofargs
.while (i < restArgs.length) { args.push(restArgs[i++]); }
-
Invoking the Original Function: Finally, we use the spread operator again to call the original function
fn
with the modifiedargs
array as individual arguments.return fn(...args);
This solution approach is efficient because:
- We have a single pass over the
args
array to replace placeholders. - We have a single pass over the remaining elements of
restArgs
(if any) to append them. - We ensure that we call the original function with precisely the right set of arguments, respecting the order and placeholders' replacement requirements.
This implementation leverages common JavaScript features such as closures to ensure that the partial
function retains access to the original fn
and args
variables when partialFn
is later invoked. The spread operator simplifies argument handling, allowing us to treat the elements of an array as individual parameters to another function.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a simple example. Suppose we have a function multiply
that takes two numbers and returns their product:
function multiply(a, b) {
return a * b;
}
Now, we want to use the partialFn
to create a new function where the first argument of multiply
is pre-filled with 2
. We also want to use _
as a placeholder for the second argument that we will provide later.
Here is how we use partialFn
:
const double = partialFn(multiply, [2, '_']);
In the above code, double
is a new function that, when called with a number, will multiply that number by 2
.
Now let's call double
with an additional argument, 3
:
const result = double(3);
Here's what happens step-by-step:
- We call
double
which is ourpartialFn
with3
asrestArgs
. - Inside
partialFn
, we iterate overargs
([2, '_']
), and when we find a placeholder ('_'
), we replace it with the first element fromrestArgs
(which is3
). - Now
args
becomes[2, 3]
. - There are no additional elements in
restArgs
to append toargs
. - We then call the original
multiply
function with the elements ofargs
spread into separate arguments, effectively callingmultiply(2, 3)
. multiply
returns6
, which is then returned bydouble
.
The result is 6
, which is the product of 2
and 3
. Our partialFn
successfully created a new function that doubled its input. This demonstrates how the partial
function application uses closures and the spread operator to pre-fill and replace function arguments on-demand.
Solution Implementation
1def partial(fn, preset_args):
2 """
3 Creates a partially applied function with the possibility to have placeholders.
4 :param fn: The original function to be partially applied.
5 :param preset_args: List of arguments to apply, where None represents placeholders for additional arguments.
6 :return: A new function with some arguments preset and remaining arguments to be provided later.
7 """
8 def partially_applied(*additional_args):
9 # Create a copy of the preset arguments to avoid modifying the original list.
10 final_args = list(preset_args)
11 add_args_index = 0
12
13 # Iterate over the preset arguments and replace placeholders with additional arguments.
14 for index in range(len(final_args)):
15 if final_args[index] is None:
16 if add_args_index < len(additional_args):
17 final_args[index] = additional_args[add_args_index]
18 add_args_index += 1
19
20 # Append any remaining additional arguments that were not used as placeholders.
21 while add_args_index < len(additional_args):
22 final_args.append(additional_args[add_args_index])
23 add_args_index += 1
24
25 # Call the original function with the combined set of arguments.
26 return fn(*final_args)
27
28 return partially_applied
29
30# Example usage:
31# def add(a, b, c):
32# return a + b + c
33# add_partially = partial(add, [1, None, 3])
34# print(add_partially(2)) # Outputs 6 (1 + 2 + 3)
35
1import java.util.function.Function;
2
3/**
4 * This class provides a way to create a partially applied function with placeholders.
5 */
6public class PartialFunction {
7
8 /**
9 * Creates a partially applied function with the possibility to have placeholders.
10 *
11 * @param fn The original function to be partially applied.
12 * @param presetArgs Array of arguments to apply, where null represents placeholders for additional arguments.
13 * @return A new function with some arguments preset and remaining arguments to be provided later.
14 */
15 public static Function<Object[], Object> partial(Function<Object[], Object> fn, Object[] presetArgs) {
16 return (additionalArgs) -> {
17 Object[] finalArgs = new Object[presetArgs.length];
18 int addArgsIndex = 0;
19
20 // Iterate over the preset arguments and replace placeholders with additional arguments.
21 for (int i = 0; i < presetArgs.length; i++) {
22 if (presetArgs[i] == null) {
23 if (addArgsIndex < additionalArgs.length) {
24 finalArgs[i] = additionalArgs[addArgsIndex++];
25 }
26 } else {
27 finalArgs[i] = presetArgs[i];
28 }
29 }
30
31 // Append any remaining additional arguments that were not used as placeholders.
32 Object[] combinedArgs = new Object[finalArgs.length + additionalArgs.length - addArgsIndex];
33 System.arraycopy(finalArgs, 0, combinedArgs, 0, finalArgs.length);
34 if (addArgsIndex < additionalArgs.length) {
35 System.arraycopy(additionalArgs, addArgsIndex, combinedArgs, finalArgs.length, additionalArgs.length - addArgsIndex);
36 }
37
38 // Call the original function with the combined set of arguments.
39 return fn.apply(combinedArgs);
40 };
41 }
42
43 // Example usage:
44 public static void main(String[] args) {
45 Function<Object[], Object> add = (Object[] params) -> {
46 int sum = 0;
47 for (Object param : params) {
48 sum += (int) param;
49 }
50 return sum;
51 };
52
53 Function<Object[], Object> addPartially = partial(add, new Object[]{1, null, 3});
54 System.out.println(addPartially.apply(new Object[]{2})); // Outputs 6 (1 + 2 + 3)
55 }
56}
57
1#include <functional>
2#include <vector>
3#include <iostream>
4
5/**
6 * Represents a placeholder for future arguments.
7 * This could be replaced with std::optional or a dedicated placeholder type for more complex scenarios.
8 */
9const auto _ = nullptr;
10
11/**
12 * Creates a partially applied function with the possibility to have placeholders.
13 * @param fn The original function to be partially applied.
14 * @param presetArgs Vector of arguments to apply, where nullptr represents placeholders for additional arguments.
15 * @returns A new function with some arguments preset and remaining arguments to be provided later.
16 */
17template<typename ReturnType, typename... Args>
18auto partial(std::function<ReturnType(Args...)> fn, std::vector<std::variant<Args..., std::nullptr_t>> presetArgs)
19{
20 // The returned lambda captures fn and presetArgs by value.
21 return [fn, presetArgs](Args... additionalArgs) mutable -> ReturnType {
22 std::vector<std::variant<Args..., std::nullptr_t>> finalArgs = presetArgs;
23 std::queue<std::variant<Args...>> addArgsQueue({additionalArgs...});
24
25 // Iterates over the preset arguments and replaces placeholders with additional arguments.
26 for (auto& arg : finalArgs) {
27 if (std::holds_alternative<std::nullptr_t>(arg)) {
28 if (!addArgsQueue.empty()) {
29 arg = addArgsQueue.front();
30 addArgsQueue.pop();
31 }
32 }
33 }
34
35 // Appends any remaining additional arguments that were not used as placeholders.
36 while (!addArgsQueue.empty()) {
37 finalArgs.push_back(addArgsQueue.front());
38 addArgsQueue.pop();
39 }
40
41 // Calls the original function with the combined set of arguments using std::apply.
42 return std::apply(fn, finalArgs);
43 };
44}
45
46// Example usage
47int add(int a, int b, int c) {
48 return a + b + c;
49}
50
51int main() {
52 std::function<int(int, int, int)> addFn = add;
53
54 // Create a partially applied function with a placeholder for the second argument
55 auto addPartially = partial(addFn, {1, _, 3});
56
57 // Outputs 6 (1 + 2 + 3)
58 std::cout << addPartially(2) << std::endl;
59
60 return 0;
61}
62
1/**
2 * Creates a partially applied function with the possibility to have placeholders.
3 * @param fn The original function to be partially applied.
4 * @param presetArgs Array of arguments to apply, where '_' represents placeholders for additional arguments.
5 * @returns A new function with some arguments preset and remaining arguments to be provided later.
6 */
7function partial(fn: (...args: any[]) => any, presetArgs: any[]): (...args: any[]) => any {
8 return function(...additionalArgs): any {
9 // Create a copy of the preset arguments to avoid modifying the original array.
10 const finalArgs = [...presetArgs];
11 let addArgsIndex = 0;
12
13 // Iterate over the preset arguments and replace placeholders with additional arguments.
14 for (let index = 0; index < finalArgs.length; ++index) {
15 if (finalArgs[index] === '_') {
16 if(addArgsIndex < additionalArgs.length) {
17 finalArgs[index] = additionalArgs[addArgsIndex++];
18 }
19 }
20 }
21
22 // Append any remaining additional arguments that were not used as placeholders.
23 while (addArgsIndex < additionalArgs.length) {
24 finalArgs.push(additionalArgs[addArgsIndex++]);
25 }
26
27 // Call the original function with the combined set of arguments.
28 return fn(...finalArgs);
29 };
30}
31
32// Example usage:
33// const add = (a, b, c) => a + b + c;
34// const addPartially = partial(add, [1, '_', 3]);
35// console.log(addPartially(2)); // Outputs 6 (1 + 2 + 3)
36
Time and Space Complexity
The given TypeScript code defines a function named partial
, which takes a function fn
and an array args
containing any number of arguments, where some arguments can be placeholders (denoted by '_
'). It returns a new function that, when called, will invoke fn
with a combination of the args
provided during partial application and the arguments passed to the newly created function. Here is an analysis of its computational complexity:
Time Complexity
The time complexity of the partial
function itself, during its creation, is O(n)
where n
is the length of the args
array. This is due to the initial for-loop which iterates over the entire args
array to replace the placeholders with actual values when the returned function is eventually called.
When the returned function is called (...restArgs
), it iterates over the args
array up to a maximum of n
times again (to replace placeholders), and then it iterates over restArgs
which can be denoted as m
, pushing any remaining arguments into the args
array. Thus, the time complexity for the returned function invocation is O(n + m)
, where m
is the number of arguments passed when the returned function is called.
Combining these, invoking the returned function has a time complexity of O(n + m)
.
Space Complexity
The space complexity of the partial
function is also O(n)
. Additional space is required for storing the partially applied arguments (args
). When the returned function is called and args
is updated, no additional space proportional to args
length is required because the changes happen in place.
However, it should be noted that this analysis assumes the fn
function that is eventually called does not allocate additional space, as the space complexity of fn
might have implications on the overall space complexity of the returned function. But with the given code, ignoring fn
's own complexity, the space complexity remains O(n)
.
Which data structure is used to implement priority queue?
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!