Using Sequence Range as a SortedRange.

D Lark dlark at example.com
Wed Jul 13 18:27:22 UTC 2022


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:

```dlang
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:
```dlang
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?


More information about the Digitalmars-d-learn mailing list