View mode: basic / threaded / horizontal-split · Log in · Help
October 31, 2012
Re: "isDroppable" range trait for slicing to end
On Wednesday, October 31, 2012 08:13:08 monarch_dodra wrote:
> BTW: Once you are done, maybe you could present here what it
> means exactly to be slice-able? AFAIK, your current proposal
> allows for infinite ranges to verify "hasSlicing", if they can be
> sliced between [a ... b], whereas Dmitry seems to think that
> should not be so. At all.

It works now, but I'm open to removing it, since it _is_ odd to be able to 
slice an infinite range and get a completely different type from out. opSlice 
with opDollar combined with take would give you the same effect:

take(infRange[a .. $], b - a);

But without at least having opSlice with opDollar, you'd be forced to use drop 
or popFrontN, which would be O(n) rather than O(1).

> Well in conclusion, sorry to have brought a crappy solution :/ I
> guess we had something simple all along...

Well, live and learn. It happens to us all from time to time. I'd forgotten 
about opDollar prior to this discussion (mostly because it wasn't working), 
and it's quite applicable to hasSlicing.

- Jonathan M Davis
October 31, 2012
Re: "isDroppable" range trait for slicing to end
10/31/2012 4:48 AM, Jonathan M Davis пишет:
> On Monday, October 29, 2012 15:33:00 monarch_dodra wrote:
>> More often than not, we want to slice a range all the way to the
>> end, and we have to use the clumsy "r[0 .. r.length]" syntax.
>>
>> What's worst is that when a range is infinite, there is no real
>> way to "slice to the end", unless you just repeatedly popFront.
>
> As already pointed out, this is solved by opDollar. We don't have a trait for
> it, but it can be tested for easily enough by doing something like
> typeof(is(r[0 .. $])) or __traits(compiles, r[0 .. $]). We may still want to
> create a trait for it though (e.g. hasOpDollar).
>

I just wanted to point out that we may as well require all RA ranges to 
have opDollar. Finite already have length, infinite would have marker.
Just need some migration path so that current RA won't lose their title 
over night.

[snip]
> Finite ranges which could have n elements popped in O(1) would be sliceable
> anyway, meaning that popFrontN would be O(1) for them already and that if a
> function requires popping n elements in O(1), it can just slice the range. So,
> isDroppable buys us nothing for finite ranges. The only gain that I really see
> here is that it would provide a way for infinite ranges to pop off their first n
> elements and still be infinite. As it stands, the best that you can do is slice
> them, but that has to result in another range type, because a finite slice
> can't be infinite.

Yes, the whole argument started with infinite ranges.

>
> However, if we take advantage of opDollar, then I think we can solve the
> problem that way. By using opDollar when slicing an infinite range, you should
> be able to keep the original range type. That being the case, I don't think
> that isDroppable is really necessary.

I said elsewhere I have feeling that hasSlicing should really check for
x = x[a..b];

Whereas for infinite ranges we need a weaker trait 
isDropable/hasSlicingToEnd(??):

x = [a..$];

> Howevere, it _does_ mean that I should
> probably adjust my pull for hasSlicing so that it tests that slicing an
> infinite range with opDollar returns the original type (assuming that opDollar
> compiles for it). Of course, once opDollar works (I don't know what it's
> current state is), it would be desirable to require it to work with slicing
> anyway, so maybe hasSlicing should have that requirement added at a later
> date.

Indeed, alternatively we can check for both hasSlicing and isInfinite.
Then in case of Infinite = true slicing only works up to $, this could 
be a better idea.

-- 
Dmitry Olshansky
October 31, 2012
Re: "isDroppable" range trait for slicing to end
On Wednesday, October 31, 2012 12:37:10 Dmitry Olshansky wrote:
> I just wanted to point out that we may as well require all RA ranges to
> have opDollar. Finite already have length, infinite would have marker.
> Just need some migration path so that current RA won't lose their title
> over night.

I agree, but for that to be realistic, I think that issue# 7177 needs to be 
implemented first. You should check out the pull request that I have for 
improving hasSlicing. I just updated it according to some of the discussion 
here, and it now checks the behavior of opDollar when it works with the range 
being sliced. For finite ranges, it essentially enforces that they function 
like arrays do, and for infinite ranges, it comes as close to that as it can:

https://github.com/D-Programming-Language/phobos/pull/854

As of the latest state of that pull request, hasSlicing looks like

template hasSlicing(R)
{
   enum bool hasSlicing = !isNarrowString!R && is(typeof(
   (inout int _dummy=0)
   {
       R r = void;

       static if(isInfinite!R)
           typeof(take(r, 1)) s = r[1 .. 2];
       else
           R s = r[1 .. 2];

       s = r[1 .. 2];

       static if(is(typeof(r[0 .. $])))
       {
           R t = r[0 .. $];
           t = r[0 .. $];

           static if(!isInfinite!R)
           {
               R u = r[0 .. $ - 1];
               u = r[0 .. $ - 1];
           }
       }

       static assert(isForwardRange!(typeof(r[1 .. 2])));
       static assert(hasLength!(typeof(r[1 .. 2])));
   }));
}


- Jonathn M Davis
October 31, 2012
Re: "isDroppable" range trait for slicing to end
On Wednesday, 31 October 2012 at 08:58:18 UTC, Jonathan M Davis 
wrote:
>
> I agree, but for that to be realistic, I think that issue# 7177 
> needs to be
> implemented first. You should check out the pull request that I 
> have for
> improving hasSlicing. I just updated it according to some of 
> the discussion
> here, and it now checks the behavior of opDollar when it works 
> with the range
> being sliced. For finite ranges, it essentially enforces that 
> they function
> like arrays do, and for infinite ranges, it comes as close to 
> that as it can:
>
> https://github.com/D-Programming-Language/phobos/pull/854
>
> As of the latest state of that pull request, hasSlicing looks 
> like
>
> template hasSlicing(R)
> {
>     enum bool hasSlicing = !isNarrowString!R && is(typeof(
>     (inout int _dummy=0)
>     {
>         R r = void;
>
>         static if(isInfinite!R)
>             typeof(take(r, 1)) s = r[1 .. 2];
>         else
>             R s = r[1 .. 2];
>
>         s = r[1 .. 2];
>
>         static if(is(typeof(r[0 .. $])))
>         {
>             R t = r[0 .. $];
>             t = r[0 .. $];
>
>             static if(!isInfinite!R)
>             {
>                 R u = r[0 .. $ - 1];
>                 u = r[0 .. $ - 1];
>             }
>         }
>
>         static assert(isForwardRange!(typeof(r[1 .. 2])));
>         static assert(hasLength!(typeof(r[1 .. 2])));
>     }));
> }
>
>
> - Jonathn M Davis

I'm not a huge fan of the "opDollar" check, because essentially, 
it doesn't really buy you anything: if hasSlicing!R, then is "r = 
r[1..$]" legal? Who knows! You as a developer need to check 
manually that "r[0 .. $]" is legal first anyways...

Under those circumstances, why not cleanly splice the two notions?

//----
template hasSlicing(R)
{
    enum bool hasSlicing = !isNarrowString!R && is(typeof(
    (inout int _dummy=0)
    {
        R r = void;

        static if(isInfinite!R)
            typeof(take(r, 1)) s = r[1 .. 2];
        else
            R s = r[1 .. 2];

        s = r[1 .. 2];

        static assert(isForwardRange!(typeof(r[1 .. 2])));
        static assert(hasLength!(typeof(r[1 .. 2])));
    }));
}

template hasSlicingToEnd(R)
{
    enum bool hasSlicingToEnd = !isNarrowString!R && is(typeof(
    (inout int _dummy=0)
    {
        R r = void;

        static if(is(typeof(r[0 .. $])))
        {
            R t = r[0 .. $];
            t = r[0 .. $];

            static if(!isInfinite!R)
            {
                R u = r[0 .. $ - 1];
                u = r[0 .. $ - 1];
            }
        }
    }));
}
//----

IMO, this makes a clean distinction between both "types" of 
slicing. An added bonus is that (for now) it also correctly 
supports finite RA ranges that don't define opDollar.


//----
PS: Do we really have to force that infinite slice to be of a 
type of "take"? Does that mean we can't imagine an infinite range 
that defines it's own finite slice type?

if we change the code to:

//----
        static if(isInfinite!R)
            auto s = r[1 .. 2]; //HERE1
        else
            R s = r[1 .. 2];

        s = r[1 .. 2]; //HERE2
//----

Then we force nothing on the slice's type (HERE1), but do verify 
that subsequent slices will be assignable back to the original 
slice (HERE2)...
October 31, 2012
Re: "isDroppable" range trait for slicing to end
10/31/2012 10:37 AM, monarch_dodra пишет:
> On Wednesday, 31 October 2012 at 08:58:18 UTC, Jonathan M Davis wrote:
>>
>> I agree, but for that to be realistic, I think that issue# 7177 needs
>> to be
>> implemented first. You should check out the pull request that I have for
>> improving hasSlicing. I just updated it according to some of the
>> discussion
>> here, and it now checks the behavior of opDollar when it works with
>> the range
>> being sliced. For finite ranges, it essentially enforces that they
>> function
>> like arrays do, and for infinite ranges, it comes as close to that as
>> it can:
>>
>> https://github.com/D-Programming-Language/phobos/pull/854
>>
>> As of the latest state of that pull request, hasSlicing looks like
>>
>> template hasSlicing(R)
>> {
>>     enum bool hasSlicing = !isNarrowString!R && is(typeof(
>>     (inout int _dummy=0)
>>     {
>>         R r = void;
>>
>>         static if(isInfinite!R)
>>             typeof(take(r, 1)) s = r[1 .. 2];
>>         else
>>             R s = r[1 .. 2];
>>
>>         s = r[1 .. 2];
>>
>>         static if(is(typeof(r[0 .. $])))
>>         {
>>             R t = r[0 .. $];
>>             t = r[0 .. $];
>>
>>             static if(!isInfinite!R)
>>             {
>>                 R u = r[0 .. $ - 1];
>>                 u = r[0 .. $ - 1];
>>             }
>>         }
>>
>>         static assert(isForwardRange!(typeof(r[1 .. 2])));
>>         static assert(hasLength!(typeof(r[1 .. 2])));
>>     }));
>> }
>>
>>
>> - Jonathn M Davis
>
> I'm not a huge fan of the "opDollar" check, because essentially, it
> doesn't really buy you anything: if hasSlicing!R, then is "r = r[1..$]"
> legal? Who knows! You as a developer need to check manually that "r[0 ..
> $]" is legal first anyways...

