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