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:

  1. It returns a new function, partialFn, that 'remembers' the original function fn and the pre-filled args array via a closure.
  2. When partialFn is called, it replaces each placeholder ("_") in args with the corresponding element from restArgs. Then, if there are additional restArgs left, it appends them to the end of args.

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:

  1. Creating the Closure: The function partial takes a function fn and an array args as parameters. It returns a new function partialFn that creates a closure over fn and args.

  2. Using the Spread Operator: Within the body of partialFn, we use the rest parameter syntax (...restArgs) to collect all additional arguments supplied to partialFn into an array called restArgs.

  3. Replacing Placeholders: We then iterate over args and replace any placeholders ("_") with the corresponding values from restArgs. We use a variable i to keep track of the current index of restArgs from which we need to take the next value.

    1for (let j = 0; j < args.length; ++j) {
    2    if (args[j] === '_') {
    3        args[j] = restArgs[i++];
    4    }
    5}
  4. 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 of args.

    1while (i < restArgs.length) {
    2    args.push(restArgs[i++]);
    3}
  5. Invoking the Original Function: Finally, we use the spread operator again to call the original function fn with the modified args array as individual arguments.

    1return 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Example 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:

1function multiply(a, b) {
2    return a * b;
3}

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:

1const 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:

1const result = double(3);

Here's what happens step-by-step:

  1. We call double which is our partialFn with 3 as restArgs.
  2. Inside partialFn, we iterate over args ([2, '_']), and when we find a placeholder ('_'), we replace it with the first element from restArgs (which is 3).
  3. Now args becomes [2, 3].
  4. There are no additional elements in restArgs to append to args.
  5. We then call the original multiply function with the elements of args spread into separate arguments, effectively calling multiply(2, 3).
  6. multiply returns 6, which is then returned by double.

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).


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