| ||||||||||

This interesting blog page "Refactoring Methods with Recursive Combinators" shows Ruby implementations of a recursive combinator: http://github.com/raganwald/homoico I like the idea of putting a blog in a version control, I just hope the usability will improve a little more for blog readers (removing some noise from the page). Here you can find my Python and D versions: http://www.fantascienza.net/leonardThe translation to Python was painless and not too much difficult, so Python is up to the task: def divide_and_conquer(value, isdivisible, conquer, divide, recombine): if isdivisible(value): return recombine(divide_and_conquer(sub_value, isdivisible, conquer, divide, recombine) for sub_value in divide(value)) else: return conquer(value) identity = lambda x: x def rotate2(square): def divide(square): half_len = len(square) // 2 def sub_square(nrow, ncol): return [row[ncol: ncol + half_len] for row in square[nrow: nrow + half_len]] upper_left = sub_square(0, 0) lower_left = sub_square(half_len, 0) upper_right = sub_square(0, half_len) lower_right = sub_square(half_len, half_len) return [upper_left, lower_left, upper_right, lower_right] def recombine((upper_left, lower_left, upper_right, lower_right)): return [l + r for l,r in zip(upper_right, lower_right)] + \ [l + r for l,r in zip(upper_left, lower_left)] return divide_and_conquer(square, isdivisible=lambda value: len(value) > 1, conquer= identity, divide= divide, recombine= recombine)I think this Python code is also a little more readable than the original Ruby one (and probably faster too). This code is a cute exercise, but it's less readable than the original version (that doesn't use a combinator), longer, more difficult to debug and modify, and slower. And using multiple threads doesn't help much in normal Python code. Then I have tried to translate the code to the D language, that is a statically typed language that is more flexible than the usual C++ or C, but not as flexible for example as Scala or Haskell. First of all I have translated the original functions (function templates), it's doable, and the result looks even nice enough, especially if you use my dlibs: BaseType!(TyIter) sum_squares3(TyIter)(TyIter value) { static if (IsIterable!(TyIter)) { BaseType1!(TyIter) x; return sum(select(sum_squares3(x), x, value)); } else return value * value; } T[][] rotate1(T)(T[][] square) { if (len(square) > 1) { int half_len = len(square) / 2; T[][] sub_square(int nrow, int ncol) { T[] row; return select(row[ncol.. ncol + half_len], row, square[nrow.. nrow + half_len]); } auto upper_left = rotate1(sub_square(0, 0)); auto lower_left = rotate1(sub_square(half_len, 0)); auto upper_right = rotate1(sub_square(0, half_len)); auto lower_right = rotate1(sub_square(half_len, half_len)); T[][] lr; return select(lr[0] ~ lr[1], lr, azip(upper_right, lower_right)) ~ select(lr[0] ~ lr[1], lr, azip(upper_left, lower_left)); } else return square; }Note that static if (IsIterable!(TyIter)), it's necessary because as the sum_squares3 drills down, the type of value changes. So you need a static if to manage the change in a static language like D. Note that the D version sum_squares3() isn't as flexible as the Python version. In normal D you can't define an array with mixed elements: [iter([1, {2:0, 3:0}]), [set([4, 5]), 6], [[[7]]]] Or even an array with a mixed number of levels: [1, 2, 3, [[4, 5], 6], [[[7]]]] You are allowed to use a fixed number or levels, with subarrays of different length: [[1, 2], [3], [4, 5], [6], [7]] Then I have tried to translate the multirec combinator itself. But I think here the static type system of D shows the limits of its flexibility. The translation was a pain. This a result: ReturnType!({ return F2.init(Init!(T)().init); }) divide_and_conquer(T, F1, F2, F3, F4) (T value, F1 isdivisible, F2 conquer, F3 divide, F4 recombine) { if (isdivisible(value)) { T[] aux; foreach (sub_value; divide(value)) aux ~= divide_and_conquer(sub_value, isdivisible, conquer, divide, recombine); return recombine(aux); } else return conquer(value); } struct _identity { static T opCall(T)(T x) { return x; } } _identity identity; T[][] rotate2(T)(T[][] square) { T[][][] divide(T[][] square) { int half_len = len(square) / 2; T[][] sub_square(int nrow, int ncol) { T[] row; return select(row[ncol ..ncol + half_len], row, square[nrow .. nrow + half_len]); } auto upper_left = sub_square(0, 0); auto lower_left = sub_square(half_len, 0); auto upper_right = sub_square(0, half_len); auto lower_right = sub_square(half_len, half_len); return [upper_left, lower_left, upper_right, lower_right][]; } T[][] recombine(T[][][] parts) { auto upper_left = parts[0]; auto lower_left = parts[1]; auto upper_right = parts[2]; auto lower_right = parts[3]; T[][] lr; return select(lr[0] ~ lr[1], lr, azip(upper_right, lower_right)) ~ select(lr[0] ~ lr[1], lr, azip(upper_left, lower_left)); } return divide_and_conquer(square, (T[][] square){return len(square) > 1;}, identity, ÷, &recombine); }Note the complex return type, that infers the type from a little function built on the fly: ReturnType!({ return F2.init(Init!(T)().init); }) In D V.2 you can just replace that with "auto", simplifying the code, using type inference on the return type. Init!(T)().init replaces a T.init, it's a way I have invented to work around a bug of the DMD compiler, that gives a wrong result if T is a static array. divide_and_conquer() in D doesn't currently work for a sum_squares4() function, because it requires isdivisible to be a compile-time template (used as a function, and passed with an alias, to the outer template) to the function template divide_and_conquer(), instead of being passed as delegate (or function pointer) as now. You can call it like this: divide_and_conquer2!(IsItetrable)(seq, sqr, identity, sumb) Where sqr and sumb are something like: struct _sqr { static typeof(T.init * T.init) opCall(T)(T x) { return x * x; } } _sqr sqr; struct _sumb { static typeof(sum(Init!(T)().init)) opCall(T)(T seq) { return sum(seq); } } _sumb sumb;Probably there's a way to make this work, but after some tried I have given up. I think that such working code can be written, but you end with two different versions of divide_and_conquer(), so if you want a single function you probably need a language with a more flexible type system than the current D1 one (I presume Haskell is up to the task). Finally I have tried to adapt the Python code to ShedSkin Python, I have had to pull out nested functions and to replace a generator expression with a list comp. I think that currently you can't write sum_squares4() because there's no way to write that isiterable() function shown in the Python code: def isiterable(value): try: iter(value) except TypeError: return False else: return True(And even once writing such function becomes possible, I don't know if the type system of ShedSkin is able to compile divide_and_conquer() that becomes polimorphic). So currently ShedSkin seems quite less flexible than the D language. | ||||||||||

comments: Leave a comment |