Pure higher order functions

[bearophile]

I think D eventually needs to allow the creation of pure higher order functions, like map, filter, amap (that means array(map(...))).


DMD 2.054beta improves the situation with the automatic inference for pure and nothrow.

(By the way, the changelog says "Add warning about calling pure nothrow functions and ignoring the result", but this was reverted).

Currently this code doesn't compile, but I expect it to eventually compile if D wants to be a bit functional:


import std.range, std.algorithm;

int sqr(int x) pure nothrow { return x * x; }

pure int foo(int n) {
    int total;
    foreach (x; map!sqr([1, 2, 3, 4]))
        total += 1;
    return total;
}

void main() {
    int x = foo(10);
}


It gives the errors:

test.d(8): Error: pure function 'foo' cannot call impure function 'map'
test.d(8): Error: pure function 'foo' cannot call impure function 'empty'
test.d(8): Error: pure function 'foo' cannot call impure function 'popFront'
test.d(8): Error: pure function 'foo' cannot call impure function 'front'

(Note how the error messages don't tell me in what module those 'map', 'empty', 'popFront' and 'front' are. I think this is worth an enhancement request.)

To see the situation better I have created a simpler version without Phobos imports (no @safe to keep things simpler):



@property bool empty(T)(in T[] a) pure nothrow {
    return !a.length;
}

@property ref T front(T)(T[] a) pure nothrow {
    assert(a.length);
    return a[0];
}

void popFront(A)(ref A a) pure nothrow {
    assert(a.length);
    a = a[1 .. $];
}

pure struct Map(alias fun, R) {
    R _input;

    this(R input) nothrow {
        _input = input;
    }

    @property bool empty() nothrow const {
        return _input.empty;
    }

    @property auto ref front() nothrow const {
        return fun(_input.front);
    }

    void popFront() nothrow {
        _input.popFront();
    }
}

template map(alias fun) {
    auto map(R)(R range) {
        return Map!(fun, R)(range);
    }
}

int sqr(int x) pure nothrow { return x * x; }

pure nothrow int foo(int n) {
    int total;
    foreach (x; map!(sqr)([1, 2, 3, 4]))
        total += x;
    return total;
}

void main() {
    assert(foo(10) == 30);
}


"pure struct" does nothing, this is bad.

If I remove the "pure" from foo, it compiles and works, even if I compile with -property.

If I add a "pure" to Map.empty it doesn't compile, with the error:
test.d(23): Error: pure nested function 'empty' cannot access mutable data '_input'

How do I create a pure higher order function?

Bye,
bearophile