Curry and partial application in Ruby - Time & Space Complexity

Time Complexity: Curry and partial application

O(n)

Understanding Time Complexity

When using curry and partial application, we want to know how the time to run the code changes as we give it more inputs.

We ask: How does the number of steps grow when we call the curried or partially applied function multiple times?

Scenario Under Consideration

Analyze the time complexity of the following Ruby code using curry and partial application.

add = ->(a, b, c) { a + b + c }
curried_add = add.curry
partial_add = curried_add.call(1)
result = partial_add.call(2).call(3)
    

This code creates a curried version of a function that adds three numbers, then partially applies the first argument, and finally calls the remaining arguments one by one.

Identify Repeating Operations

Look for repeated steps or calls in the code.

• Primary operation: Calling the curried function multiple times to supply arguments.
• How many times: Once per argument after currying (here, two calls after the first partial call).

How Execution Grows With Input

Each argument requires one function call after currying.

Input Size (n)	Approx. Operations
3 (arguments)	3 calls (one initial, two after)
10 (arguments)	10 calls (one initial, nine after)
100 (arguments)	100 calls (one initial, ninety-nine after)

Pattern observation: The number of calls grows linearly with the number of arguments supplied.

Final Time Complexity

Time Complexity: O(n)

This means the time to fully call a curried function grows in a straight line with the number of arguments.

Common Mistake

[X] Wrong: "Currying makes the function run faster because it breaks calls into smaller parts."

[OK] Correct: Currying changes how you call the function but does not reduce the total work; each argument still needs to be processed, so total time grows with the number of arguments.

Interview Connect

Understanding how currying affects time helps you explain function calls clearly and shows you can think about how code scales, a useful skill in many programming tasks.

Self-Check

What if we changed the curried function to accept all arguments at once instead of one by one? How would the time complexity change?

Practice

1. What does currying a function in Ruby allow you to do?

easy

A. Call the function with fewer arguments and get a new function

B. Run the function faster by optimizing code

C. Convert the function into a class method

D. Automatically memoize the function results

Solution

1. Step 1: Understand currying concept

   Currying transforms a function so you can call it with fewer arguments than it needs.

2. Step 2: Result of currying

   When called with fewer arguments, it returns a new function waiting for the rest.

3. Final Answer:

   Call the function with fewer arguments and get a new function -> Option A

4. Quick Check:

   Currying = call fewer args, get new function [OK]

Hint: Currying means breaking function calls into smaller steps [OK]

Common Mistakes:

• Thinking currying speeds up code
• Confusing currying with memoization
• Believing currying changes function to class method

2. Which of the following is the correct way to curry a lambda in Ruby?

easy

A. lambda.curry(my_lambda)

B. curry(my_lambda)

C. my_lambda.partial

D. my_lambda.curry

Solution

1. Step 1: Recall Ruby syntax for currying

   In Ruby, you call the .curry method on a lambda or Proc object.

2. Step 2: Identify correct usage

   Calling my_lambda.curry returns a curried version of the lambda.

3. Final Answer:

   my_lambda.curry -> Option D

4. Quick Check:

   Use .curry method on lambda object [OK]

Hint: Use .curry directly on lambda or Proc [OK]

Common Mistakes:

• Trying to call curry as a standalone function
• Using .partial instead of .curry
• Passing lambda as argument to curry method

3. What is the output of this Ruby code?

add = ->(x, y) { x + y }
curried_add = add.curry
add_five = curried_add.call(5)
puts add_five.call(3)

medium

A. 5

B. 3

C. 8

D. Error

Solution

1. Step 1: Understand currying and calls

   The lambda add takes two arguments and returns their sum. Currying allows calling with one argument to get a new function.

2. Step 2: Trace the calls

   curried_add.call(5) returns a new function that adds 5 to its argument. Calling add_five.call(3) returns 5 + 3 = 8.

3. Final Answer:

   8 -> Option C

4. Quick Check:

   Curried add with 5 then 3 = 8 [OK]

Hint: Currying splits args; add 5 + 3 = 8 [OK]

Common Mistakes:

• Expecting add_five to be a number, not a function
• Confusing call with direct invocation
• Thinking currying changes output type

4. Identify the error in this Ruby code using currying:

multiply = ->(x, y) { x * y }
curried_multiply = multiply.curry
result = curried_multiply(2)(3)
puts result

medium

A. multiply should be defined with def, not lambda

B. No error, code runs correctly and prints 6

C. curry method does not exist for lambdas

D. curried_multiply(2)(3) should be curried_multiply.call(2).call(3)

Solution

1. Step 1: Check syntax for currying and calling

   In Ruby, lambdas can be curried and called using parentheses like functions.

2. Step 2: Verify code behavior

   curried_multiply(2) returns a function that multiplies by 2; calling (3) returns 6. The code runs without error.

3. Final Answer:

   No error, code runs correctly and prints 6 -> Option B

4. Quick Check:

   Currying with lambdas and calls works as shown [OK]

Hint: Parentheses work for calling curried lambdas [OK]

Common Mistakes:

• Thinking .call is required for every call
• Believing curry is not available for lambdas
• Assuming lambdas must be defined with def

5. Given this code, what will be the output?

concat = ->(a, b, c) { "#{a}-#{b}-#{c}" }
curried_concat = concat.curry
partial = curried_concat.call('X').call('Y')
puts partial.call('Z')

What does this demonstrate about currying and partial application?

hard

A. You can fix some arguments step-by-step, creating simpler functions

B. Currying only works if all arguments are given at once

C. Partial application requires a special method, not currying

D. Calling curried functions with fewer arguments causes errors

Solution

1. Step 1: Analyze the currying calls

   The original lambda takes 3 arguments and joins them with dashes. Currying allows calling with one argument at a time.

2. Step 2: Understand partial application here

   Calling curried_concat.call('X') fixes the first argument. Then .call('Y') fixes the second. The resulting function waits for the third argument.

3. Step 3: Output and meaning

   Calling partial.call('Z') returns "X-Y-Z". This shows partial application by fixing some arguments step-by-step.

4. Final Answer:

   You can fix some arguments step-by-step, creating simpler functions -> Option A

5. Quick Check:

   Currying enables partial application stepwise [OK]

Hint: Currying lets you fix args one by one [OK]

Common Mistakes:

• Thinking all args must be given at once
• Confusing currying with separate partial method
• Assuming partial calls cause errors