Parametric Polymorphism and The D Programming Language

Solving Generic Problems in Python

(And in other dynamically-typed languages)

• Throw away types
• Rely on duck typing and tests

# Create a one-to-many mapping from a sequence of pairs.
def to_many(sequence_of_pairs):
    mapping = {}

    for left, right in sequence_of_pairs:
        mapping.setdefault(left, []).append(right)

    return mapping

to_many([(1, 2), (1, 3)]) == {1: [2, 3]}                    # lists

to_many(((1, 2), (1, 3))) == {1: [2, 3]}                    # tuples

to_many(OrderedDict(((1, 2), (1, 3))).items()) == {1: [3]}  # OrderedDict?

to_many("garbage")                                          # Uh oh...

to_many(42)                                                 # Help!

Why Type Parameters?

You need to apply algorithms over a range of type to save yourself from going mad.

// Sum a sequence of numbers.
int sum(int* pointer, size_t length) {
int total = 0;

for(size_t index = 0; index < length; index++) {
    total += pointer[index];
}

return total;
}

What about summing floats?

You have to write it again!

// Sum a sequence of floating point numbers.
float sum_float(float* pointer, size_t length) {
float total = 0;

for(size_t index = 0; index < length; index++) {
    total += pointer[index];
}

return total;
}

What about summing double-precision floats?

Write it again! ... and again.

// Sum a sequence of double-precision floating point numbers.
double sum_double(double* pointer, size_t length) {
double total = 0;

for(size_t index = 0; index < length; index++) {
    total += pointer[index];
}

return total;
}

Are you bored yet?

Add Type Parameters

Let's take the code from before, but let's make the number type itself a parameter of the function.

// Sum a sequence of numbers.
template<typename Number> Number sum(Number* pointer, size_t length) {
    Number total = 0;

    for(size_t index = 0; index < length; index++) {
        total += pointer[index];
    }

    return total;
}

Now it works for all numbers!

int int_array[3] = {1, 2, 3};
float float_array[3] = {1, 2, 3};
double double_array[3] = {1, 2, 3};
long long_array[3] = {1, 2, 3};

sum<int>(int_array, 3) == 6
sum<float>(float_array, 3) == 6.0f
// C++ can infer the type parameters, so we don't need to type them.
sum(double_array, 3) == 6.0
sum(long_array, 3) == 6L

But Aren't "Generics" Enough?

The short answer is "no," the long answer involves shaming Java.

Let's try and write to_many in Java...

Let's define a Pair first.

public class Example {
    public static class Pair<T, U> {
        final public T first;
        final public U second;

        public Pair(T first, U second) {
            this.first = first;
            this.second = second;
        }

        public static <T, U> Pair<T, U> of(T first, U second) {
            return new Pair<T, U>(first, second);
        }
    }
/* ... */

Let's bang out the function.

    static <T, U> HashMap<T, ArrayList<U>>
    toMany(Collection<Pair<T, U>> sequenceOfPairs) {
       HashMap<T, ArrayList<U>> mapping = new HashMap<>();

       for (Pair<T, U> pair: sequenceOfPairs) {
            if (!mapping.containsKey(pair.first)) {
                mapping.put(pair.first, new ArrayList<U>());
            }

            mapping.get(pair.first).add(pair.second);
       }

       return mapping;
    }

    public static void main (String[] argv) {
        HashMap<Integer, List<Integer>> expectedMapping = new HashMap<>();
        expectedMapping.put(1, Arrays.asList(2, 3));

        HashMap<Integer, List<Integer>> actualMapping = toMany(
            Arrays.asList(Pair.of(1, 2), Pair.of(1, 3))
        );

        assert actualMapping.equals(expectedMapping);
    }
}

What about other types? This only works for Collection

Let's Make it More Generic

Let's define a pair, even though we don't have concrete type.

// Write a function template which acts on a pair.
void pairTest(T)(T anything) {
auto first = anything.first;
auto second = anything.second;
}

// Write a value template which returns true
// if such a function will compile for a given type.
enum isPair(T) = __traits(compiles, pairTest!T);

