Range indexes

[bearophile]

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