That's a temporary thing because otherwise it'll break all of current 
RA. The idea is that if there is $ then it's tested

> Under those circumstances, why not cleanly splice the two notions?
>
> //----
> template hasSlicing(R)
> {
>      enum bool hasSlicing = !isNarrowString!R && is(typeof(
>      (inout int _dummy=0)
>      {
>          R r = void;
>
>          static if(isInfinite!R)
>              typeof(take(r, 1)) s = r[1 .. 2];
>          else
>              R s = r[1 .. 2];
>
>          s = r[1 .. 2];
>
>          static assert(isForwardRange!(typeof(r[1 .. 2])));
>          static assert(hasLength!(typeof(r[1 .. 2])));
>      }));
> }
>
> template hasSlicingToEnd(R)
> {
>      enum bool hasSlicingToEnd = !isNarrowString!R && is(typeof(
>      (inout int _dummy=0)
>      {
>          R r = void;
>
>          static if(is(typeof(r[0 .. $])))
>          {
>              R t = r[0 .. $];
>              t = r[0 .. $];
>
>              static if(!isInfinite!R)
>              {
>                  R u = r[0 .. $ - 1];
>                  u = r[0 .. $ - 1];
>              }
>          }
>      }));
> }
> //----
>
> IMO, this makes a clean distinction between both "types" of slicing. An
> added bonus is that (for now) it also correctly supports finite RA
> ranges that don't define opDollar.

