• bearophile (97/97) Jul 16 2010 This computes an array of square numbers, and then for successive proces...

bearophile <bearophileHUGS lycos.com> writes:

This computes an array of square numbers, and then for successive processing I
need both the values and their indexes (here just a writeln):

import std.stdio, std.algorithm, std.conv, std.range, std.string;
void main() {
    auto items = array(map!"a*a"(iota(20)));
    foreach (i, x; items)
        writeln(i, " ", x);
}


If I remove the array() to avoid the up-front computation, this doesn't compile
any more:


import std.stdio, std.algorithm, std.conv, std.range, std.string;
void main() {
    auto items = map!"a*a"(iota(20));
    foreach (i, x; items)
        writeln(i, " ", x);
}


You can't iterate on a map() with an index too, but in my code the index is
useful very often when I use foreach. This is a strong need for me.

A possible solution is modify the foreach, so it can magically syntetize the
index too. If the itereated thing yields more than one thing, then adding the
index becomes hairy, it's a bad solution.

Python prefers a different solution composed of two parts:
- The for loop doesn't magically generate an index, there is a lazy generator
named enumerate(iterable, start=0) that yields the (index, item) pair.
- Tuple unpacking exists, so you can unpack the 2-tuple into index and value:
for i, item in enumerate(items): ...
But you can also keep them in a tuple if you want:
for i_item in enumerate(items): ...

But to implement an enumerate(iterable, start=0) in D I think you need opApply,
and this destroys the range protocol of the iterable that's inside. On the
other hand thinking more about it I think the access to the parts of the range
protocol is useless when foreach is used. So an enumerate that contains opApply
can be used.

A problem is that in Python sometimes this is useful:
list(enumerate(iterable))

This means that Phobos array() has to digest an iterable that defines opApply
too (see bug 4346).

This is a first try:


import std.range: hasLength;
import std.traits: ReturnType;

template isIterable(alias iter) {
    enum bool isIterable = __traits(compiles, { foreach (x; iter) break; });
}

template isReverseIterable(alias iter) {
    enum bool isReverseIterable = __traits(compiles, { foreach_reverse (x;
iter) break; });
}

///
struct Enumerate(T) if (isIterable!(T.init)) {
    T items;
    int start = 0;
    alias ReturnType!(typeof({ foreach(x; items) return x; assert(0); })) Titem;

    static if (hasLength!T) {
         property size_t length() {
            return items.length;
        }
    }

    int opApply(int delegate(ref int, ref Titem) dg) {
        int result;
        foreach (item; this.items) {
            result = dg(start, item);
            if (result)
                break;
            start++;
        }
        return result;
    }

    static if (isReverseIterable!items) {
        int opApplyReverse(int delegate(ref int, ref Titem) dg) {
            int result;
            foreach_reverse (item; this.items) {
                result = dg(start, item);
                if (result)
                    break;
                start++;
            }
            return result;
        }
    }
}


/// ditto
Enumerate!T enumerate(T)(T items, int start=0) if (isIterable!items) {
    return Enumerate!T(items, start);
}

// --------- a little demo ------------------
import std.stdio: write, writeln;
import std.array: array;
import std.algorithm: map;
import std.range: iota;

void main() {
    string[] arr = ["red", "hello", "two"];

    foreach (i, el; enumerate(arr))
        writeln(i, " ", el, " ");
    writeln();

    foreach_reverse (i, el; enumerate(arr, 5))
        writeln(i, " ", el, " ");
    writeln();

    auto m1 = map!"a*a"(iota(10));
    foreach (i, el; enumerate(m1, 1000))
        writeln(i, " ", el, " ");
    writeln();

    writeln(enumerate(arr).length);
    // writeln(map!"a*a"(iota(10)).length); // bug
}


You can't use this enumerate() in all situations, for example if the iterable
contains just one opApply that yields 2 items enumerate() doesn't work. But the
most important case is covered.

Once foreach_reverse is removed, retro() makes things kind of impossible if you
want indexes even in reverse iterations. So this is an important use case for
foreach_reverse that I think retro() can't cover.

Note: if retro(iota(...)) or foreach(;enumerate(...)) is not efficient enough
even after all possible improvements to their simple code, then it's a really
good idea to improve the compiler instead, adding it some heuristic to make it
able to digest better those very common and critical constructs. The compiler
is not an abstract thing set in stone, it must adapt itself a little to the
most critical idioms of the language it has to compile.

Bye,
bearophile