# Waquo/combinators-info.github.com

Switch branches/tags
Nothing to show
Fetching contributors…
Cannot retrieve contributors at this time
1181 lines (941 sloc) 144 KB
 8 Refactoring Methods with Recursive Combinators

8 Refactoring Methods with Recursive Combinators

In previous chapters, we have met some of Combinatory Logic’s most interesting combinators like the Kestrel, Thrush, Cardinal, Quirky Bird, and Bluebird. Today we are going to learn how combinators can help us separate the general form of an algorithm like “divide and conquer” from its specific concrete steps. Consider the method #sum_squares: It sums the squares of a tree of numbers, represented as a nested list.

def sum_squares(value)
if value.kind_of?(Enumerable)
value.map do |sub_value|
sum_squares(sub_value)
end.inject() { |x,y| x + y }
else
value ** 2
end
end

p sum_squares([1, 2, 3, [[4,5], 6], [[[7]]]])
=> 140

And the method #rotate: It rotates a square matrix, provided the length of each side is a power of two:

def rotate(square)
if square.kind_of?(Enumerable) && square.size > 1
half_sz = square.size / 2
sub_square = lambda do |row, col|
square.slice(row, half_sz).map { |a_row| a_row.slice(col, half_sz) }
end
upper_left = rotate(sub_square.call(0,0))
lower_left = rotate(sub_square.call(half_sz,0))
upper_right = rotate(sub_square.call(0,half_sz))
lower_right = rotate(sub_square.call(half_sz,half_sz))
upper_right.zip(lower_right).map { |l,r| l + r } +
upper_left.zip(lower_left).map { |l,r| l + r }
else
square
end
end

p rotate([[1,2,3,4], [5,6,7,8], [9,10,11,12], [13,14,15,16]])
=> [[4, 8, 12, 16], [3, 7, 11, 15], [2, 6, 10, 14], [1, 5, 9, 13]]

Our challenge is to refactor them. You could change sub_square from a closure to a private method (and in languages like Java, you have to do that in the first place). What else? Is there any common behaviour we can extract from these two methods?

Looking at the two methods, there are no lines of code that are so obviously identical that we could mechanically extract them into a private helper. Automatic refactoring tools fall down given these two methods. And yet, there is a really, really important refactoring that should be performed here.

8.1 Divide and Conquer

Both of these methods use the Divide and Conquer strategy.

As described, there are two parts to each divide and conquer algorithm. We’ll start with conquer: you need a way to decide if the problem is simple enough to solve in a trivial manner, and a trivial solution. You’ll also need a way to divide the problem into sub-problems if it’s too complex for the trivial solution, and a way to recombine the pieces back into the solution. The entire process is carried our recursively.

For example, here’s how #rotate rotated the square. We started with a square matrix of size 4:

[
[  1,  2,  3,  4],
[  5,  6,  7,  8],
[  9, 10, 11, 12],
[ 13, 14, 15, 16]
]

That cannot be rotated trivially, so we divided it into four smaller sub-squares:

[            [
[  1,  2],   [  3,  4],
[  5,  6]    [  7,  8]
]            ]

[            [
[  9, 10],   [ 11, 12],
[ 13, 14]    [ 15, 16]
]            ]

Those couldn’t be rotated trivially either, so our algorithm divide each of them into four smaller squares again, giving us sixteen squares of one number each. Those are small enough to rotate trivially (they do not change), so the algorithm could stop subdividing.

We said there was a recombination step. For #rotate, four sub-squares are recombined into one square by moving them counter-clockwise 90 degrees. The sixteen smallest squares were recombined into four sub-squares like this:

[            [
[  2,  6],   [  4,  8],
[  1,  5]    [  3,  7]
]            ]

[            [
[ 10, 14],   [ 12, 16],
[  9, 13]    [ 11, 15]
]            ]

Then those four squares were recombined into the final result like this:

