Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 408 lines (317 sloc) 21.298 kb
5b0bc8d title change in the latest post
Reg Braithwaite authored
1 Refactoring Methods with Recursive Combinators
4117f7e recursive combinators post
Reg Braithwaite authored
2 ===
3
94aa33b Reg Braithwaite Updated links, especially to combinators
raganwald authored
4 In previous commits, we have met some of [Combinatory Logic](http://en.wikipedia.org/wiki/Combinatory_logic)'s most interesting combinators like the [Kestrel](http://github.com/raganwald/homoiconic/tree/master/2008-10-29/kestrel.markdown#readme), [Thrush](http://github.com/raganwald/homoiconic/tree/master/2008-10-30/thrush.markdown#readme), [Cardinal](http://github.com/raganwald/homoiconic/tree/master/2008-10-31/songs_of_the_cardinal.markdown "Songs of the Cardinal"), [Quirky Bird](http://github.com/raganwald/homoiconic/tree/master/2008-11-04/quirky_birds_and_meta_syntactic_programming.markdown "Quirky Birds and Meta-Syntactic Programming"), and [Bluebird](http://github.com/raganwald/homoiconic/tree/master/2008-11-07/from_birds_that_compose_to_method_advice.markdown "Aspect-Oriented Programming in Ruby using Combinator Birds"). 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.
0469080 put the introduction back
Reg Braithwaite authored
5
94aa33b Reg Braithwaite Updated links, especially to combinators
raganwald authored
6 > As explained in [Kestrels](http://github.com/raganwald/homoiconic/tree/master/2008-10-29/kestrel.markdown#readme), the practice of nicknaming combinators after birds was established in Raymond Smullyan's amazing book [To Mock a Mockingbird](http://www.amazon.com/gp/product/0192801422?ie=UTF8&tag=raganwald001-20&linkCode=as2&camp=1789&creative=9325&creativeASIN=0192801422). In this book, Smullyan explains combinatory logic and derives a number of important results by presenting the various combinators as songbirds in a forest. Since the publication of the book more than twenty years ago, the names he gave the birds have become standard nicknames for the various combinators.
0469080 put the introduction back
Reg Braithwaite authored
7
8 Consider the method `#sum_squares`: It sums the squares of a tree of numbers, represented as a nested list.
4117f7e recursive combinators post
Reg Braithwaite authored
9
10 def sum_squares(value)
11 if value.kind_of?(Enumerable)
12 value.map do |sub_value|
13 sum_squares(sub_value)
14 end.inject() { |x,y| x + y }
15 else
16 value ** 2
17 end
18 end
19
20 p sum_squares([1, 2, 3, [[4,5], 6], [[[7]]]])
21 => 140
22
23 And the method `#rotate`: It rotates a square matrix, provided the length of each side is a power of two:
24
25 def rotate(square)
26 if square.kind_of?(Enumerable) && square.size > 1
27 half_sz = square.size / 2
28 sub_square = lambda do |row, col|
29 square.slice(row, half_sz).map { |a_row| a_row.slice(col, half_sz) }
30 end
31 upper_left = rotate(sub_square.call(0,0))
32 lower_left = rotate(sub_square.call(half_sz,0))
33 upper_right = rotate(sub_square.call(0,half_sz))
34 lower_right = rotate(sub_square.call(half_sz,half_sz))
35 upper_right.zip(lower_right).map { |l,r| l + r } +
36 upper_left.zip(lower_left).map { |l,r| l + r }
37 else
38 square
39 end
40 end
41
42 p rotate([[1,2,3,4], [5,6,7,8], [9,10,11,12], [13,14,15,16]])
43 => [[4, 8, 12, 16], [3, 7, 11, 15], [2, 6, 10, 14], [1, 5, 9, 13]]
44
45 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?
46
47 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.
48
49 Divide and Conquer
50 ---
51
0469080 put the introduction back
Reg Braithwaite authored
52 Both of these methods use the [Divide and Conquer](http://www.cs.berkeley.edu/~vazirani/algorithms/chap2.pdf) strategy.
53
54 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.
4117f7e recursive combinators post
Reg Braithwaite authored
55
56 For example, here's how `#rotate` rotated the square. We started with a square matrix of size 4:
57
58 [
59 [ 1, 2, 3, 4],
60 [ 5, 6, 7, 8],
61 [ 9, 10, 11, 12],
62 [ 13, 14, 15, 16]
63 ]
64
65 That cannot be rotated trivially, so we divided it into four smaller sub-squares:
66
67 [ [
68 [ 1, 2], [ 3, 4],
69 [ 5, 6] [ 7, 8]
70 ] ]
71
72 [ [
73 [ 9, 10], [ 11, 12],
74 [ 13, 14] [ 15, 16]
75 ] ]
76
77 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.
78
79 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:
80
81 [ [
82 [ 2, 6], [ 4, 8],
83 [ 1, 5] [ 3, 7]
84 ] ]
85
86 [ [
87 [ 10, 14], [ 12, 16],
88 [ 9, 13] [ 11, 15]
89 ] ]
90
91 Then those four squares were recombined into the final result like this:
92
93 [ [
94 [ 4, 8], [ 12, 16],
95 [ 3, 7] [ 11, 15]
96 ] ]
97
98 [ [
99 [ 2, 6], [ 10, 14],
100 [ 1, 5] [ 9, 13]
101 ]
102
103 And smooshed (that is the technical term) back together:
104
105 [
106 [ 4, 8, 12, 16],
107 [ 3, 7, 11, 15],
108 [ 2, 6, 10, 14],
109 [ 1, 5, 9, 13]
110 ]
111
112 And Voila! There is your rotated square matrix.
113
221bc11 fixed a link and formatted a list
Reg Braithwaite authored
114 Both rotation and summing the squares of a tree combine the four steps of a divide and conquer strategy:
115
116 1. Deciding whether the problem is divisible into smaller pieces or can be solved trivially,
117 1. A solution fro the trivial case,
118 1. A way to divide a non-trivial problem up,
119 1. And a way to piece it back together.
4117f7e recursive combinators post
Reg Braithwaite authored
120
121 Here are the two methods re-written to highlight the common strategy. First, `#sum_squares_2`:
122
123 public
124
125 def sum_squares_2(value)
126 if sum_squares_divisible?(value)
127 sum_squares_recombine(
128 sum_squares_divide(value).map { |sub_value| sum_squares_2(sub_value) }
129 )
130 else
131 sum_squares_conquer(value)
132 end
133 end
134
135 private
136
137 def sum_squares_divisible?(value)
138 value.kind_of?(Enumerable)
139 end
140
141 def sum_squares_conquer(value)
142 value ** 2
143 end
144
145 def sum_squares_divide(value)
146 value
147 end
148
149 def sum_squares_recombine(values)
150 values.inject() { |x,y| x + y }
151 end
152
153 And `#rotate_2`:
154
155 public
156
157 def rotate_2(value)
158 if rotate_divisible?(value)
159 rotate_recombine(
160 rotate_divide(value).map { |sub_value| rotate_2(sub_value) }
161 )
162 else
163 rotate_conquer(value)
164 end
165 end
166
167 private
168
169 def rotate_divisible?(value)
170 value.kind_of?(Enumerable) && value.size > 1
171 end
172
173 def rotate_conquer(value)
174 value
175 end
176
177 def rotate_divide(value)
178 half_sz = value.size / 2
179 sub_square = lambda do |row, col|
180 value.slice(row, half_sz).map { |a_row| a_row.slice(col, half_sz) }
181 end
182 upper_left = sub_square.call(0,0)
183 lower_left = sub_square.call(half_sz,0)
184 upper_right = sub_square.call(0,half_sz)
185 lower_right = sub_square.call(half_sz,half_sz)
186 [upper_left, lower_left, upper_right, lower_right]
187 end
188
189 def rotate_recombine(values)
190 upper_left, lower_left, upper_right, lower_right = values
191 upper_right.zip(lower_right).map { |l,r| l + r } +
192 upper_left.zip(lower_left).map { |l,r| l + r }
193 end
194
195 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:
196
197 public
198
199 def sum_squares_3(list)
200 divide_and_conquer(
201 list,
202 :divisible? => lambda { |value| value.kind_of?(Enumerable) },
203 :conquer => lambda { |value| value ** 2 },
204 :divide => lambda { |value| value },
205 :recombine => lambda { |list| list.inject() { |x,y| x + y } }
206 )
207 end
208
209 def rotate_3(square)
210 divide_and_conquer(
211 square,
212 :divisible? => lambda { |value| value.kind_of?(Enumerable) && value.size > 1 },
213 :conquer => lambda { |value| value },
214 :divide => lambda do |square|
215 half_sz = square.size / 2
216 sub_square = lambda do |row, col|
217 square.slice(row, half_sz).map { |a_row| a_row.slice(col, half_sz) }
218 end
219 upper_left = sub_square.call(0,0)
220 lower_left = sub_square.call(half_sz,0)
221 upper_right = sub_square.call(0,half_sz)
222 lower_right = sub_square.call(half_sz,half_sz)
223 [upper_left, lower_left, upper_right, lower_right]
224 end,
225 :recombine => lambda do |list|
226 upper_left, lower_left, upper_right, lower_right = list
227 upper_right.zip(lower_right).map { |l,r| l + r } +
228 upper_left.zip(lower_left).map { |l,r| l + r }
229 end
230 )
231 end
232
233 private
234
235 def divide_and_conquer(value, steps)
236 if steps[:divisible?].call(value)
237 steps[:recombine].call(
238 steps[:divide].call(value).map { |sub_value| divide_and_conquer(sub_value, steps) }
239 )
240 else
241 steps[:conquer].call(value)
242 end
243 end
244
245 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.
246
3292cde Reg Braithwaite better links on each page
raganwald authored
247 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:
4117f7e recursive combinators post
Reg Braithwaite authored
248
249 var fib0 = function(n){
250 return n <= 1 ? 1 :
251 arguments.callee.call(this, n - 1) +
252 arguments.callee.call(this, n - 2);
253 };
254
255 var fib1 = binrec("<= 1", "1", "[[n - 1], [n - 2]]", "+");
256
257 The Merge Sort
258 ---
259
260 Let's look at another example, implementing a [merge sort](http://en.wikipedia.org/wiki/Merge_sort "Merge sort - Wikipedia, the free encyclopedia"). This algorithm has a distinguished pedigree: It was invented by John Von Neumann in 1945.
261
262 > 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](http://www.amazon.com/gp/product/038541580X?ie=UTF8&amp;tag=raganwald001-20&amp;linkCode=as2&amp;camp=1789&amp;creative=390957&amp;creativeASIN=038541580X "Amazon.com: Prisoner's Dilemma: William Poundstone: Books")![amazon](http://www.assoc-amazon.com/e/ir?t=raganwald001-20&l=as2&o=1&a=038541580X) is a very fine book about both game theory and one of the great minds of modern times.
263
264 Conceptually, a merge sort works as follows:
265
266 * If the list is of length 0 or 1, then it is already sorted.
267 * Otherwise:
268 1. Divide the unsorted list into two sublists of about half the size.
269 1. Sort each sublist recursively by re-applying merge sort.
270 1. Merge the two sublists back into one sorted list.
271
272 The merge sort part will be old hat given our `#divide_and_conquer` helper:
273
274 def merge_sort(list)
275 divide_and_conquer(
276 list,
277 :divisible? => lambda { |list| list.length > 1 },
278 :conquer => lambda { |list| list },
279 :divide => lambda do |list|
280 half_index = (list.length / 2) - 1
281 [ list[0..half_index], list[(half_index + 1)..-1] ]
282 end,
283 :recombine => lambda { |pair| merge_two_sorted_lists(pair.first, pair.last) }
284 )
285 end
286
287 The interesting part is our `#merge_two_sorted_lists` method. Given two sorted lists, our merge algorithm works like this:
288
289 * If either list is of length zero, return the other list.
290 * Otherwise:
291 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.
292 1. 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.
293 1. Merge each pair of lists recursively by applying merge two sorted lists.
294 1. Catenate the results together.
295
296 As you can tell from the description, this is another divide and conquer algorithm:
297
298 def merge_two_sorted_lists(*pair)
299 divide_and_conquer(
300 pair,
301 :divisible? => lambda { |pair| !pair.first.empty? && !pair.last.empty? },
302 :conquer => lambda do |pair|
303 if pair.first.empty? && pair.last.empty?
304 []
305 elsif pair.first.empty?
306 pair.last
307 else
308 pair.first
309 end
310 end,
311 :divide => lambda do |pair|
312 preceding, following = case pair.first.first <=> pair.last.first
313 when -1: [pair.first, pair.last]
314 when 0: [pair.first, pair.last]
315 when 1: [pair.last, pair.first]
316 end
317 [
318 [[preceding.first], []],
319 [preceding[1..-1], following]
320 ]
321 end,
322 :recombine => lambda { |pair| pair.first + pair.last }
323 )
324 end
325
326 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.
327
328 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](http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Recn/Linear/ "Linear Recursion").
329
330 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:
331
332 def merge_two_sorted_lists(*pair)
333 linear_recursion(
334 pair,
335 :divisible? => lambda { |pair| !pair.first.empty? && !pair.last.empty? },
336 :conquer => lambda do |pair|
337 if pair.first.empty? && pair.last.empty?
338 []
339 elsif pair.first.empty?
340 pair.last
341 else
342 pair.first
343 end
344 end,
345 :divide => lambda do |pair|
346 preceding, following = case pair.first.first <=> pair.last.first
347 when -1: [pair.first, pair.last]
348 when 0: [pair.first, pair.last]
349 when 1: [pair.last, pair.first]
350 end
351 [ preceding.first, [preceding[1..-1], following] ]
352 end,
353 :recombine => lambda { |trivial_bit, divisible_bit| [trivial_bit] + divisible_bit }
354 )
355 end
356
357 def linear_recursion(value, steps)
358 if steps[:divisible?].call(value)
359 trivial_part, sub_problem = steps[:divide].call(value)
360 steps[:recombine].call(
361 trivial_part, linear_recursion(sub_problem, steps)
362 )
363 else
364 steps[:conquer].call(value)
365 end
366 end
367
368 You may think this is even better, and it is.
369
370 Separating Declaration from Implementation
371 ---
372
373 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.*
374
375 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...
376
377 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?
378
379 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.
380
381 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.
382
383 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.
384
385 For these reasons, I strongly encourage the use of recursion combinators, either those supplied here or ones you write for yourself.
386
94aa33b Reg Braithwaite Updated links, especially to combinators
raganwald authored
387 **Update**: [Practical Recursive Combinators](http://github.com/raganwald/homoiconic/tree/master/2008-11-26/practical_recursive_combinators.md#readme) explains how to improve these naive implementations. Or you can just grab the [updated source code](http://github.com/raganwald/homoiconic/tree/master/2008-11-26/recursive_combinators.rb "2008-11-26/recursive_combinators.rb") for yourself.
7a164df Reg Braithwaite
raganwald authored
388
4d5e58d added a dissenting opinion link
Reg Braithwaite authored
389 And a [dissenting opinion](http://leonardo-m.livejournal.com/73087.html "leonardo_m: A recursive combinator").
390
4117f7e recursive combinators post
Reg Braithwaite authored
391 ---
392
fe91187 Reg Braithwaite mockingbird links and removing the "NEW!"
raganwald authored
393 _More on combinators_: [Kestrels](http://github.com/raganwald/homoiconic/tree/master/2008-10-29/kestrel.markdown#readme), [The Thrush](http://github.com/raganwald/homoiconic/tree/master/2008-10-30/thrush.markdown#readme), [Songs of the Cardinal](http://github.com/raganwald/homoiconic/tree/master/2008-10-31/songs_of_the_cardinal.markdown#readme), [Quirky Birds and Meta-Syntactic Programming](http://github.com/raganwald/homoiconic/tree/master/2008-11-04/quirky_birds_and_meta_syntactic_programming.markdown#readme), [Aspect-Oriented Programming in Ruby using Combinator Birds](http://github.com/raganwald/homoiconic/tree/master/2008-11-07/from_birds_that_compose_to_method_advice.markdown#readme), [The Enchaining and Obdurate Kestrels](http://github.com/raganwald/homoiconic/tree/master/2008-11-12/the_obdurate_kestrel.md#readme), [Finding Joy in Combinators](http://github.com/raganwald/homoiconic/tree/master/2008-11-16/joy.md#readme), [Refactoring Methods with Recursive Combinators](http://github.com/raganwald/homoiconic/tree/master/2008-11-23/recursive_combinators.md#readme), [Practical Recursive Combinators](http://github.com/raganwald/homoiconic/tree/master/2008-11-26/practical_recursive_combinators.md#readme), [The Hopelessly Egocentric Blog Post](http://github.com/raganwald/homoiconic/tree/master/2009-02-02/hopeless_egocentricity.md#readme), [Wrapping Combinators](http://github.com/raganwald/homoiconic/tree/master/2009-06-29/wrapping_combinators.md#readme), and [Mockingbirds and Simple Recursive Combinators in Ruby](https://github.com/raganwald/homoiconic/blob/master/2011/11/mockingbirds.md#readme).
4117f7e recursive combinators post
Reg Braithwaite authored
394
7d4a695 Reg Braithwaite dasherize the mores
raganwald authored
395 ---
f69ce70 Reg Braithwaite Link to the book
raganwald authored
396
8c4fb37 Reg Braithwaite My recent work
raganwald authored
397 My recent work:
398
f9d4487 Reg Braithwaite allongé
raganwald authored
399 ![](http://i.minus.com/iL337yTdgFj7.png)[![JavaScript Allongé](http://i.minus.com/iW2E1A8M5UWe6.jpeg)](http://leanpub.com/javascript-allonge "JavaScript Allongé")![](http://i.minus.com/iL337yTdgFj7.png)[![CoffeeScript Ristretto](http://i.minus.com/iMmGxzIZkHSLD.jpeg)](http://leanpub.com/coffeescript-ristretto "CoffeeScript Ristretto")![](http://i.minus.com/iL337yTdgFj7.png)[![Kestrels, Quirky Birds, and Hopeless Egocentricity](http://i.minus.com/ibw1f1ARQ4bhi1.jpeg)](http://leanpub.com/combinators "Kestrels, Quirky Birds, and Hopeless Egocentricity")
4479986 Reg Braithwaite More recent work!
raganwald authored
400
f9d4487 Reg Braithwaite allongé
raganwald authored
401 * [JavaScript Allongé](http://leanpub.com/javascript-allonge), [CoffeeScript Ristretto](http://leanpub.com/coffeescript-ristretto), and my [other books](http://leanpub.com/u/raganwald).
21fcc00 Reg Braithwaite redirect to allong.es
raganwald authored
402 * [allong.es](http://allong.es), practical function combinators and decorators for JavaScript.
17be325 Reg Braithwaite revised footers
raganwald authored
403 * [Method Combinators](https://github.com/raganwald/method-combinators), a CoffeeScript/JavaScript library for writing method decorators, simply and easily.
4f7cce6 Reg Braithwaite githiub
raganwald authored
404 * [jQuery Combinators](http://github.com/raganwald/jquery-combinators), what else? A jQuery plugin for writing your own fluent, jQuery-like code.
f69ce70 Reg Braithwaite Link to the book
raganwald authored
405
16fa4bb Reg Braithwaite separated .sig
raganwald authored
406 ---
407
7e71700 Reg Braithwaite updated links
raganwald authored
408 [Reg Braithwaite](http://braythwayt.com) | [@raganwald](http://twitter.com/raganwald)
Something went wrong with that request. Please try again.