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?

On Wednesday, 13 July 2022 at 18:27:22 UTC, D Lark wrote:

For the first snippet, I did not get to that point, but it appears I would have to add a search policy to lower bound since the list is infinite and the default policy, binary search, requires both initial bounds. i.e:

auto lowerBounds = seqAsSorted.lowerBound!(SearchPolicy.gallop)(n);

On Wednesday, 13 July 2022 at 22:35:35 UTC, D Lark wrote:

auto lowerBounds = seqAsSorted.lowerBound!(SearchPolicy.gallop)(n);

Actually looking at the implementation of lowerBound it seems that search generally is not supported for infinite ranges as irrespective of the overload chosen via the search policy, we still explicitly depend on length which is obviously not defined for infinite ranges.

I guess that leads to the question (probably already covered indirectly in my initial questions):
Is SortedRange intended to be used with infinite ranges?

It would seem that the search policies trot and gallop are theoretically compatible with infinite ranges, but they have been specifically implemented to depend on length.

I note that only the binary search policy overload of getTransitionIndex explicitly requires the existence of a member length which is consistent with my conceptual expectation, but all the overloads actually depend on it in the implementation.