Problem Description

This problem asks you to create a function that performs function composition on an array of functions.

Function composition means applying multiple functions in sequence, where the output of one function becomes the input of the next. When you have functions [f1, f2, f3, ..., fn], the composed function should work from right to left.

For example:

• If you have [f(x), g(x), h(x)], the composition creates a new function where fn(x) = f(g(h(x)))
• This means h is applied first to x, then g is applied to that result, and finally f is applied to that result

Key requirements:

• Each function in the input array takes one integer as input and returns one integer as output
• The composed function should also take one integer and return one integer
• If the array is empty, return the identity function (a function that returns its input unchanged: f(x) = x)

Example walkthrough:

• Given compose([x => x + 1, x => 2 * x]) and calling fn(4):
  1. Start with x = 4
  2. Apply the rightmost function: 2 * 4 = 8
  3. Apply the next function: 8 + 1 = 9
  4. Return 9

The solution uses reduceRight to iterate through the functions array from right to left, applying each function to the accumulated result, starting with the initial input value x.

Intuition

The key insight is recognizing that function composition naturally follows a right-to-left execution pattern. When we write f(g(h(x))), we evaluate from the innermost function outward - first h(x), then g of that result, then f of that result.

This right-to-left pattern immediately suggests using reduceRight as our core mechanism. The reduceRight method processes array elements from right to left, which perfectly matches our composition order.

Think of it like a pipeline running backwards:

• We start with our initial value x
• We pass it through the rightmost function
• The output becomes the input for the next function to the left
• This continues until we've processed all functions

Why reduceRight is the natural choice:

1. It automatically handles the right-to-left iteration we need
2. It maintains an accumulator (acc) that carries the result from one function to the next
3. It elegantly handles the empty array case - when there are no functions, reduceRight returns the initial value unchanged, giving us the identity function behavior for free

The solution structure becomes clear:

• Return a new function that captures the functions array in its closure
• When this new function is called with x, use reduceRight to thread x through all functions
• Each step applies the current function fn to the accumulated result acc
• The initial accumulator value is x itself

This approach is both concise and efficient, avoiding the need for explicit loops or recursion while naturally handling all edge cases.

Solution Approach

The implementation uses a higher-order function pattern - a function that returns another function. Let's break down the solution step by step:

Function Signature:

function compose(functions: F[]): F

• Takes an array of functions as input
• Returns a new function of the same type F (a function that accepts and returns a number)

Creating the Composed Function:

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

The solution creates and returns an anonymous function that:

1. Accepts a single parameter x (the initial input)
2. Uses reduceRight to process the functions array

How reduceRight Works Here:

• Callback function: (acc, fn) => fn(acc)
  • acc is the accumulator (the running result)
  • fn is the current function being processed
  • Simply applies the current function to the accumulated value
• Initial value: x (the input to our composed function)
• Direction: Processes array from right to left

Execution Flow Example: For compose([f, g, h])(x):

1. Start with accumulator = x
2. Process h: accumulator = h(x)
3. Process g: accumulator = g(h(x))
4. Process f: accumulator = f(g(h(x)))
5. Return final accumulator value

Edge Case Handling:

• Empty array: When functions is empty, reduceRight returns the initial value x unchanged, automatically giving us the identity function behavior
• Single function: Works correctly, applying just that one function
• Multiple functions: Chains them in the correct right-to-left order

The beauty of this solution lies in its simplicity - reduceRight naturally handles the composition pattern without any explicit conditionals or loops, making the code both readable and efficient.

Example Walkthrough

Let's trace through a concrete example to understand how the solution works.

Given:

functions = [x => x + 1, x => x * x, x => 2 * x]
compose(functions)(5)

Step-by-step execution:

1. Initial Setup:

   • We call the composed function with x = 5
   • reduceRight starts from the rightmost function
   • Initial accumulator = 5

2. First iteration (rightmost function: x => 2 * x):

   • Current function: fn = x => 2 * x
   • Current accumulator: acc = 5
   • Apply function: fn(acc) = 2 * 5 = 10
   • New accumulator = 10

3. Second iteration (middle function: x => x * x):

   • Current function: fn = x => x * x
   • Current accumulator: acc = 10
   • Apply function: fn(acc) = 10 * 10 = 100
   • New accumulator = 100