Jonathon's version also supports RA without opDollar.

>
> //----
> PS: Do we really have to force that infinite slice to be of a type of
> "take"? Does that mean we can't imagine an infinite range that defines
> it's own finite slice type?
>
> if we change the code to:
>
> //----
>          static if(isInfinite!R)
>              auto s = r[1 .. 2]; //HERE1
>          else
>              R s = r[1 .. 2];
>
>          s = r[1 .. 2]; //HERE2
> //----
>
> Then we force nothing on the slice's type (HERE1), but do verify that
> subsequent slices will be assignable back to the original slice (HERE2)...

Well I'd rather never check that infinite range has 1..2 form of slicing 
to begin with. If we have some that do then we'd have to keep it.

-- 
Dmitry Olshansky
October 31, 2012
Re: "isDroppable" range trait for slicing to end
On Wednesday, October 31, 2012 11:37:13 monarch_dodra wrote:
> IMO, this makes a clean distinction between both "types" of
> slicing. An added bonus is that (for now) it also correctly
> supports finite RA ranges that don't define opDollar.

I don' think that such a distinction should be made at all. I think that all 
sliceable ranges should be required to implement opDollar. The problem is that 
it's unreasonable to require that when opDollar just got fixed, and arguably 
issue# 7177 should be implemented before it's reasonable to require it. But 
regardless, that means that creating a trait to test for opDollar working 
doesn't make sense. It would just have to be thrown away later.

