Higher Order Range Pattern

From David Simcha's D-Specific Design Patterns talk at DConf 2013.

Problem: Need to transform a range before passing to a function/object

Want:

• O(1) auxiliary memory usage
• O(1) preprocessing time
• Minimal wasted effort if only part of the range is consumed.

Solution: Process the range lazily

// Simplified version of std.range.Retro
struct Retro(Range)
{
    // These functions can be inlined
    @property
    {
        auto ref front() { return range_.back;  }
        auto ref back()  { return range_.front; }
        bool empty()     { return range_.empty; }
    }

    void popFront() { range_.popBack();  }
    void popBack()  { range_.popFront(); }

    Range range_;
}

// Instantiator function
auto retro(Range)(Range range)
{
    return Retro!Range(range);
}

void main()
{
    import std.algorithm;

    auto arr = [1, 2, 3, 4, 5];
    assert(equal(retro(arr), [5, 4, 3, 2, 1]));
}

The example above is simplified version of std.range.retro that provides a reverse view of a range. You have a range that you iterate through in one order, you pass it to retro and retro makes it look like is has the same elements in the opposite order.

It has a front function that forwards to back which is a simple function that can be inlined by the compiler to have zero overhead.

auto ref makes it simple to forward return types between functions. So when you have an auto ref return type, it returns by ref if and only if it what its returning can be returned by ref, meaning it's an lvalue and not a stack variable.

back forwards to front, popFront pops the back of the range, popBack pops the front of the range, and range_ stores the range.

The instantiate function is done in the opposite way. The return type is specified explicitly in the body and return auto because D allows automatic inference of return types.

An array is created from 1 to 5, it's passed to retro, and the result is verified using std.algorithm.equal which tests element-by-element the equality of ranges, that it's equivalent to 5, 4, 3, 2, 1, the reverse of the original.

Arrays in D are not like arrays in C++; they don't own their own ranges. Arrays in D are fat pointers, meaning a pointer and size, pointing to memory owned by the garbage collector. So when you pass an array around in D by value, you're actually only passing the fat pointer: 16 bytes on a 64-bit architecture and 8 bytes on a 32-bit architecture. You don't need to worry about passing by reference, or worry that the array will go out of scope. The garbage collector makes this a simpler and more transparent way of doing things in D than it would be in C++.

Examples in Phobos

• std.range.retro
• std.range.indexed
• std.range.take
• std.range.stride
• std.range.cycle
• std.range.zip
• std.algorithm.map
• std.range.filter