2629. Function Composition

Problem Description

Given an array of functions such as [f1, f2, f3, ..., fn], the task is to construct a new function fn that represents the function composition of all these functions. Essentially, what this means is that if you have functions f(x), g(x), and h(x), the new function fn(x) would apply these functions in a sequence where the output of one function becomes the input to the next. For example, fn(x) with the given functions would be equivalent to f(g(h(x))). This nesting should work with any number of functions provided in the input array.

A special rule applies when the array is empty: in this case, the expected function to return is an identity function, which is a function that returns its input value f(x) = x. This function does not modify the input value in any way, essentially leaving it unchanged. Every function in the provided array is to be considered as a unary function, meaning it takes a single integer input and produces a single integer output.

Intuition

To construct the composite function fn, we can apply a concept from functional programming called reduceRight. This allows us to start from the last function in the array and iteratively apply the next function to the result of the current one, accumulating the results backward. Essentially, for any starting input x, we pass it through the last function, take that output and pass it through the second-to-last function, and so on until we reach the first function in the array; the final result of this first function is then the result of the composite function fn(x).

The use of reduceRight is essential as it ensures the correct order of function application: from the end of the array to the beginning, mimicking the nesting of functions. As mentioned, if the array is empty, then according to functional programming principles, the accumulation will simply return the initial value x, which is exactly the behavior of an identity function, hence satisfying that special case as well.

This solution elegantly leverages the array's reduceRight JavaScript method to handle the composition logic, which abstracts away the details of iterating through the array and accumulating results for us.

Solution Approach

The implementation for the problem at hand uses the reduceRight method, which is a built-in array method in JavaScript. This method applies a function against an accumulator and each value of the array (from right-to-left) to reduce it to a single value. Here, the "accumulator" is not a numerical value, as it often is with sums or products, but a function.

The main goal is to generate a new function that when called with an argument, it will process this argument through a sequence of the given functions from right-to-left.

Here's the step-by-step algorithm described with relevance to the provided TypeScript code:

1. We define a function compose that takes an array of functions functions: F[] as its parameter. F is a type alias for functions that accept a number and return a number (x: number) => number.

2. compose returns a new function, effectively creating the composition. This returned function uses reduceRight to process an input x: number.

3. The reduceRight method is called on the functions array. It takes two parameters: an accumulator (initially the input x) and a function from the array fn.

4. The callback for reduceRight applies the current function in the array fn to the accumulator acc and returns the result, which becomes the accumulator for the next iteration.

5. This process continues until reduceRight has applied every function in the array to the input, starting from the last function and ending with the first.

6. The result of the reduceRight operation is the return value of the last (or first, depending on perspective) function application, which is the fully composed function being applied to the initial input x.

7. When compose is called with an array of functions, it constructs this new function described above, and when the new function is eventually called with an argument, it executes the composed operations in the correct order.

The key to this solution is understanding the reduceRight function and how it can be leveraged to perform operations in a specific order, which in this case is the function composition from right-to-left (or last-to-first in terms of array indices).

Example Walkthrough

Let's consider a simple example with three functions [f1, f2, f3]. Here, f1(x) = x + 1, f2(x) = x * 2, and f3(x) = x - 3. Our task is to create a new function that composes these three functions, so running fn(x) will perform the operations in sequence as f1(f2(f3(x))).

Here's how we would walk through this using the solution approach:

1. We start by defining our three functions:

   1const f1 = x => x + 1;
   2const f2 = x => x * 2;
   3const f3 = x => x - 3;

2. We then use these functions to create an array of functions:

   1const functions = [f1, f2, f3];

3. Next, we write a compose function that takes this array of functions:

   1function compose(functions){
   2  return (x) => functions.reduceRight((acc, fn) => fn(acc), x);
   3}

4. Now we utilize the compose function to create our composite function fn:

   1const fn = compose(functions);

5. Let's walk through the execution of fn(5):

   • The reduceRight method starts with the last function, f3.
   • For the initial value x, we pass 5: f3(5), which gives us 2.
   • Next, the output of f3, which is 2, is passed to f2: f2(2), which gives us 4.
   • Finally, the output of f2, which is 4, is passed to f1: f1(4), which gives us 5.

6. Therefore, fn(5) processes as f1(f2(f3(5))) = f1(f2(2)) = f1(4) = 5.

In conclusion, by using the compose function, we have successfully created a new function fn that will apply a sequence of operations from our original array of functions. If we were to call fn(x) with any number as the input, it would apply f1, f2, and f3 to that number in the sequence from the last function to the first function.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the compose function is O(n*m), where n is the number of functions in the functions array, and m is the complexity of the individual functions being composed. If we assume that each function in the array has a constant time complexity, then the time complexity would simplify to O(n). This is because the composed function produced by compose calls each function in the array exactly once for each invocation, and it does so in a linear sequence using reduceRight.

For each call of the returned composed function, reduceRight iteratively applies the function calls one by one, starting from the last function to the first function in the array, using the return value of the last function as the input to the previous function. Therefore, the time it takes to execute scales linearly with the number of functions in the array.

Space Complexity

The space complexity of the compose function is O(n) primarily due to functional closure. When compose returns the composed function, it keeps a closure over the functions array. This requires storing a reference to each function in the array, so space used scales linearly with the number of functions.

The actual execution may require additional space, which also depends on the nature of the functions. If none of the functions in the array creates additional space that depends on the size of the input or the number of functions, the overall space complexity of the composed function remains O(n). However, if any individual function has a greater space complexity, this would necessariy increase the space complexity of the composed function.