This is the homepage of Peter Alexander. I am currently at Facebook working on Core Data. Previously a game developer at Codemasters. Any opinions are my own.
- unique_ptr Type Erasure
- The Condenser Part 1
- Cube Vertex Numbering
- Range-Based Graph Search in D
- Ranges Part 1 - Basics
Ranges Part 1 - Basics
Iteration is one of the most common activities in programming. Few programming tasks can be accomplished without looping or recursing over some set of values, whether it be a stream of bytes from a file, elements of an array, rows in a database, or nodes in an implicitly generated graph. Programs need to iterate, and programming languages need to provide idioms for iteration.
In D, iteration is achieved through the use of ranges. Broadly speaking, a range defines a sequence of values. There are many styles of ranges. For example, some ranges lazily generate their values instead of iterating over data; some ranges are infinite; some ranges can be iterated from both ends; and some ranges allow you to jump around to any index (like arrays). For the most part, the details of how a particular range operates is up to the range implementor.
So how do you implement a range? At the most basic level, a range is just a
type with three member functions:
frontreturns the value from the front of the range.
emptyreturns true if the range has been exhausted.
popFrontremoves the first value from the range.
As a simple example, here is a range that counts from 0 to ‘n’.
Notice that there is no need to inherit from any sort of
There’s nothing magic about ranges, they are just simple types with those
To iterate over a range, you can manually call those functions using a
loop, or use the built-in
foreach loop in D, which knows about ranges.
As expected, this will print out the numbers 0 through 9, one per line. Of
writeln knows about ranges too, so
writeln(Iota(10)) works as
well, and will print out
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], formatted like an
Writing functions that work with ranges is not difficult. Suppose we want to
write a function to count the number of elements in a range. This can be
achieved by accepting the range as a template parameter and iterating the
popFront() explicitly, like so:
By using templates, we can create range types that are templated on other range types. For example, consider a skip range that skips every second element in another range. You could define it like this:
We can then use
Skip in conjunction with
Iota to skip through consecutive
Notice that we have to redundantly specify
Iota as a template parameter to
Skip. This is because D doesn’t currently support type inference for
template type constructors. A common workaround is to create a module-level
function that wraps the constructor:
We can then use these like so:
The above code also makes use of another D feature: uniform function call
syntax, which basically means
f(x) can be written as
x.f() as if
f were a member function of
x. If you come from the C# world, you can
kind of think of it as every free function being an Extension Method.
We could have also written
10.iota().skip() or just plain
There’s no difference, so choose whatever you think is most readable.
The ability to combine arbitrary ranges is perhaps their most powerful feature. There’s no reason we need to stop at combining just two ranges:
It shouldn’t be hard to imagine the kind of flexibility and expressiveness that can be achieved once you have a large vocabulary of ranges at your disposal.
In Part 2 we’ll look at some of the different categories of ranges.