[            [
[  4,  8],   [ 12, 16],
[  3,  7]    [ 11, 15]
]            ]

[            [
[  2,  6],   [ 10, 14],
[  1,  5]    [  9, 13]
]

And smooshed (that is the technical term) back together:

[
[  4,  8,  12, 16],
[  3,  7,  11, 15],
[  2,  6,  10, 14],
[  1,  5,   9, 13]
]

And Voila! There is your rotated square matrix.

Both rotation and summing the squares of a tree combine the four steps of a divide and conquer strategy:

1. Deciding whether the problem is divisible into smaller pieces or can be solved trivially,
2. A solution fro the trivial case,
3. A way to divide a non-trivial problem up,
4. And a way to piece it back together.

Here are the two methods re-written to highlight the common strategy. First, #sum_squares_2:

public

def sum_squares_2(value)
if sum_squares_divisible?(value)
sum_squares_recombine(
sum_squares_divide(value).map { |sub_value| sum_squares_2(sub_value) \
}
)
else
sum_squares_conquer(value)
end
end

private

def sum_squares_divisible?(value)
value.kind_of?(Enumerable)
end

def sum_squares_conquer(value)
value ** 2
end

def sum_squares_divide(value)
value
end

def sum_squares_recombine(values)
values.inject() { |x,y| x + y }
end

And #rotate_2:

public

def rotate_2(value)
if rotate_divisible?(value)
rotate_recombine(
rotate_divide(value).map { |sub_value| rotate_2(sub_value) }
)
else
rotate_conquer(value)
end
end

private

def rotate_divisible?(value)
value.kind_of?(Enumerable) && value.size > 1
end

def rotate_conquer(value)
value
end

def rotate_divide(value)
half_sz = value.size / 2
sub_square = lambda do |row, col|
value.slice(row, half_sz).map { |a_row| a_row.slice(col, half_sz) }
end
upper_left = sub_square.call(0,0)
lower_left = sub_square.call(half_sz,0)
upper_right = sub_square.call(0,half_sz)
lower_right = sub_square.call(half_sz,half_sz)
[upper_left, lower_left, upper_right, lower_right]
end

def rotate_recombine(values)
upper_left, lower_left, upper_right, lower_right = values
upper_right.zip(lower_right).map { |l,r| l + r } +
upper_left.zip(lower_left).map { |l,r| l + r }
end

Now the common code is glaringly obvious. The main challenge in factoring it into a helper is deciding whether you want to represent methods like #rotate_divide as lambdas or want to fool around specifying method names as symbols. Let’s go with lambdas for the sake of writing a clear example:

public

def sum_squares_3(list)
divide_and_conquer(
list,
:divisible? => lambda { |value| value.kind_of?(Enumerable) },
:conquer    => lambda { |value| value ** 2 },
:divide     => lambda { |value| value },
:recombine  => lambda { |list| list.inject() { |x,y| x + y } }
)
end

def rotate_3(square)
divide_and_conquer(
square,
:divisible? => lambda { |value| value.kind_of?(Enumerable) && value.siz\
e > 1 },
:conquer => lambda { |value| value },
:divide => lambda do |square|
half_sz = square.size / 2
sub_square = lambda do |row, col|
square.slice(row, half_sz).map { |a_row| a_row.slice(col, half_sz) }
end
upper_left = sub_square.call(0,0)
lower_left = sub_square.call(half_sz,0)
upper_right = sub_square.call(0,half_sz)
lower_right = sub_square.call(half_sz,half_sz)
[upper_left, lower_left, upper_right, lower_right]
end,
:recombine => lambda do |list|
upper_left, lower_left, upper_right, lower_right = list
upper_right.zip(lower_right).map { |l,r| l + r } +
upper_left.zip(lower_left).map { |l,r| l + r }
end
)
end

private

def divide_and_conquer(value, steps)
if steps[:divisible?].call(value)
steps[:recombine].call(
steps[:divide].call(value).map { |sub_value| divide_and_conquer(sub_v\
alue, steps) }
)
else
steps[:conquer].call(value)
end
end

Now we have refactored the common algorithm out. Typically, something like divide and conquer is treated as a “pattern,” a recipe for writing methods. We have changed it into an abstraction by writing a #divide_and_conquer method and passing it our own functions which it combines to form the final algorithm. That ought to sound familiar: #divide_and_conquer is a combinator that creates recursive methods for us.

You can also find recursive combinators in other languages like Joy, Factor, and even Javascript (the recursive combinator presented here as #divide_and_conquer is normally called multirec). Eugene Lazutkin’s article on [Using recursion combinators in JavaScript](http://lazutkin.com/blog/2008/jun/30/using-recursion-combinators-javascript/ “”) shows how to use combinators to build divide and conquer algorithms in Javascript with the Dojo libraries. This example uses binrec, a recursive combinator for algorithms that always divide their problems in two:

var fib0 = function(n){
return n <= 1 ? 1 :
arguments.callee.call(this, n - 1) +
arguments.callee.call(this, n - 2);
};

var fib1 = binrec("<= 1", "1", "[[n - 1], [n - 2]]", "+");

8.2 The Merge Sort

Let’s look at another example, implementing a merge sort. This algorithm has a distinguished pedigree: It was invented by John Von Neumann in 1945.

Von Neumann was a brilliant and fascinating individual. he is most famous amongst Computer Scientists for formalizing the computer architecture which now bears his name. he also worked on game theory, and it was no game to him: He hoped to use math to advise the United States whether an when to launch a thermonuclear war on the USSR. If you are interested in reading more, Prisoner’s Dilemma is a very fine book about both game theory and one of the great minds of modern times.

Conceptually, a merge sort works as follows:

• If the list is of length 0 or 1, then it is already sorted.
• Otherwise:
1. Divide the unsorted list into two sublists of about half the size.
2. Sort each sublist recursively by re-applying merge sort.
3. Merge the two sublists back into one sorted list.

The merge sort part will be old hat given our #divide_and_conquer helper:

def merge_sort(list)
divide_and_conquer(
list,
:divisible? => lambda { |list| list.length > 1 },
:conquer    => lambda { |list| list },
:divide     => lambda do |list|
half_index = (list.length / 2) - 1
[ list[0..half_index], list[(half_index + 1)..-1] ]
end,
:recombine  => lambda { |pair| merge_two_sorted_lists(pair.first, pair.\
last) }
)
end

The interesting part is our #merge_two_sorted_lists method. Given two sorted lists, our merge algorithm works like this:

• If either list is of length zero, return the other list.
• Otherwise:
1. Compare the first item of each list using <=>. Let’s call the list which has the “preceding” first item the preceding list and the list which has the “following” first item the following list.
2. Create a pair of lists consisting of the preceding item and an empty list, and another pair of lists consisting of the remainder of the preceding list and the entire following list.
3. Merge each pair of lists recursively by applying merge two sorted lists.
4. Catenate the results together.

As you can tell from the description, this is another divide and conquer algorithm:

def merge_two_sorted_lists(*pair)
divide_and_conquer(
pair,
:divisible? => lambda { |pair| !pair.first.empty? && !pair.last.empty? \
},
:conquer => lambda do |pair|
if pair.first.empty? && pair.last.empty?
[]
elsif pair.first.empty?
pair.last
else
pair.first
end
end,
:divide => lambda do |pair|
preceding, following = case pair.first.first <=> pair.last.first
when -1: [pair.first, pair.last]
when 0:  [pair.first, pair.last]
when 1:  [pair.last, pair.first]
end
[
[[preceding.first], []],
[preceding[1..-1], following]
]
end,
:recombine => lambda { |pair| pair.first + pair.last }
)
end

That’s great. Well, that’s barely ok, actually. The problem is that when doing our merge sort, when we decide which item is the preceding item (least most, front most, whatever you want to call it), we already know that it is a trivial item and that it doesn’t need any further merging. The only reason we bundle it up in [[preceding.first], []] is because our #divide_and_conquer method expects to recursively attempt to solve all of the sub-problems we generate.

In this case, #merge_two_sorted_lists does not really divide a problem into a list of one or more sub-problems, some of which may or may not be trivially solvable. Instead, it divides a problem into a part of the solution and a single sub-problem which may or may not be trivially solvable. This common strategy also has a name, linear recursion.

Let’s write another version of #merge_two_sorted_lists, but his time instead of using #divide_and_conquer, we’ll write a linear recursion combinator:

def merge_two_sorted_lists(*pair)
linear_recursion(
pair,
:divisible? => lambda { |pair| !pair.first.empty? && !pair.last.empty? \
},
:conquer => lambda do |pair|
if pair.first.empty? && pair.last.empty?
[]
elsif pair.first.empty?
pair.last
else
pair.first
end
end,
:divide => lambda do |pair|
preceding, following = case pair.first.first <=> pair.last.first
when -1: [pair.first, pair.last]
when 0:  [pair.first, pair.last]
when 1:  [pair.last, pair.first]
end
[ preceding.first, [preceding[1..-1], following] ]
end,
:recombine => lambda { |trivial_bit, divisible_bit| [trivial_bit] + div\
isible_bit }
)
end

def linear_recursion(value, steps)
if steps[:divisible?].call(value)
trivial_part, sub_problem = steps[:divide].call(value)
steps[:recombine].call(
trivial_part, linear_recursion(sub_problem, steps)
)
else
steps[:conquer].call(value)
end
end

You may think this is even better, and it is.

8.3 Separating Declaration from Implementation

Using recursive combinators like #divide_and_conquer and #linear_recursion are abstraction wins. They make recursive code much easier to read, because you know the general form of the algorithm and don’t need to pick through it to discover the individual steps. But there’s another benefit we should consider: Recursive combinators separate declaration from implementation.

Consider #linear_recursion again. This is not the fastest possible implementation. There is a long and tedious argument that arises when one programmer argues it should be implemented with iteration for performance, and the other argues it should be implemented with recursion for clarity, and a third programmer who never uses recursion claims the iterative solution is easier to understand…

Imagine a huge code base full of #linear_recursion and #divide_and_conquer calls. What happens if you decide that each one of these algorithms should be implemented with iteration? Hmmm… How about we modify #linear_recursion and #divide_and_conquer, and all of the methods that call them switch from recursion to iteration for free?

Or perhaps we decide that we really should take advantage of multiple threads… Do you see where this is going? You can write a new implementation and again, all of the existing methods are upgraded.

Even if you do not plan to change the implementation, let’s face a simple fact: when writing a brand new recursive or iterative method, you really have two possible sources of bugs: you may not have declared the solution correctly, and you may not implement it correctly.

Using combinators like #divide_and_conquer simplifies things: You only need to get your declaration of the solution correct, the implementation is taken care of for you. This is a tremendous win when writing recursive functions.

For these reasons, I strongly encourage the use of recursion combinators, either those supplied here or ones you write for yourself.

8.4 Practical Recursive Combinators

We’ve seen how recursive combinators like #divide_and_conquer and #linear_recursion are abstraction wins. They make recursive code much easier to read, because you know the general form of the algorithm and don’t need to pick through it to discover the individual steps.

We also saw that by separating the recursion implementation from the declaration of how to perform the steps of an algorithm like #rotate, we leave ourselves the opportunity to improve the performance of our implementation without the risk of adding bugs to our declaration. And today we’re going to do just that, along with a few tweaks for usability.

In this section, we’re going to optimize our combinators’ performance and make them a little easier to use with goodies like string_to_proc. To do that, we’re going to work with closures, defining methods with define_method, and implement functional programming’s partial application. We’ll wrap up by converting linrec from a recursive to an iterative implementation.

First, a little organization. Here are the original examples. I’ve placed them in a module and named the combinators multirec and linrec in conformance with common practice:

module RecursiveCombinators

def multirec(value, steps)
if steps[:divisible?].call(value)
steps[:recombine].call(
steps[:divide].call(value).map { |sub_value| multirec(sub_value, st\
eps) }
)
else
steps[:conquer].call(value)
end
end

def linrec(value, steps)
if steps[:divisible?].call(value)
trivial_part, sub_problem = steps[:divide].call(value)
steps[:recombine].call(
trivial_part, linrec(sub_problem, steps)
)
else
steps[:conquer].call(value)
end
end

module_function :multirec, :linrec

end

Since they are also module functions, call them by sending a message to the module:

def merge_sort(list)
RecursiveCombinators.multirec(
list,
:divisible? => lambda { |list| list.length > 1 },
:conquer    => lambda { |list| list },
:divide     => lambda do |list|
half_index = (list.length / 2) - 1
[ list[0..half_index], list[(half_index + 1)..-1] ]
end,
:recombine  => lambda { |pair| merge_two_sorted_lists(pair.first, pair.\
last) }
)
end

Or you can include the RecursiveCombinators module and call either method directly:

include RecursiveCombinators

def merge_two_sorted_lists(*pair)
linrec(
pair,
:divisible? => lambda { |pair| !pair.first.empty? && !pair.last.empty? \
},
:conquer => lambda do |pair|
if pair.first.empty? && pair.last.empty?
[]
elsif pair.first.empty?
pair.last
else
pair.first
end
end,
:divide => lambda do |pair|
preceding, following = case pair.first.first <=> pair.last.first
when -1: [pair.first, pair.last]
when 0:  [pair.first, pair.last]
when 1:  [pair.last, pair.first]
end
[ preceding.first, [preceding[1..-1], following] ]
end,
:recombine => lambda { |trivial_bit, divisible_bit| [trivial_bit] + div\
isible_bit }
)
end

merge_sort([8, 3, 10, 1, 9, 5, 7, 4, 6, 2])
=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Ok, we’re ready for some slightly more substantial work. These methods were fine for illustration, but I have a few questions for the author(!)

8.5 Spicing things up

First, note that every single time we call a method like merge_sort, we create four new lambdas from scratch. This seems wasteful, especially since the lambdas never change. Why create some objects just to throw them away?

On the other hand, it’s nice to be able to use create algorithms without having to define a method by name. Although I probably wouldn’t do a merge sort anonymously, when I need a one-off quickie, I might like to write something like:

RecursiveCombinators.multirec(
[1, 2, 3, [[4,5], 6], [[[7]]]],
:divisible? => lambda { |value| value.kind_of?(Enumerable) },
:conquer    => lambda { |value| value ** 2 },
:divide     => lambda { |value| value },
:recombine  => lambda { |list| list.inject() { |x,y| x + y } }
)
=> 140

But when I want a permanent sum of the squares method, I don’t want to write:

def sum_squares(list)
RecursiveCombinators.multirec(
list,
:divisible? => lambda { |value| value.kind_of?(Enumerable) },
:conquer    => lambda { |value| value ** 2 },
:divide     => lambda { |value| value },
:recombine  => lambda { |list| list.inject() { |x,y| x + y } }
)
end

…because that would create four lambdas every time I call the function. There are a couple of ways around this problem. First, our “recipe” for summing squares is a simple hash. We could extract that from the method into a constant:

SUM_SQUARES_RECIPE = {
:divisible? => lambda { |value| value.kind_of?(Enumerable) },
:conquer    => lambda { |value| value ** 2 },
:divide     => lambda { |value| value },
:recombine  => lambda { |list| list.inject() { |x,y| x + y } }
}

def sum_squares(list)
RecursiveCombinators.multirec(list, SUM_SQUARES_RECIPE)
end

That (and the isomorphic solution where the constant SUM_SQUARES_RECIPE is instead a private helper method #sum_squares_recipe) is nice if you have some reason you wish to re-use the recipe elsewhere. But we don’t, so this merely clutters our class up and separates the method definition from its logic.

I have something in mind. To see what it is, let’s start by transforming our method definition from using the def keyword to using the define_method private class method. This obviously needs a module or class to work:

class Practicum

include RecursiveCombinators

define_method :sum_squares do |list|
multirec(
list,
:divisible? => lambda { |value| value.kind_of?(Enumerable) },
:conquer    => lambda { |value| value ** 2 },
:divide     => lambda { |value| value },
:recombine  => lambda { |list| list.inject() { |x,y| x + y } }
)
end

end

Practicum.new.sum_squares([1, 2, 3, [[4,5], 6], [[[7]]]])

As you probably know, any method taking a block can take a lambda using the & operator, so:

define_method :sum_squares, &(lambda do |list|
multirec(
list,
:divisible? => lambda { |value| value.kind_of?(Enumerable) },
:conquer    => lambda { |value| value ** 2 },
:divide     => lambda { |value| value },
:recombine  => lambda { |list| list.inject() { |x,y| x + y } }
)
end)

This is useful, because now we can express what we want: a lambda taking one argument that in turn calls multirec with the other arguments filled in. Functional programmers call this Partial Application. The idea is that if you have a function or method taking two arguments, if you only give it one argument you get a function back that takes the other. So:

multirec(x).call(y)
=> multirec(x,y)

Now the drawback with this “standard” implementation of partial application is that we would pass a list to multirec and get back a function taking a hash of declarations. That isn’t what we want. We could partially apply things backwards so that multirec(x).call(y) => multirec(y,x) (if Ruby was a concatenative language, we would be concatenating the multirec combinator with a thrush). The trouble with that is it is the reverse of how partial application works in every other programming language and functional programming library.

Instead, we will switch the arguments to multirec ourselves, so it now works like this:

multirec(
{
:divisible? => lambda { |value| value.kind_of?(Enumerable) },
:conquer    => lambda { |value| value ** 2 },
:divide     => lambda { |value| value },
:recombine  => lambda { |list| list.inject() { |x,y| x + y } }
},
list
)

The drawback with this approach is that we lose a little of Ruby’s syntactic sugar, the ability to fake named parameters by passing hash arguments without {} if they are the last parameter. And now, let’s give it the ability to partially apply itself. You can do some stuff with allowing multiple arguments and counting the number of arguments, but we’re going to make the wild assumption that you never attempt a recursive combinator on nil. Here’s multirec, you can infer the implementation for linrec:

def multirec(steps, optional_value = nil)
worker_proc = lambda do |value|
if steps[:divisible?].call(value)
steps[:recombine].call(
steps[:divide].call(value).map { |sub_value| worker_proc.call(sub_v\
alue) }
)
else
steps[:conquer].call(value)
end
end
if optional_value.nil?
worker_proc
else
worker_proc.call(optional_value)
end
end

Notice that you get the same correct result whether you write:

RecursiveCombinators.multirec(
:divisible? => lambda { |value| value.kind_of?(Enumerable) },
:conquer    => lambda { |value| value ** 2 },
:divide     => lambda { |value| value },
:recombine  => lambda { |list| list.inject() { |x,y| x + y } }
).call([1, 2, 3, [[4,5], 6], [[[7]]]])
=> 140

Or:

RecursiveCombinators.multirec(
{
:divisible? => lambda { |value| value.kind_of?(Enumerable) },
:conquer    => lambda { |value| value ** 2 },
:divide     => lambda { |value| value },
:recombine  => lambda { |list| list.inject() { |x,y| x + y } }
},
[1, 2, 3, [[4,5], 6], [[[7]]]]
)
=> 140

Let’s go back to what we were trying to do with &:

define_method :sum_squares, &(lambda do |list|
multirec(
list,
:divisible? => lambda { |value| value.kind_of?(Enumerable) },
:conquer    => lambda { |value| value ** 2 },
:divide     => lambda { |value| value },
:recombine  => lambda { |list| list.inject() { |x,y| x + y } }
)
end)

Now we know how to build our lambda:

require 'partial_application_recursive_combinators'

class Practicum

extend PartialApplicationRecursiveCombinators   # so we can call multirec\
in class scope

define_method :sum_squares, &multirec(
:divisible? => lambda { |value| value.kind_of?(Enumerable) },
:conquer    => lambda { |value| value ** 2 },
:divide     => lambda { |value| value },
:recombine  => lambda { |list| list.inject() { |x,y| x + y } }
)

end

Practicum.new.sum_squares([1, 2, 3, [[4,5], 6], [[[7]]]])
=> 140

You can verify for yourself that no matter how many times you call sum_squares, you do not build those lambdas again. What we have just done is added partial application to multirec and linrec, which in turn allows us to ensure that he cost of constructing lambdas for our methods is only done when the method is defined, not every time it is called.

8.6 Building on a legacy

We have already renamed divide_and_conquer and linear_recursion to bring them into line with standard practice and other programming languages. Now it’s time for us to bring the parameters–the declarative lambdas–into line with standard practice.

The four arguments to both methods are normally called cond, then, before, and after:

• cond is the logical inverse of divisible? So if cond(value) evaluates to true, then we do not need to subdivide the problem.
• then is exactly the same as conquer, if cond then then. That’s the way I think of it.
• before is the same as divide.
• after is the same as recombine.

Things look very similar with the new scheme for now:

require 'legacy_recursive_combinators'

class Practicum

extend LegacyRecursiveCombinators   # so we can call multirec in class sc\
ope

define_method :sum_squares, &multirec(
:cond   => lambda { |value| value.kind_of?(Numeric) }, # the only change\
right now
:then   => lambda { |value| value ** 2 },
:before => lambda { |value| value },
:after  => lambda { |list| list.inject() { |x,y| x + y } }
)

end

All right, now our combinators will look familiar to functional programmers, and even better when we look at functional programs using recursive combinators we will understand them at a glance. Okay, let’s get serious and work on making our combinators easy to use and our code easy to read.

8.7 Seriously

As long as you’re writing these lambdas out, writing :cond => isn’t a hardship. And in an explanatory article like this, it can help at first. However, what if you find a way to abbreviate things? For example, you might alias lambda to L. Or you might want to use string\_to\_proc:

string_to_proc.rb

class String
unless ''.respond_to?(:to_proc)
def to_proc &block
params = []
expr = self
sections = expr.split(/\s*->\s*/m)
if sections.length > 1 then
eval sections.reverse!.inject { |e, p| "(Proc.new { |#{p.split(/\\
s/).join(', ')}| #{e} })" }, block && block.binding
elsif expr.match(/\b_\b/)
eval "Proc.new { |_| #{expr} }", block && block.binding
else
leftSection = expr.match(/^\s*(?:[+*\/%&|\^\.=<>\[]|!=)/m)
rightSection = expr.match(/[+\-*\/%&|\^\.=<>!]\s*\$/m)
if leftSection || rightSection then
if (leftSection) then
params.push('\$left')
expr = '\$left' + expr
end
if (rightSection) then
params.push('\$right')
expr = expr + '\$right'
end
else
self.gsub(
/(?:\b[A-Z]|\.[a-zA-Z_\$])[a-zA-Z_\$\d]*|[a-zA-Z_\$][a-zA-Z_\
\$\d]*:|self|arguments|'(?:[^'\\]|\\.)*'|"(?:[^"\\]|\\.)*"/, ''
).scan(
/([a-z_\$][a-z_\$\d]*)/i
) do |v|
params.push(v) unless params.include?(v)
end
end
eval "Proc.new { |#{params.join(', ')}| #{expr} }", block && bloc\
k.binding
end
end
end
end

So we should support passing the declarative arguments by position as well as by ‘name.’ And with a final twist, if any of the declarative arguments aren’t already lambdas, we’ll try to create lambdas by sending them the message to_proc. So our goal is to write what we wrote above or either of the following and have it “just work:”

define_method :sum_squares, &multirec(
lambda { |value| value.kind_of?(Numeric) }, # the only change right now
lambda { |value| value ** 2 },
lambda { |value| value },
lambda { |list| list.inject() { |x,y| x + y } }
)

include 'string-to_proc'

define_method :sum_squares, &multirec("value.kind_of?(Numeric)", "value ** \
2","value","value.inject(&'+')")

And here is the code that makes it work:

recursive_combinators.rb

module RecursiveCombinators

separate_args = lambda do |args|
if ![1,2,4,5].include?(args.length)
raise ArgumentError
elsif args.length <= 2
steps = [:cond, :then, :before, :after].map { |k| args.first[k].to_pr\
oc }
steps.push(args[1]) unless args[1].nil?
steps
else
steps = args[0..3].map { |arg| arg.to_proc }
steps.push(args[4]) unless args[4].nil?
steps
end
end

define_method :multirec do |*args|
cond_proc, then_proc, before_proc, after_proc, optional_value = separat\
e_args.call(args)
worker_proc = lambda do |value|
if cond_proc.call(value)
then_proc.call(value)
else
after_proc.call(
before_proc.call(value).map { |sub_value| worker_proc.call(sub_va\
lue) }
)
end
end
if optional_value.nil?
worker_proc
else
worker_proc.call(optional_value)
end
end

define_method :linrec do |*args|
cond_proc, then_proc, before_proc, after_proc, optional_value = separat\
e_args.call(args)
worker_proc = lambda do |value|
trivial_parts, sub_problem = [], value
while !cond_proc.call(sub_problem)
trivial_part, sub_problem = before_proc.call(sub_problem)
trivial_parts.unshift(trivial_part)
end
trivial_parts.unshift(then_proc.call(sub_problem))
trivial_parts.inject do |recombined, trivial_part|
after_proc.call(trivial_part, recombined)
end
end
if optional_value.nil?
worker_proc
else
worker_proc.call(optional_value)
end
end

module_function :multirec, :linrec

end

Now when we have trivial lambdas, we can use nice syntactic sugar to express them. string_to_proc is not part of our recursive combinators, but making recursive combinators flexible, we make it “play well with others,” which is a win for our code.

8.8 Separating Implementation from Declaration

In Refactoring Methods with Recursive Combinators, we read the claim that by separating the recursion implementation from the declaration of how to perform the steps of an algorithm like #rotate, we leave ourselves the opportunity to improve the performance of our implementation without the risk of adding bugs to our declaration.

In other words, we can optimize linrec if we want to. Well, we want to. So what we’re going to do is optimize its performance by trading time for space. Let’s have a quick look at the worker_proc lambda inside of linrec:

worker_proc = lambda do |value|
if cond_proc.call(value)
then_proc.call(value)
else
trivial_part, sub_problem = before_proc.call(value)
after_proc.call(
trivial_part, worker_proc.call(sub_problem)
)
end
end

As you can see, it is recursive, it calls itself to solve each sub-problem. And here is an iterative replacement:

worker_proc = lambda do |value|
trivial_parts, sub_problem = [], value
while !cond_proc.call(sub_problem)
trivial_part, sub_problem = before_proc.call(sub_problem)
trivial_parts.unshift(trivial_part)
end
trivial_parts.unshift(then_proc.call(sub_problem))
trivial_parts.inject do |recombined, trivial_part|
after_proc.call