2629. Function Composition

Easy

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:

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.
compose returns a new function, effectively creating the composition. This returned function uses reduceRight to process an input x: number.
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.
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.
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.
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.
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).

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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:

We start by defining our three functions:

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

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

const functions = [f1, f2, f3];

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

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

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

const fn = compose(functions);

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

1from typing import List, Callable
2
3# Define a type alias 'FunctionType' for functions that take a number and return a number
4FunctionType = Callable[[float], float]
5
6def compose(functions: List[FunctionType]) -> FunctionType:
7    """
8    Composes an array of functions into a single function.
9    The functions are composed from right to left.
10
11    :param functions: A list of functions to be composed.
12    :return: A new function that is the result of composing the input functions.
13    """
14    # Define and return a new function that takes a single argument 'x'
15    def composed_function(x: float) -> float:
16        # Use 'reduce' to apply each function in the list from right to left
17        # to the accumulator 'acc', starting with the initial value 'x'
18        return reduce(lambda acc, fn: fn(acc), reversed(functions), x)
19    return composed_function
20
21# Use functools.reduce to provide the reduce functionality in Python
22from functools import reduce
23
24# Example usage:
25# Create a new function 'composed_fn' by composing functions:
26# first incrementing a number, then doubling it.
27composed_fn = compose([lambda x: x + 1, lambda x: 2 * x])
28# Applying 'composed_fn' to 4 should first double it (2 * 4 = 8),
29# and then increment the result (8 + 1 = 9), so 'composed_fn(4)' should return 9.
30print(composed_fn(4))  # Output: 9
31

1import java.util.function.Function;
2import java.util.List;
3import java.util.Collections;
4
5public class FunctionComposition {
6
7    // Define a functional interface 'FunctionType' for functions that take a number and return a number
8    @FunctionalInterface
9    interface FunctionType extends Function<Integer, Integer> {
10    }
11
12    /**
13     * Composes a list of functions into a single function.
14     * The functions are composed from right to left.
15     * 
16     * @param functions - A list of functions to be composed.
17     * @return A new function that is the result of composing the input functions.
18     */
19    public static FunctionType compose(List<FunctionType> functions) {
20        // Return a function that takes a single argument 'x'
21        return (Integer x) -> {
22            // Use 'reduce' on the reversed list to apply each function from right to left 
23            // to the current result 'result', starting with the initial value 'x'
24            return functions.stream()
25                .reduce((FunctionType) result -> result,
26                        (nextFunction, currentComposition) ->
27                                (x2) -> currentComposition.apply(nextFunction.apply(x2)));
28        };
29    }
30
31    public static void main(String[] args) {
32        // Example usage:
33        // Create a new function 'fn' by composing functions:
34        // first incrementing a number, then doubling it.
35        FunctionType fn = compose(List.of(
36            x -> 2 * x, // Doubling function
37            x -> x + 1  // Incrementing function
38        )); 
39        // Applying 'fn' to 4 should first double it (2 * 4 = 8), 
40        // and then increment the result (8 + 1 = 9), so 'fn.apply(4)' should return 9.
41        System.out.println(fn.apply(4)); // Output: 9
42    }
43}
44

1#include <vector>
2#include <functional>
3#include <numeric>
4
5// Define a type 'FunctionType' for functions that take an int and return an int
6using FunctionType = std::function<int(int)>;
7
8/**
9 * Composes an array of functions into a single function.
10 * The functions are composed from right to left.
11 * 
12 * @param functions - A vector of functions to be composed.
13 * @returns A new function that is the result of composing the input functions.
14 */
15FunctionType compose(const std::vector<FunctionType>& functions) {
16    // Return a function that takes a single argument 'x'
17    return [functions](int x) -> int {
18        // Use 'std::accumulate' with reverse iterators to apply each function
19        // in the vector from right to left to the accumulator 'acc',
20        // starting with the initial value 'x'
21        return std::accumulate(functions.rbegin(), functions.rend(), x,
22            [](int acc, const FunctionType& fn) -> int {
23                // Apply the current function 'fn' to the accumulator 'acc'
24                return fn(acc);
25            }); // Initial value for 'acc' is 'x'
26    };
27}
28
29// Example usage:
30int main() {
31    // Create a new function 'fn' by composing functions:
32    // first incrementing an integer, then doubling it.
33    FunctionType fn = compose({[](int x) { return x + 1; }, [](int x) { return 2 * x; }});
34  
35    // Applying 'fn' to 4 should first double it (2 * 4 = 8),
36    // and then increment the result (8 + 1 = 9), so 'fn(4)' should return 9.
37    std::cout << fn(4) << std::endl; // Output: 9
38
39    return 0;
40}
41

1// Define a type 'FunctionType' for functions that take a number and return a number
2type FunctionType = (x: number) => number;
3
4/**
5 * Composes an array of functions into a single function.
6 * The functions are composed from right to left.
7 * 
8 * @param functions - An array of functions to be composed.
9 * @returns A new function that is the result of composing the input functions.
10 */
11function compose(functions: FunctionType[]): FunctionType {
12    // Return a function that takes a single argument 'x'
13    return function (x: number): number {
14        // Use 'reduceRight' to apply each function in the array from right to left
15        // to the accumulator 'acc', starting with the initial value 'x'
16        return functions.reduceRight((acc: number, fn: FunctionType): number => {
17            // Apply the current function 'fn' to the accumulator 'acc'
18            return fn(acc);
19        }, x); // Initial value for 'acc' is 'x'
20    };
21}
22
23// Example usage:
24// Create a new function 'fn' by composing functions: 
25// first incrementing a number, then doubling it.
26const fn = compose([x => x + 1, x => 2 * x]); 
27// Applying 'fn' to 4 should first double it (2 * 4 = 8), 
28// and then increment the result (8 + 1 = 9), so 'fn(4)' should return 9.
29console.log(fn(4)); // Output: 9
30

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.

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