Channels ▼
RSS

Web Development

Component Programming in D


For example, an OutputRange that writes characters to stdout would be:

    struct StdoutByChar {
        void put(char c) {
            if (fputc(c, stdout) == EOF)
		throw new Exception("stdout error");
        }
    }

Recall our earlier:

foreach (c; StdinByChar())
    fputc(c, stdout);

Using an OutputRange, this becomes:

    StdoutByChar r;
    foreach (c; StdinByChar())
	r.put(c);

This is starting to look pretty generic. And something subtle has happened along the way: Our earlier version ignored fputc errors, but the range version doesn't. With exception handling, the errors can be detected in the range code, and it won't "uglify" the algorithm code.

Algorithms

Consider what that last snippet of code does — it copies the data, element by element, from an InputRange and puts it into the OutputRange. Generalizing a bit, and calling it copy:

    void copy(ref StdinByChar source, ref StdoutByChar sink) {
	foreach (c; source)
	    sink.put(c);
    }

This is lovely as long as you've got types StdinByChar and StdoutByChar, but it's back to copy/paste for any other types. Fixing that by making copy a template looks like:

    void copy(Source, Sink)(ref Source source, ref Sink sink) {
	foreach (c; source)
	    sink.put(c);
    }

and copy now will generically take any type, including, of course, types that are not valid InputRanges or OutputRanges. The hapless programmer will see the horrible obscure failure messages coming from the body of copy. This is not so nice. The generic version of copy has the opposite problem from the specific one. Recall that InputRanges and OutputRanges are concepts, not types. The algorithm can be fixed by adding constraints (which are D's idea of concepts):

    Sink copy(Source, Sink)(ref Source source, ref Sink sink)
        if (isInputRange!Source &&
            isOutputRange!(Sink, ElementType!Source))
    {
	foreach (c; source)
	    sink.put(c);
	return sink;
    }

isInputRange is a library template that can determine if its argument is a valid InputRange, and isOutputRange is a library template that determines if its argument is a valid OutputRange that is compatible with the element type of the InputRange. (The sink return was added to help make copy composable.) How is our top level code looking now?

    StdinByChar source;
    StdoutByChar sink;
    copy(source, sink);

Almost there. The syntax does not read left to right. But D has a feature (called Uniform Function Call Syntax, UFCS) that allows func(a,b,c) to be written as a.func(b,c) so now the component copy looks like:

  StdinByChar source;
  StdoutByChar sink;
  source.copy(sink);

Filters

The copy algorithm is a trivial example of a filter. A filter copies some subset of its input to its output. What would a slightly more sophisticated filter look like? How about all the integers less than 3?

    int[] arr = [1,2,3,4,5];
    auto r = arr.filter!(a => a < 3);
    writeln(r);

This code prints: [1, 2]

Note the simple lambda (a => a < 3) as the selection predicate for the filter. As should be apparent, arrays are InputRanges, or more precisely, RandomAccessRanges. One appealing thing about input, forward, bidirectional, and random-access ranges is that they form a hierarchy; the more powerful ranges are refined version of the simpler ones.

Maps and Reducers

Map algorithms read their input, transform it, and return an InputRange that is the transformed result. For example, to square the input:

    int[] arr = [1,2,3,4,5];
    auto r = arr.map!(a => a * a);
    writeln(r);

Which prints: [1, 4, 9, 16, 25].

A reducer algorithm starts with an initial value, and combines that value with the values of all the elements in the range, and produces a single value as a result. For example, to get the sum of the input:

    int[] arr = [1,2,3,4,5];
    auto r = arr.reduce!((a,b) => a + b);
    writeln(r);

Which prints: 15. Note the two-argument lambda.

Just to show how flexible algorithms can be, reduce can also compute multiple values with one pass through the data (which is pretty useful for streaming data and would be expensive to save for a second pass through it). Multiple lambdas produce a tuple result, here the sum and sum of squares is computed:

    int[] arr = [1,2,3,4,5];
    auto r = arr.reduce!((a,b) => a + b, (a,b) => a + b * b);
    writefln("sum = %s, sum of squares = %s", r[0], r[1]);

Which prints: sum = 15, sum of squares = 55

Sorting

Sorting is a broader topic, so let's focusing on the quicksort variety. Unlike the other algorithms discussed so far, quicksort needs its data in memory; and for good performance, it needs random access.

To match the impedance of a streaming input to quicksort, we'd need to accumulate all input in an array. Quicksort being an in-place algorithm, it would modify the array and return a view of that same array that offers extra amenities available to sorted arrays, such as binary search and merge operations.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 
Dr. Dobb's TV