I am trying to use a sequence range as a sorted range so that I can apply a search on it. For instance this might be used to implement integer square root as so:
auto square(N)(N n) {
return n * n;
}
auto isqrt(int n) {
import std.range: sequence, assumeSorted;
auto seq = sequence!((a, n) => square(n));
auto seqAsSorted = seq.assumeSorted!((a, b) => a <= b); // fails to compile
auto lowerBounds = seqAsSorted.lowerBound(n);
auto ret = lowerBounds.length;
return ret;
}
The assumeSorted line which creates a SortedRange fails to compile (dmd v2.100.1)
I get the following error instead:
/usr/local/opt/dmd/include/dlang/dmd/std/range/package.d(10896): Error: generated function `repro_range_sorted.isqrt.Sequence!(__lambda2, Tuple!()).Sequence.opAssign(Sequence!(__lambda2, Tuple!()) p)` is not callable using argument types `(Take!(Sequence!(__lambda2, Tuple!())))`
/usr/local/opt/dmd/include/dlang/dmd/std/range/package.d(10896): cannot pass argument `this._input.opSlice(a, b)` of type `Take!(Sequence!(__lambda2, Tuple!()))` to parameter `Sequence!(__lambda2, Tuple!()) p`
/usr/local/opt/dmd/include/dlang/dmd/std/range/package.d(11478): Error: template instance `repro_range_sorted.isqrt.SortedRange!(Sequence!(__lambda2, Tuple!()), __lambda4, SortedRangeOptions.assumeSorted)` error instantiating
/<truncated>/src/repro_range_sorted.d(22): instantiated from here: `assumeSorted!((a, b) => a <= b, Sequence!(__lambda2, Tuple!()))`
Failed: ["/usr/local/Cellar/dmd/2.100.1/bin/dmd", "-v", "-o-", "/<truncated>/src/repro_range_sorted.d", "-I/<truncated>/src"]
From trying to understand the error, it seems that opSlice
for Sequence
is implemented via a Take
which means that it returns a range of a different type than the object on which opSlice
was called (Sequence
). The implementation of SortedRange
assumes that the type of the wrapped range is static, hence in its own implementation of opSlice
it assigns the result of calling opSlice
on the wrapped range to the variable of the original, fixed, type (here Sequence
).
Questions:
Would this use of SortedRange
/Sequence
be considered conventional and something to be supported? How would you write the above code differently, in a range-like manner if not? My motivation in using Sequence
is constant memory. For comparison here is a variant that using an array range:
auto isqrt2(int n) {
import std.algorithm: map;
import std.range: array, iota, sequence, assumeSorted;
auto seq = iota(1, n + 1).map!(square).array;
auto seqAsSorted = seq.assumeSorted!((a, b) => a <= b);
auto lowerBounds = seqAsSorted.lowerBound(n);
auto ret = lowerBounds.length;
return ret;
}
It is a bit surprising that opSlice
returns an object of a different type, is this something that was designed? Are there other instances in the standard library where a range-returning method gives a different type than the type on which the method is implemented (i.e. method defined in a Range class / struct, not standalone methods like map
and co. available within std.algorithm
)?
It would seem from the SortedRange
example that the assumption is that methods returning a range object return an object of the same type. Is there a way to check where else this assumption is made?