Make the function accept any type which acts like a pair.

auto toMany(Pair)(Pair[] sequenceOfPairs) if(isPair!Pair) {
alias T = typeof(sequenceOfPairs[0].first);
alias U = typeof(sequenceOfPairs[0].second);

U[][T] mapping;

foreach(pair; sequenceOfPairs) {
    mapping[pair.first] ~= pair.second;
}

return mapping;
}

Now the algorithm can be applied to types not yet known.

struct MyNewType(T, U) {
T first; U second;

this(T first, U second) {
    this.first = first;
    this.second = second;
}

MyNewType!(T, U) of(T, U)(T first, U second) {
    return MyNewType!(T, U)(first, second);
}
}

unittest {
assert(toMany([MyNewType.of(1, 2), MyNewType.of(1, 3)]) == [1: [2, 3]]);
}

It doesn't work for Tuple any more though...

auto first(T)(T pair) { return pair[0]; }
auto second(T)(T pair) { return pair[1]; }

unittest {
    auto someTuple = tuple(1, 2);
    // Any f(x) can be rewritten x.f() in D.
    auto first someTuple.first();
    // Or even x.f
    auto second = someTuple.second;
    // It works again!
    assert(toMany([tuple(1, 2), tuple(1, 3)]) == [1: [2, 3]]);
}

Let's Go Even Further, Operate on Any Sequence

import std.range: isInputRange, ElementType;

// Write the algorithm in terms of InputRange!
auto toMany(R)(R sequenceOfPairs)
if(isInputRange!R && IsPair!(ElementType!R)) {
    alias T = typeof(sequenceOfPairs.front[0]);
    alias U = typeof(sequenceOfPairs.front[1]);

    U[][T] mapping;

    foreach(pair; sequenceOfPairs) {
        mapping[pair[0]] ~= pair[1];
    }

    return mapping;
}

What are Ranges?

Ranges are categories of types which represent "ranges" of elements.

An InputRange is anything which acts like this:

T someRange;

// Check if the range is empty.
while(!someRange.empty) {
    // Get the current value.
    auto someElement = someRange.front;

    // Advance to the next value.
    someRange.popFront();
}

std.range Predicates

Worth mentioning: hasLength, hasSlicing, isInfinite.

Example Applications of Ranges

Implementing sort -u.

#!/usr/bin/env rdmd
import std.stdio;
import std.array;
import std.algorithm;

void main() {
    stdin.byLineCopy(KeepTerminator.yes) // InputRange from stdin
    .array                               // Collect all lines in an array
    .sort                                // New InputRange, sorted items
    .uniq                                // New InputRange, skipping duplicates
    .copy(stdout.lockingTextWriter());   // Write to a stdout OutputRange.
}

FizzBuzz!

import std.range: iota;
import std.algorithm: map, each;
import std.conv: to;
import std.stdio: writeln;

void main() {
    iota(1, 101)
    .map!(
        number =>
            number % 3 == 0 && number % 5 == 0 ? "FizzBuzz" :
            number % 3 == 0 ? "Fizz" :
            number % 5 == 0 ? "Buzz" :
            number.to!string
    )
    .each!writeln;
}

Print the first 50 Fibonacci numbers.

#!/usr/bin/env rdmd
import std.range: recurrence, take;
import std.algorithm: each;
import std.stdio: writeln;

void main() {
    recurrence!((a, n) => a[0] + a[1])(1L, 1L)
    .take(50)
    .each!writeln;
}

Printing all ancestor directories.

import std.range;
import std.algorithm;
import std.path;
import std.file;
import std.stdio;

auto iterate(alias func, T)(T initialValue) {
    return recurrence!((values, index) => func(values[0]))(initialValue);
}

void main() {
    getcwd()                                 // get the working directory.
    .iterate!dirName                         // An infinite range of ancestors.
    .until(rootName(getcwd()), OpenRight.no) // Stop when we hit /, C:\, etc.
    .each!writeln;                           // Print everything to stdout.
}