Ok, I've mostly been convinced. I browsed through std.range and
couldn't find any case of ranges that were finite and random access, but
where that slicing would be difficult to implement provided that, in the
case of higher order ranges, the base range supports slicing.
The one somewhat difficult case is when you take a finite number of
elements from an infinite range. I assume we don't want to make
infinite ranges support slicing, as this would be kind of silly. For
example, other than an infinite random access range specialization of
Take that simply maintains a lowerLim variable in addition to an
upperLim variable (which is not unreasonable), I don't see any way to
support slicing like:
take(cycle([1,2,3]), 100)[31..41];
In practice it seems like there are three basic types of random access
ranges (as it's difficult to imagine any other cases where you'd have
O(1) access to every element and dense 0..N indexing):
1. Arrays and array-like objects that are implemented as a contiguous
block of memory.
2. Iota, Sequence, Repeat/Replicate, etc., which are based on
evaluation of mathematical functions.
3. Higher order ranges using (1) or (2) as the base range.
In all of these cases supporting slicing is completely feasible. If
we're sure we agree, I'll fold this into the bug fixing/cleanup I've
resumed in std.range.
On 8/13/2010 5:47 PM, Andrei Alexandrescu wrote:
I'm just saying it's reasonable to require ranges to define slicing. I
understand that that may feel some creators of random-access ranges
aggravated, but it's not like we define five random-access ranges a day.
Let's require slicing (I meant to do that for a long time) and move on
to more interesting problems. I just don't feel a slicer wrapper
justifies itself.
Andrei
David Simcha wrote:
But this would lead to boilerplate and inefficiency in cases where
slicing isn't needed. Ranges that don't have a better way of dealing
with slicing would have to have lowerLim and upperLim variables and
add lowerLim every time the range was indexed. While I think the
overhead of this is reasonable if the alternative is an algorithm
simply not working, I don't think it's reasonable to pay for it (both
in execution efficiency and boilerplate code) when it's not going to
be used.
On Fri, Aug 13, 2010 at 2:04 PM, Andrei Alexandrescu
<[email protected] <mailto:[email protected]>> wrote:
I'd favor simplicity by just requiring random-access ranges to
define slicing.
Andrei
David Simcha wrote:
I would agree if we were talking about big-O efficiency, or even
a large constant overhead, but IMHO avoiding Slicer is a
micro-optimization, not a macro-optimization. Therefore, by
default it should "just work" even if it's slightly inefficient
and intervention should be required only if the programmer
decides it needs to be optimized.
On Fri, Aug 13, 2010 at 1:02 PM, Jonathan M Davis
<[email protected] <mailto:[email protected]>
<mailto:[email protected] <mailto:[email protected]>>>
wrote:
On Thursday, August 12, 2010 20:24:03 David Simcha wrote:
> A whole bunch of stuff in Phobos (including
std.range.Radial and
the FFT
> algorithm I just checked in) requires that ranges provided
to it have
> slicing. This limitation is a PITA. Should we add a Slicer
meta-range
> that takes a finite random-access range and bolts slicing
on in the
> obvious but relatively inefficient way if it's not already
supported and
> simply returns the range if it already supports slicing? This
would be
> used under the hood when slicing is required. For example:
>
> struct Slicer(R) if(isRandomAccessRange!R && !hasSlicing!R) {
> R range;
> size_t lowerLim, upperLim;
>
> this(R r) {
> this.range = range;
> this.upperLim = range.length;
> }
>
> // Range primitives: front, popFront, etc.
>
> typeof(this) opSlice(size_t lower, size_t upper) {
> // Error checking
> auto ret = this;
> ret.upperLim -= this.length - upper;
> ret.lowerLim += lower;
> return ret;
> }
> }
>
> auto slicer(R)(R range) {
> static if(hasSlicing!R) {
> return range;
> } else {
> return Slicer!(R)(range);
> }
> }
> _______________________________________________
> phobos mailing list
> [email protected] <mailto:[email protected]>
<mailto:[email protected] <mailto:[email protected]>>
> http://lists.puremagic.com/mailman/listinfo/phobos
I'm not sure I like the idea that this would be done without
programmer
intervention. If it's inefficient, it'll lead to programmers
using
range types
with algorithms that really aren't supposed to take those
range
types and
without them realizing the fact that it's inefficient.
Having a
means to allow the
programmer to wrap a range to allow it to be used by an
algorithm
which it
wouldn't normally work with may be a good idea, but each
algorithm
takes certain
types of ranges for a reason, and I'd hate to see much
impact to
efficiency
because of internal range wrangling that the programmer
using the
function isn't
even aware of.
- Jonathan M Davis
_______________________________________________
phobos mailing list
[email protected] <mailto:[email protected]>
<mailto:[email protected] <mailto:[email protected]>>
http://lists.puremagic.com/mailman/listinfo/phobos
------------------------------------------------------------------------
_______________________________________________
phobos mailing list
[email protected] <mailto:[email protected]>
http://lists.puremagic.com/mailman/listinfo/phobos
_______________________________________________
phobos mailing list
[email protected] <mailto:[email protected]>
http://lists.puremagic.com/mailman/listinfo/phobos
------------------------------------------------------------------------
_______________________________________________
phobos mailing list
[email protected]
http://lists.puremagic.com/mailman/listinfo/phobos
_______________________________________________
phobos mailing list
[email protected]
http://lists.puremagic.com/mailman/listinfo/phobos
_______________________________________________
phobos mailing list
[email protected]
http://lists.puremagic.com/mailman/listinfo/phobos
