digitalmars.D.learn - Using Sequence Range as a SortedRange.
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?
Jul 13 2022
On Wednesday, 13 July 2022 at 18:27:22 UTC, D Lark wrote: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: [...]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);
Jul 13 2022
D Lark <dlark example.com> On Wednesday, 13 July 2022 at 22:35:35 UTC, D Lark wrote:On Wednesday, 13 July 2022 at 18:27:22 UTC, D Lark wrote: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.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: [...]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);
Jul 13 2022