Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 36 ยท Arrays and Ranges

Ranges and Algorithms in D: map, filter, sort and Lazy Pipelines

Learn D's range concept (empty, front, popFront), build lazy pipelines with map, filter, take and iota, use sort, reduce and array, and write your own range.

Ranges are the idea that holds D's standard library together. A range is anything you can look at one element at a time: an array, a file's lines, the numbers from 1 to a million, the output of another range. Algorithms such as map, filter and sort work on any range, and most of them are lazy: they do the work only when you ask for the next element. This lesson explains the three-function range interface, the everyday algorithms, lazy pipelines, and how to write your own range. D code is read-only; the C stand-ins build the same iteration protocol by hand.

The range interface

An input range needs three members:

Member Meaning
empty true when there are no more elements
front The current element (does not advance)
popFront() Move to the next element

foreach over a range is shorthand for:

D
for (; !r.empty; r.popFront())
{
    auto x = r.front;
    // use x
}

An array is already a range: popFront just does a = a[1 .. $], as you saw in Slices in depth. Stronger range kinds add abilities: a forward range can be copied (save) and traversed again, a bidirectional range adds back and popBack, and a random-access range adds indexing and length. Arrays are all of these.

Everyday algorithms

Most of these live in std.algorithm and std.range:

D
import std.stdio;
import std.algorithm : map, filter, sort, reduce, sum, canFind, count, equal;
import std.range : iota, take, enumerate, zip, chain, retro;
import std.array : array;

void main()
{
    auto nums = iota(1, 11);                              // 1..10, lazily
    writeln(nums.filter!(n => n % 2 == 0));               // [2, 4, 6, 8, 10]
    writeln(nums.map!(n => n * n).take(4));               // [1, 4, 9, 16]
    writeln(nums.sum);                                    // 55
    writeln(nums.reduce!((a, b) => a * b));               // 3628800

    int[] data = [5, 2, 9, 1];
    data.sort();                                          // in place: [1, 2, 5, 9]
    writeln(data.retro);                                  // [9, 5, 2, 1]

    foreach (i, v; data.enumerate)
    {
        write(i, ":", v, " ");                            // 0:1 1:2 2:5 3:9
    }
    writeln();

    auto names = ["Ada", "Bob"];
    auto ages = [36, 41];
    foreach (name, age; zip(names, ages))
    {
        writeln(name, " is ", age);
    }
}

The template argument after ! is the function to apply, usually a lambda. filter!(pred) keeps the elements for which the predicate holds; map!(fn) transforms each element; reduce!(fn) folds all elements into one value; take(n) keeps the first n; chain joins ranges end to end; zip walks several ranges together. Printing a lazy range with writeln prints its elements. Call .array (from std.array) when you need a real array to keep.

Laziness

map and filter do not compute anything when you call them. They return a small object that holds the source range and the function. Work happens during iteration, one element at a time:

D
import std.stdio;
import std.algorithm : map, filter;
import std.range : iota;

void main()
{
    auto pipeline = iota(1, 1_000_000_000)
        .map!(n => n * 3)
        .filter!(n => n % 2 == 0)
        .map!(n => n + 1);

    foreach (v; pipeline)
    {
        writeln(v);              // 7, 13, 19, ...
        if (v > 20) break;
    }
}

The loop reads only a handful of elements. A billion-element range costs no memory because no array is ever built; this is why you can chain algorithms freely without worrying about temporary arrays. The same laziness means a range of map results recomputes the function if you traverse it twice, so convert to an array with .array when the function is expensive.

A lazy pipeline

iota Source: 1, 2, 3, ...
filter Keep matching items
map Transform each item
array / sum Finally do the work

Nothing runs until the end of the chain

1 / 2

Writing your own range

Any struct with empty, front and popFront is an input range and works with every algorithm:

D
struct Fibonacci
{
    ulong a = 0, b = 1;
    enum empty = false;                 // infinite
    ulong front() { return a; }
    void popFront()
    {
        auto next = a + b;
        a = b;
        b = next;
    }
}

void main()
{
    import std.range : take;
    import std.stdio : writeln;
    writeln(Fibonacci().take(10));      // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
}

enum empty = false makes the range infinite, and take(10) makes it finite. Because Fibonacci is a struct with value semantics, copying it copies the state.

A stand-in for the range protocol

C C stand-in: empty, front and popFront by hand

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

It prints sum of 1..10 = 55, the same as iota(1, 11).sum in D.

C C stand-in: a lazy map and filter pipeline with function pointers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The first four outputs are 7, 13, 19 and 25. Each element travels through the whole chain before the next one is read, and nothing past the fourth match is ever computed, which is exactly the lazy behavior of the D pipeline.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which three members make an input range?

    empty tests for the end, front reads, popFront advances.
  2. 2. What does map!(n => n * 2) do when called on a range?

    map is lazy; use .array to materialize it.
  3. 3. What does iota(1, 5) produce?

    iota excludes the end value.
  4. 4. How do you turn a lazy range into an array?

    std.array.array allocates an array from any range.

Summary

  • A range is anything with empty, front and popFront; arrays are ranges.
  • map, filter, take, chain, zip and friends compose into lazy pipelines.
  • sort, reduce, sum and array do the real work at the end of a chain.
  • Any struct with the three members is a range and works with all algorithms.

Next: back to the D Programming Language track