> PS: Do we really have to force that infinite slice to be of a
> type of "take"? Does that mean we can't imagine an infinite range
> that defines it's own finite slice type?

I think that it's more valuable to make it consistent. What would a separate 
finite type even buy you? It would just be doing what take would do. I do kind 
of like the idea of just disallowing slicing without opDollar on infinite 
ranges though, in which case you'd have to use take yourself. I don't know 
what Andrei's take would be on that though.

- Jonathan M Davis
November 01, 2012
Re: "isDroppable" range trait for slicing to end
On Wednesday, 31 October 2012 at 18:40:09 UTC, Jonathan M Davis
wrote:
> On Wednesday, October 31, 2012 11:37:13 monarch_dodra wrote:
>> IMO, this makes a clean distinction between both "types" of
>> slicing. An added bonus is that (for now) it also correctly
>> supports finite RA ranges that don't define opDollar.
>
> I don' think that such a distinction should be made at all. I 
> think that all
> sliceable ranges should be required to implement opDollar. The 
> problem is that
> it's unreasonable to require that when opDollar just got fixed, 
> and arguably
> issue# 7177 should be implemented before it's reasonable to 
> require it. But
> regardless, that means that creating a trait to test for 
> opDollar working
> doesn't make sense. It would just have to be thrown away later.
>
>> PS: Do we really have to force that infinite slice to be of a
>> type of "take"? Does that mean we can't imagine an infinite 
>> range
>> that defines it's own finite slice type?
>
> I think that it's more valuable to make it consistent. What 
> would a separate
> finite type even buy you? It would just be doing what take 
> would do. I do kind
> of like the idea of just disallowing slicing without opDollar 
> on infinite
> ranges though, in which case you'd have to use take yourself. I 
> don't know
> what Andrei's take would be on that though.
>
> - Jonathan M Davis

You are probably right. I think I've had my head too deep inside
algorithm implementation detail, and got my focus on the wrong
things.

Most of the theoretical ranges I'm trying to support probably
don't exist in real life anyways :/ Might as well keep things 
consistent.
Next ›   Last »
1 2 3
Top | Discussion index | About this forum | D home