Proc composition in Ruby - Time & Space Complexity

Time Complexity: Proc composition

O(n)

Understanding Time Complexity

We want to understand how the time needed changes when we combine multiple Procs (small pieces of code) in Ruby.

How does running one Proc after another affect the total work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

add_one = ->(x) { x + 1 }
double = ->(x) { x * 2 }

composed = ->(x) { double.call(add_one.call(x)) }

result = inputs.map(&composed) # assuming inputs is an array of size n
    

This code creates two simple Procs and then combines them so each input goes through both in order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calling each Proc once in sequence.
• How many times: Each Proc is called exactly one time per input.

How Execution Grows With Input

Each input value goes through both Procs one after the other, so the work grows by adding the cost of each Proc.

Input Size (n)	Approx. Operations
10	20 (10 inputs x 2 Procs each)
100	200 (100 inputs x 2 Procs each)
1000	2000 (1000 inputs x 2 Procs each)

Pattern observation: The total work grows directly with the number of inputs, multiplied by the number of Procs composed.

Final Time Complexity

Time Complexity: O(n)

This means the time grows in a straight line as the input size grows, because each input goes through a fixed number of Procs.

Common Mistake

[X] Wrong: "Composing Procs multiplies the time by the number of Procs squared."

[OK] Correct: Each input only passes through each Proc once, so the time adds up, it does not multiply in a more complex way.

Interview Connect

Understanding how combining small pieces of code affects performance helps you write clear and efficient programs, a skill valued in many coding challenges.

Self-Check

"What if we composed Procs inside a loop that runs n times? How would the time complexity change?"

Practice

1. What does the >> operator do when used with two Procs in Ruby?

easy

A. It merges two Procs into one that runs them both in parallel.

B. It creates a new Proc that runs the first Proc, then passes its result to the second Proc.

C. It swaps the order of execution of two Procs.

D. It deletes the second Proc and keeps only the first.

Solution

1. Step 1: Understand Proc composition operator

   The >> operator chains two Procs so the output of the first becomes input of the second.

2. Step 2: Explain the effect of chaining

   Calling the combined Proc runs the first, then passes its result to the second, producing a final result.

3. Final Answer:

   It creates a new Proc that runs the first Proc, then passes its result to the second Proc. -> Option B

4. Quick Check:

   Proc composition = chaining with >> [OK]

Hint: Remember >> chains Procs passing output as input [OK]

Common Mistakes:

• Thinking >> runs Procs in parallel
• Assuming >> swaps execution order
• Believing >> deletes one Proc

2. Which of the following is the correct syntax to compose two Procs p1 and p2 in Ruby?

easy

A. combined = p1 >> p2

B. combined = p1 >>> p2

C. combined = p1 << p2

D. combined = p1 >> p2.call

Solution

1. Step 1: Recall correct Proc composition operator

   The operator to compose Procs is >>, which is written as >> but in Ruby code it is >> (two greater-than signs).

2. Step 2: Check each option

   combined = p1 >> p2 uses >> correctly. combined = p1 >>> p2 uses three > which is invalid. combined = p1 << p2 uses << which is not for composition. combined = p1 >> p2.call calls p2 immediately, which is wrong.

3. Final Answer:

   combined = p1 >> p2 -> Option A

4. Quick Check:

   Proc composition syntax = p1 >> p2 [OK]

Hint: Use exactly two > signs to compose Procs [OK]

Common Mistakes:

• Using >>> instead of >>
• Using << instead of >>
• Calling Proc instead of composing

3. What is the output of this Ruby code?

p1 = Proc.new { |x| x + 2 }
p2 = Proc.new { |y| y * 3 }
combined = p1 >> p2
puts combined.call(4)

medium

A. 18

B. 14

C. 20

D. 12

Solution

1. Step 1: Evaluate first Proc with input 4

   p1 adds 2 to input: 4 + 2 = 6.

2. Step 2: Pass result 6 to second Proc

   p2 multiplies input by 3: 6 * 3 = 18.

3. Final Answer:

   18 -> Option A

4. Quick Check:

   (4 + 2) * 3 = 18 [OK]

Hint: Apply first Proc, then second on result [OK]

Common Mistakes:

• Adding instead of multiplying in second Proc
• Multiplying first, then adding
• Confusing order of Procs

4. Identify the error in this Ruby code that tries to compose two Procs:

p1 = Proc.new { |x| x * 2 }
p2 = Proc.new { |y| y + 5 }
combined = p1 >> p2.call
puts combined.call(3)

medium

A. Syntax error due to missing parentheses

B. Using wrong operator for composition

C. Missing block parameters in p1

D. Calling p2 immediately instead of composing

Solution

1. Step 1: Check how p2 is used in composition

   The code uses p2.call which calls p2 immediately, returning a value, not a Proc.

2. Step 2: Understand correct composition usage

   To compose, use p1 >> p2 without calling p2. Calling p2 breaks composition.

3. Final Answer:

   Calling p2 immediately instead of composing -> Option D

4. Quick Check:

   Compose Procs without calling them [OK]

Hint: Do not call Procs when composing, just use >> [OK]

Common Mistakes:

• Calling Proc instead of composing
• Using wrong operator like <<
• Forgetting block parameters

5. Given these Procs:

p1 = Proc.new { |x| x.to_s }
p2 = Proc.new { |s| s + "!" }
p3 = Proc.new { |str| str.reverse }

How do you compose them so that calling the combined Proc with 5 returns "5!"?

hard

A. combined = p3 >> p2 >> p1

B. combined = p1 >> p2 >> p3

C. combined = p1 >> p3 >> p2

D. combined = p2 >> p1 >> p3

Solution

1. Step 1: Understand each Proc's effect

   p1 converts number to string, p2 adds "!", p3 reverses string.

2. Step 2: Find composition order to get "5!"

   "5".reverse = "5", so p1 >> p3 >> p2 gives: "5" -> "5" -> "5!". But p1 >> p2 >> p3: "5" -> "5!" -> "!5". Only A produces "5!".

3. Final Answer:

   combined = p1 >> p3 >> p2 -> Option C

4. Quick Check:

   to_s, reverse, then add ! = "5!" [OK]

Hint: Order Procs by desired transformations stepwise [OK]

Common Mistakes:

• Putting p2 before p3 changes output to "!5"
• Reversing order causes errors on non-string
• Ignoring effect of reverse on "5!"