SelflessSingleton

Inject And Zip With The Y-Combinator

February 20, 2015 ยป 6 minutes (1137 words)

Lately I've wondered what it would be like to try to write some of Ruby's enumerable methods using only lambdas. I previously had given a talk about the Y combinator and was already familiar with the notion of a fixed point combinator. I was curious to see what it would take to implement Ruby's inject method supporting the basic arithmetic operations and Ruby's zip method.

To follow this post, I'm assuming you have a comfortable familiarity with the Y-combinator. If you're new to the Y-combinator, I would suggest first viewing an inspiring and thorough talk given by the late Jim Weirich. The overview he provides of how the Y-combinator works, along with the explanations about the underlying concepts from lambda calculus used by Haskell Curry to formally define the Y-combinator will give you a solid foundation for understanding the concept. However, in a nutshell, the Y-combinator allows us the ability to employ recursion using only anonymous functions.

Let's take a look at a classic example of a Y-combinator application - calculating a factorial. You'll notice that the result is stored as a local variable, but otherwise the recursion is handled entirely via anonymous functions via Ruby's lambda short-hand operator, the -> operator.

 1 # Find the factorial of 5
 2 5 * 4 * 3 * 2 * 1 = 120
 3 
 4 # Y-combinator solution
 5 result = -> (builder, number) { builder.call(builder, number) }.call(
 6   -> (recurse, number) {
 7     return 1 if number == 0
 8     return number * recurse.call(recurse, number - 1)
 9   },
10   5
11 )
12 
13 result # => 120

Given that we have this example of a factorial Y-combinator, let's take a look at what inject looks like given the constraint of only using anonymous functions.

 1 # Ruby inject example
 2 [*0..10].inject(&:+) # => 55
 3 
 4 # Y-combinator solution
 5 result = -> (builder, limit, count = 0) { builder.call(builder, limit, count) }.call(
 6   -> (recurse, limit, count) {
 7     return 0 if count > limit
 8     return count + recurse.call(recurse, limit, count + 1)
 9   },
10   10
11 )
12 
13 result # => 55

This Y-combinator gives us the correct result, but there are limitations with this solution. The first is that we are required to pass in a limit as an input parameter rather than a collection or a range with arbitrary start and stop points. This solution is also only capable of addition. Should we choose to implement inject-like functionality using multiplication instead, we would have to duplicate most of this solution. Let's make our Y-combinator solution a little more sophisticated, so that it can handle a range or collection as an input parameter, and also support any of the basic arithmetic operations.

 1 # Ruby inject example
 2 [100, 10].inject(&:*) # => 1000
 3 
 4 # Y-combinator solution
 5 result = -> (builder, range, operator) { builder.call(builder, range, operator) }.call(
 6   -> (recurse, range, operator, count = 0) {
 7     if range[count] == range[-1]
 8       return range[count].send(operator, operator == :* || operator == :/ ? 1 : 0)
 9     else
10       return range[count].send(operator, recurse.call(recurse, range, operator, count + 1))
11     end
12   },
13   [100, 10],
14   :*
15 )
16 
17 result # => 1000

The approach now takes in a range or collection and an operator as input parameters. In order to support a generic Y-combinator that allows for any arithmetic operation, we make use of the various arithmetic identities. Given Ruby's Smalltalk roots, we can send the operator message to each of the elements in the provided range or collection. To prove this works, I've included examples of subtraction and division below.

 1 # Ruby inject example with subtraction
 2 [100, 10].inject(&:-) # => 90
 3 
 4 # Y-combinator solution
 5 result = -> (builder, range, operator) { builder.call(builder, range, operator) }.call(
 6   -> (recurse, range, operator, count = 0) {
 7     if range[count] == range[-1]
 8       return range[count].send(operator, operator == :* || operator == :/ ? 1 : 0)
 9     else
10       return range[count].send(operator, recurse.call(recurse, range, operator, count + 1))
11     end
12   },
13   [100, 10],
14   :-
15 )
16 
17 result # => 90
18 
19 # Ruby inject example with division
20 [100, 10].inject(&:/) # => 10
21 
22 # Y-combinator solution
23 result = -> (builder, range, operator) { builder.call(builder, range, operator) }.call(
24   -> (recurse, range, operator, count = 0) {
25     if range[count] == range[-1]
26       return range[count].send(operator, operator == :* || operator == :/ ? 1 : 0)
27     else
28       return range[count].send(operator, recurse.call(recurse, range, operator, count + 1))
29     end
30   },
31   [100, 10],
32   :/
33 )
34 
35 result # => 10

Now let's take a look at Ruby's zip method. This one is a little more interesting because it involves two collections.

 1 # Ruby zip example
 2 [*0..5].zip([*100..105]) # => [[0, 100], [1, 101], [2, 102], [3, 103], [4, 104], [5, 105]]
 3 
 4 result = -> (builder, collection1, collection2, count = 0) { builder.call(builder, collection1, collection2, count) }.call(
 5   -> (recurse, collection1, collection2, count) {
 6     return [] if count == collection1.count
 7     return recurse.call(recurse, collection1, collection2, count + 1).push([collection1[collection1.count - 1 - count], collection2[collection2.count - 1 - count]])
 8   },
 9   [*0..5],
10   [*100..105]
11 )
12 
13 result # => [[0, 100], [1, 101], [2, 102], [3, 103], [4, 104], [5, 105]]

I ran into a problem initially with implementing zip as a Y-combinator. Ruby does not have a cons function similar to cons found in Lisp or Scheme. I reasoned I could create an accumulator variable and pass it along through each recursive call, but the mutation of that accumulator variable is troubling. I reasoned that the base case of the recursive function would instead return an empty array, to which the zipped tuples of both collections would be added.

Just for fun I was curious to see how the Y-combinator zip solution profiled against Ruby's zip method. The results are unsurprising. Ruby's native zip method is far better optimized than recursive lambda calls.

 1 require 'benchmark'
 2 
 3 native_result = Benchmark.measure do
 4   10000.times do
 5     [*0..100].zip([*0..100])
 6   end
 7 end
 8 
 9 native_result.real # => 0.177837
10 
11 y_combinator_result = Benchmark.measure do
12   10000.times do
13     -> (builder, collection1, collection2, count = 0) { builder.call(builder, collection1, collection2, count) }.call(
14       -> (recurse, collection1, collection2, count) {
15         return [] if count == collection1.count
16         return recurse.call(recurse, collection1, collection2, count + 1).push([collection1[collection1.count - 1 - count], collection2[collection2.count - 1 - count]])
17       },
18       [*0..100],
19       [*0..100]
20     )
21   end
22 end
23 
24 y_combinator_result.real # => 0.61685
25 
26 (native_result.real - y_combinator_result.real) / native_result.real.to_f * 100 # => -246%

Although the Y-combinator zip method is roughly 246% less performant than Ruby's native zip method, the exercise of implementing two of Ruby's enumerable methods using Y-combinators was good fun. This post was originally inspired by Tom Stuart's amazing programming with nothing, and is also available as a talk.