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++.