Purity of Phobos reduce

Question

Why isn't std.algorithm.reduce in Phobos pure? Is it an unfixed Issue or is there a reason why it can't be?

Has this something todo with the question: "What does a pure function look like" Andrei asked in the final lecture at DConf 2013?

See: http://forum.dlang.orgthread/[email protected]

I want the function sparseness in the following code to be pure. I guess I could always replace reduce with a foreach loop for now right?

import std.algorithm: reduce, min, max;
import std.typetuple: templateAnd;
import std.traits: isArray, Unqual;
import std.range: ElementType, isInputRange, isBidirectionalRange, isFloatingPoint;

//** Returns: true if $(D a) is set to the default value of its type. */
bool defaulted(T)(T x) @safe pure nothrow { return x == T.init; }
alias defaulted untouched;

/** Returns: Number of Default-Initialized (Zero) Elements in $(D range). */
size_t sparseness(T)(in T x, int recurseDepth = -1) @trusted /* pure nothrow */ {
    import std.traits: isStaticArray;
    static if (isStaticArray!T ||
               isInputRange!T) {
        import std.range: empty;
        immutable isEmpty = x.empty;
        if (isEmpty || recurseDepth == 0) {
            return isEmpty;
        } else {
            const nextDepth = (recurseDepth == -1 ?
                               recurseDepth :
                               recurseDepth - 1);
            static if (isStaticArray!T) { // TODO: We can't algorithms be applied to static arrays?
                typeof(return) ret;
                foreach (ref elt; x) { ret += elt.sparseness(nextDepth); }
                return ret;
            } else {
                import std.algorithm: map, reduce;
                return reduce!"a+b"(x.map!(a => a.sparseness(nextDepth)));
            }
        }
    } else static if (isFloatingPoint!T) {
        return x == 0; // explicit zero because T.init is nan here
    } else {
        return x.defaulted;
    }
}
unittest {
    assert(1.sparseness == 0);
    assert(0.sparseness == 1);
    assert(0.0.sparseness == 1);
    assert(0.1.sparseness == 0);
    assert(0.0f.sparseness == 1);
    assert(0.1f.sparseness == 0);
    assert("".sparseness == 1);
    assert(null.sparseness == 1);
    immutable ubyte[3]    x3   = [1, 2, 3];    assert(x3[].sparseness == 0);
    immutable float[3]    f3   = [1, 2, 3];    assert(f3[].sparseness == 0);
    immutable ubyte[2][2] x22  = [0, 1, 0, 1]; assert(x22[].sparseness == 2);
    immutable ubyte[2][2] x22z = [0, 0, 0, 0]; assert(x22z[].sparseness == 4);
}

Update:

I decided on instead using isIterable and foreach instead of the above, as this works just aswell for me right now and makes things @safe pure nothrow. I see no need right now to use higher order functions to solve this problem. I also found Davids Simchas' upcoming std.rational very natural to use here:

import rational: Rational;

/** Returns: Number of Default-Initialized (Zero) Elements in $(D x) at
    recursion depth $(D depth).
*/
Rational!ulong sparseness(T)(in T x, int depth = -1) @safe pure nothrow {
    alias R = typeof(return); // rational shorthand
    static if (isIterable!T) {
        import std.range: empty;
        immutable isEmpty = x.empty;
        if (isEmpty || depth == 0) {
            return R(isEmpty, 1);
        } else {
            immutable nextDepth = (depth == -1 ? depth : depth - 1);
            ulong nums, denoms;
            foreach (ref elt; x) {
                auto sub = elt.sparseness(nextDepth);
                nums += sub.numerator;
                denoms += sub.denominator;
            }
            return R(nums, denoms);
        }
    } else static if (isFloatingPoint!T) {
        return R(x == 0, 1); // explicit zero because T.init is nan here
    } else {
        return R(x.defaulted, 1);
    }
}

Answer 1

If you change nextDepth to immutable rather than const then sparseness will be pure.

I believe this is a bug, it may be to do with the closure being passed to reduce capturing nextDepth, and for some reason thinking it may be mutable because it is const. Values declared as const are however identical to those declared as immutable -- the difference only manifests itself with indirections -- so I believe it is an error.

You may want to file a minimal repro case as a bug.

(it cannot be nothrow however, because reduce can, in fact, throw)