Automatic opApply iteration counter
bearophile
bearophileHUGS at lycos.com
Tue Apr 13 01:59:00 PDT 2010
I have not written this as enhancement request on Bugzilla because while I have a clear (small) problem, I think my possible solution is bad (see at the bottom).
This is how I can use opApply() to create a lazy generator of the first Fibonacci numbers, inside opApply there can be a good amount of code:
import std.stdio: writeln;
struct Xfibonacci {
long max;
this(long inmax) { max = inmax; }
int opApply(int delegate(ref long) dg) {
int result;
long a=0, b=1;
while (a < max) {
result = dg(b);
if (result) break;
a += b;
result = dg(a);
if (result) break;
b += a;
}
return result;
}
}
void main() {
foreach (f; Xfibonacci(200))
writeln(f);
}
But in many situations it's good to have an interation counter too, to index the given item:
foreach (i, f; Xfibonacci(2_000))
To allow both the foreach version with and without index I have to duplicate the body of the opApply, but this code duplication is bad:
import std.stdio: writeln;
struct Xfibonacci {
long max;
this(long inmax) { max = inmax; }
int opApply(int delegate(ref long) dg) {
int result;
long a=0, b=1;
while (a < max) {
result = dg(b);
if (result) break;
a += b;
result = dg(a);
if (result) break;
b += a;
}
return result;
}
int opApply(int delegate(ref int, ref long) dg) {
int result, index;
long a=0, b=1;
while (a < max) {
result = dg(index, b);
if (result) break;
index++;
a += b;
result = dg(index, a);
if (result) break;
b += a;
index++;
}
return result;
}
}
void main() {
foreach (i, f; Xfibonacci(2_000))
writeln(i, " ", f);
}
To avoid the code duplication I can define a generic Enumerate (with its helper function 'enumerate'), very similar to the enumerate() present in Python for the same purpose:
import std.stdio: writeln;
import std.traits: ReturnType;
struct Xfibonacci {
long max;
this(long inmax) { max = inmax; }
int opApply(int delegate(ref long) dg) {
int result;
long a=0, b=1;
while (a < max) {
result = dg(b);
if (result) break;
a += b;
result = dg(a);
if (result) break;
b += a;
}
return result;
}
}
struct Enumerate(Iter) {
Iter iterable;
int index;
alias ReturnType!(typeof({foreach(x; iterable) return x; assert(0); })) ItemType;
int opApply(int delegate(ref int, ref ItemType) dg) {
int result;
foreach (el; iterable) {
result = dg(index, el);
if (result) break;
index++;
}
return result;
}
}
Enumerate!Iter enumerate(Iter)(Iter iterable, int start=0) {
return Enumerate!Iter(iterable, start);
}
void main() {
foreach (i, f; enumerate(Xfibonacci(2_000)))
writeln(i, " ", f);
}
This is not too much bad, but the Fibonacci numbers now come out of two opApply, so the compiler fail in optimizing the code well.
So I propose the automatic generation of the indexed version:
import std.stdio: writeln;
struct Xfibonacci {
long max;
this(long inmax) { max = inmax; }
int opApply(int delegate(ref long) dg) {
int result;
long a=0, b=1;
while (a < max) {
result = dg(b);
if (result) break;
a += b;
result = dg(a);
if (result) break;
b += a;
}
return result;
}
}
void main() {
foreach (f; Xfibonacci(200)) // OK
writeln(f);
foreach (i, f; Xfibonacci(200)) // OK
writeln(f);
}
This can cause problems if Xfibonacci already contains an OpApply that yields two or more items... To me it seems to lead to a messy situation... If you have alternative solutions please tell me.
Bye,
bearophile
More information about the Digitalmars-d
mailing list