4. Third iteration (leftmost function: x => x + 1):

   • Current function: fn = x => x + 1
   • Current accumulator: acc = 100
   • Apply function: fn(acc) = 100 + 1 = 101
   • New accumulator = 101

5. Final Result:

   • reduceRight completes and returns 101
   • The composed function returns 101

Verification: This is equivalent to computing (x + 1)((x * x)(2 * x)) with x = 5:

• First: 2 * 5 = 10
• Then: 10 * 10 = 100
• Finally: 100 + 1 = 101 ✓

Empty Array Case:

functions = []
compose(functions)(5)

• reduceRight with empty array returns initial value unchanged
• Result: 5 (identity function behavior)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of functions in the array.

When compose is called, it returns a new function immediately in O(1) time. However, when the returned function is invoked with a value x, it executes reduceRight which iterates through all n functions in the array, applying each function exactly once. Each function application is assumed to be O(1), so the total time complexity of executing the composed function is O(n).

Space Complexity: O(n) where n is the number of functions in the array.

The space complexity includes:

• The returned function holds a reference to the functions array through closure, which takes O(n) space
• During execution of reduceRight, the call stack depth is O(1) since reduceRight is implemented iteratively in JavaScript
• The intermediate value acc takes O(1) space

Therefore, the overall space complexity is O(n) due to storing the reference to the functions array in the closure.

Common Pitfalls

1. Incorrect Order of Composition

The most common mistake is applying functions in left-to-right order instead of right-to-left. Many developers intuitively think of reading the array from start to end.

Wrong Implementation:

def compose(functions: List[F]) -> F:
    def composed_function(x: float) -> float:
        accumulator = x
        for fn in functions:  # Wrong: iterates left to right
            accumulator = fn(accumulator)
        return accumulator
    return composed_function

Impact: For compose([f, g, h])(x), this gives f(g(h(x))) instead of the correct f(g(h(x))). Wait, that looks the same! But consider compose([x => x + 1, x => 2 * x])(4):

• Wrong: (4 + 1) * 2 = 10
• Correct: (2 * 4) + 1 = 9

Solution: Always use reversed() or iterate backwards through the array.

2. Mutating the Original Functions Array

Some implementations might accidentally modify the input array when trying to reverse it.

Wrong Implementation:

def compose(functions: List[F]) -> F:
    functions.reverse()  # Mutates the original array!
    def composed_function(x: float) -> float:
        accumulator = x
        for fn in functions:
            accumulator = fn(accumulator)
        return accumulator
    return composed_function

Solution: Use reversed() which returns an iterator without modifying the original list, or create a copy before reversing.

3. Type Confusion with Return Values

Forgetting that each function must return a value that can be passed to the next function.

Wrong Usage:

# This will fail if any function returns None
functions = [
    lambda x: print(x),  # Returns None!
    lambda x: x * 2
]

Solution: Ensure all functions in the array return appropriate values:

functions = [
    lambda x: (print(f"Value: {x}"), x)[1],  # Prints and returns x
    lambda x: x * 2
]

4. Not Handling Edge Cases Properly

Explicitly checking for empty arrays with unnecessary conditional logic.

Overcomplicated Implementation:

def compose(functions: List[F]) -> F:
    def composed_function(x: float) -> float:
        if len(functions) == 0:  # Unnecessary check
            return x
        accumulator = x
        for fn in reversed(functions):
            accumulator = fn(accumulator)
        return accumulator
    return composed_function

Solution: The loop naturally handles empty arrays - when there are no functions to iterate over, the accumulator remains as the initial value x, giving us the identity function behavior automatically.

5. Performance Issues with Large Function Arrays

Creating unnecessary intermediate data structures or copies.

Inefficient Implementation:

def compose(functions: List[F]) -> F:
    def composed_function(x: float) -> float:
        reversed_list = list(reversed(functions))  # Creates unnecessary copy
        accumulator = x
        for fn in reversed_list:
            accumulator = fn(accumulator)
        return accumulator
    return composed_function

Solution: Use reversed() directly as an iterator without converting to a list, or use negative indexing to iterate backwards without creating any copies:

def compose(functions: List[F]) -> F:
    def composed_function(x: float) -> float:
        accumulator = x
        for i in range(len(functions) - 1, -1, -1):
            accumulator = functions[i](accumulator)
        return accumulator
    return composed_function