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/leonard
The 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.