www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - non empty slices

reply Alex <sascha.orlov gmail.com> writes:
Ok, a strange question from my side again...
Let's begin, with what works:
Say, I define two types:

import std.typecons : Nullable;
alias M = uint;
alias Mr = Nullable!M;

then, I can write two types of methods. Those which can handle 
Mr's:
void fun1(Mr val)
{
     //do some funny stuff
}

and those, which assume an existing value is provided:
void fun2(M val)
{
     //do some other funny stuff
}

they could be overloaded by using the same name I think... but 
this is not the point.

The question is, how to define the same thing for ranges. What I 
started with is:

import std.range : iota;
alias MrSlice = typeof(iota(M.init));

so far, so good. The MrSlice-thing is the analogy for Mr, as it 
can be empty, as Mr can.
What I also need is the analogy for the M-thing. But how can I 
define a slice, which is not-empty by definition?

A workaround, which works is for example, using in a function 
which assumes a non-empty slice a contract:
void fun3(MrSlice val)
in
{
     assert(!val.empty);
}
body
{
     // do some funny stuff, part 3 :)
}

I tried also something using Algebraic types with an underlying 
int, but couldn't manage to append elements to something like:
alias List2 = Algebraic!(This[]);
or
alias List(Leaf) = Algebraic!(Leaf, This*);

The cool thing is, if the algebraic stuff works, it would 
potentially be able to replace all four aliases altogether...
But a knock-out criteria is: the solution has to be  nogc
Jun 02 2016
parent reply ag0aep6g <anonymous example.com> writes:
On 06/02/2016 03:37 PM, Alex wrote:

 The question is, how to define the same thing for ranges. What I started
 with is:

 import std.range : iota;
 alias MrSlice = typeof(iota(M.init));

 so far, so good. The MrSlice-thing is the analogy for Mr, as it can be
 empty, as Mr can.
 What I also need is the analogy for the M-thing. But how can I define a
 slice, which is not-empty by definition?


A little terminology: "Slice" is not a synonym for "range". iota does 
not return a slice, it returns a range. "Slice" is being used as a 
synonym for "dynamic array" (Type[]), and in the context of the slicing 
operator (expression[] or expression[a .. b]).

Now, for the actual question - how to define a range that is non-empty 
by definition:

One of the range primitives is popFront. popFront removes one element 
from the range. popFront cannot change the type of the range. So you 
can't have a type that is a range, and is guaranteed not to be empty, 
and can be emptied by calling popFront.

But you can have a type that is a range, is guaranteed not to be empty, 
and *cannot* be emptied by calling popFront: an infinite range. That's a 
range that never gets empty no matter how often popFront is called.

The library recognizes infinite ranges when you define `empty` like 
this: `enum bool empty = false;`. There's 
std.range.primitives.isInfinite [1] to check for them.

I guess that's not really what you're looking for. I don't think you can 
otherwise statically check that a range isn't empty. You could probably 
make a wrapper that checks once on construction, but that's still a 
run-time check. And I don't see it being particularly useful, because 
popFront is an essential parts of ranges.

[...]

 I tried also something using Algebraic types with an underlying int, but
 couldn't manage to append elements to something like:
 alias List2 = Algebraic!(This[]);
 or
 alias List(Leaf) = Algebraic!(Leaf, This*);

 The cool thing is, if the algebraic stuff works, it would potentially be
 able to replace all four aliases altogether...
 But a knock-out criteria is: the solution has to be  nogc


You've lost me there. I don't see how non-empty range and Algebraic connect.


[1] https://dlang.org/phobos/std_range_primitives.html#.isInfinite
Jun 02 2016
parent reply Alex <sascha.orlov gmail.com> writes:
On Thursday, 2 June 2016 at 14:31:15 UTC, ag0aep6g wrote:

 A little terminology: "Slice" is not a synonym for "range". 
 iota does not return a slice, it returns a range. "Slice" is 
 being used as a synonym for "dynamic array" (Type[]), and in 
 the context of the slicing operator (expression[] or 
 expression[a .. b]).

 Now, for the actual question - how to define a range that is 
 non-empty by definition:

 One of the range primitives is popFront. popFront removes one 
 element from the range. popFront cannot change the type of the 
 range. So you can't have a type that is a range, and is 
 guaranteed not to be empty, and can be emptied by calling 
 popFront.

 But you can have a type that is a range, is guaranteed not to 
 be empty, and *cannot* be emptied by calling popFront: an 
 infinite range. That's a range that never gets empty no matter 
 how often popFront is called.

 The library recognizes infinite ranges when you define `empty` 
 like this: `enum bool empty = false;`. There's 
 std.range.primitives.isInfinite [1] to check for them.

 I guess that's not really what you're looking for.


Yes, that's not. :)


 I don't think you can otherwise statically check that a range 
 isn't empty. You could probably make a wrapper that checks once 
 on construction, but that's still a run-time check. And I don't 
 see it being particularly useful, because popFront is an 
 essential parts of ranges.


So this would mean, the contract I use now for run-time check is 
ok.
And... well... maybe I can alias two different methods, one which 
returns an arbitrary range and one which returns a range, checked 
for emptiness in an out contract...
This already would save a lot of code duplication...


 You've lost me there. I don't see how non-empty range and 
 Algebraic connect.


What I mean is: if there would be a possibility to use algebraic 
types here (or maybe some kind of template...), then my types 
would be able (maybe! did not seen anything similar yet...) to 
choose the proper methods for themselves automatically:
As long as my type has a length > 1 it is handled as a range, if 
the range has the length=1 it is handled as a single element and 
not as a range, if the range has the length=0 it is handled as an 
absent element.
Jun 02 2016
parent reply ag0aep6g <anonymous example.com> writes:
On 06/02/2016 05:16 PM, Alex wrote:

 What I mean is: if there would be a possibility to use algebraic types
 here (or maybe some kind of template...), then my types would be able
 (maybe! did not seen anything similar yet...) to choose the proper
 methods for themselves automatically:
 As long as my type has a length > 1 it is handled as a range, if the
 range has the length=1 it is handled as a single element and not as a
 range, if the range has the length=0 it is handled as an absent element.


I may be getting what you're up to. Maybe not.

So we start with something like this (using arrays instead of arbitrary 
ranges to keep things simple):


     import std.stdio: writeln;
     void main()
     {
         f([]);
         f([1]);
         f([1, 2]);
     }
     void f(int[] a)
     {
         if (a.length == 0) f_none(a);
         else if (a.length == 1) f_one(a);
         else f_many(a);
     }
     void f_none(int[] a)
     {
         writeln("nothing to see here");
     }
     void f_one(int[] a)
     {
         assert(a.length == 1);
         writeln("exactly one: ", a[0]);
     }
     void f_many(int[] a)
     {
         assert(a.length >= 2);
         writeln("at least two: ", a[0 .. 2]);
     }


And instead you'd like something more like this:


     import std.stdio: writeln;
     import std.variant: Algebraic;

     void main()
     {
         f([]);
         f([1]);
         f([1, 2]);
     }

     void f(int[] arr)
     {
         A a = arrayToA(arr);
         foreach (T; A.AllowedTypes)
         {
             if (T* p = a.peek!T) f_impl(*p);
         }
     }

     void f_impl(Empty e) { writeln("nothing to see here"); }
     void f_impl(int a) { writeln("exactly one: ", a); }
     void f_impl(Many!int a) { writeln("at least two: ", a[0 .. 2]); }

     struct Empty {}
     struct Many(T)
     {
         T[] arr;
         alias arr this;
         /* Somehow it's enforced here that arr.length >= 2. */
     }

     alias A = Algebraic!(Empty, int, Many!int);
     A arrayToA(int[] a)
     {
         A result;
         switch (a.length)
         {
             case 0: result = Empty.init; break;
             case 1: result = a[0]; break;
             default: result = Many!int(a);
         }
         return result;
     }


And the advantages of it are:
* Don't need asserts in the different `f_impl`s.
* The branching in f is guided by the parameter types of f_impl (could 
possibly be extracted, instead of being hardcoded manually).

Tell me if I'm way off.
Jun 02 2016
parent reply Alex <sascha.orlov gmail.com> writes:
On Thursday, 2 June 2016 at 16:21:03 UTC, ag0aep6g wrote:

 On 06/02/2016 05:16 PM, Alex wrote:

 I may be getting what you're up to. Maybe not.

 So we start with something like this (using arrays instead of 
 arbitrary ranges to keep things simple):


     import std.stdio: writeln;
     void main()
     {
         f([]);
         f([1]);
         f([1, 2]);
     }
     void f(int[] a)
     {
         if (a.length == 0) f_none(a);
         else if (a.length == 1) f_one(a);
         else f_many(a);
     }
     void f_none(int[] a)
     {
         writeln("nothing to see here");
     }
     void f_one(int[] a)
     {
         assert(a.length == 1);
         writeln("exactly one: ", a[0]);
     }
     void f_many(int[] a)
     {
         assert(a.length >= 2);
         writeln("at least two: ", a[0 .. 2]);
     }


 And instead you'd like something more like this:


     import std.stdio: writeln;
     import std.variant: Algebraic;

     void main()
     {
         f([]);
         f([1]);
         f([1, 2]);
     }

     void f(int[] arr)
     {
         A a = arrayToA(arr);
         foreach (T; A.AllowedTypes)
         {
             if (T* p = a.peek!T) f_impl(*p);
         }
     }

     void f_impl(Empty e) { writeln("nothing to see here"); }
     void f_impl(int a) { writeln("exactly one: ", a); }
     void f_impl(Many!int a) { writeln("at least two: ", a[0 .. 
 2]); }

     struct Empty {}
     struct Many(T)
     {
         T[] arr;
         alias arr this;
         /* Somehow it's enforced here that arr.length >= 2. */
     }

     alias A = Algebraic!(Empty, int, Many!int);
     A arrayToA(int[] a)
     {
         A result;
         switch (a.length)
         {
             case 0: result = Empty.init; break;
             case 1: result = a[0]; break;
             default: result = Many!int(a);
         }
         return result;
     }


 And the advantages of it are:
 * Don't need asserts in the different `f_impl`s.


Yes.


 * The branching in f is guided by the parameter types of f_impl 
 (could possibly be extracted, instead of being hardcoded 
 manually).


Yes! :)


 Tell me if I'm way off.


You totally hit the point!
The cool thing about the Algebraic is as I expected, that it 
doesn't change it's type... And the hard thing is, that I'm not 
used to its Empty, Many, ... things yet.
But the question remains how to keep this  nogc? I wonder at the 
line with peek... and why it is not just returning the value...
Jun 02 2016
next sibling parent reply Alex <sascha.orlov gmail.com> writes:
On Thursday, 2 June 2016 at 20:11:21 UTC, Alex wrote:

 On Thursday, 2 June 2016 at 16:21:03 UTC, ag0aep6g wrote:

     void f(int[] arr)
     {
         A a = arrayToA(arr);
         foreach (T; A.AllowedTypes)
         {
             if (T* p = a.peek!T) f_impl(*p);
         }
     }


 You totally hit the point!
 The cool thing about the Algebraic is as I expected, that it 
 doesn't change it's type... And the hard thing is, that I'm not 
 used to its Empty, Many, ... things yet.
 But the question remains how to keep this  nogc? I wonder at 
 the line with peek... and why it is not just returning the 
 value...


Just tried this instead of your f-function:
void f(int[] arr)
{
     A result;
     import std.meta;
     alias TL = AliasSeq!(Empty, int, Many!int);
     int caseS;
     switch (arr.length)
     {
         case 0: result = Empty.init; caseS = 0; break;
         case 1: result = arr[0]; caseS = 1;  break;
         default: result = Many!int(arr); caseS = 2;
     }
     f_impl(*result.get!(TL[caseS]));
}
But got: Error: variable caseS cannot be read at compile time
which is obviously true...
Jun 02 2016
parent reply ag0aep6g <anonymous example.com> writes:
On 06/02/2016 11:37 PM, Alex wrote:

 Just tried this instead of your f-function:
 void f(int[] arr)
 {
      A result;
      import std.meta;
      alias TL = AliasSeq!(Empty, int, Many!int);
      int caseS;
      switch (arr.length)
      {
          case 0: result = Empty.init; caseS = 0; break;
          case 1: result = arr[0]; caseS = 1;  break;
          default: result = Many!int(arr); caseS = 2;
      }
      f_impl(*result.get!(TL[caseS]));
 }
 But got: Error: variable caseS cannot be read at compile time
 which is obviously true...


Yeah, can't do it that way. You have only one f_impl call, but want it 
to go to different overloads based on dynamic information (caseS). That 
doesn't work.

You need three different f_impl calls. You can generate them, so there's 
only one in the source, but it's a bit involved:

     sw: switch (caseS)
     {
         foreach (i, T; TL)
         {
             case i: f_impl(result.get!T); break sw;
         }
         default: assert(false);
     }
Jun 02 2016
parent reply Alex <sascha.orlov gmail.com> writes:
On Thursday, 2 June 2016 at 22:17:32 UTC, ag0aep6g wrote:

 Yeah, can't do it that way. You have only one f_impl call, but 
 want it to go to different overloads based on dynamic 
 information (caseS). That doesn't work.

 You need three different f_impl calls. You can generate them, 
 so there's only one in the source, but it's a bit involved:

     sw: switch (caseS)
     {
         foreach (i, T; TL)
         {
             case i: f_impl(result.get!T); break sw;
         }
         default: assert(false);
     }


Oh... wow... cool! :)
But still, I can't mark the f-method  nogc, and this is not due 
to the writeln calls... why GC is invoked, although everything is 
known and no memory allocation should happen?
Jun 02 2016
parent reply ag0aep6g <anonymous example.com> writes:
On 06/03/2016 01:17 AM, Alex wrote:

 But still, I can't mark the f-method  nogc, and this is not due to the
 writeln calls... why GC is invoked, although everything is known and no
 memory allocation should happen?


It's the Algebraic. The `get` method isn't  nogc. The documentation [1] 
says that it may throw an exception, which is most probably being 
allocated through the GC. So that's a reason why it can't be  nogc.

The alternative `peek` method is not documented to throw an exception, 
but it's not  nogc either. No idea why. Maybe Algebraic does GC 
allocations internally. I wouldn't know for what, though. Or it misses a 
 nogc somewhere.
Jun 02 2016
next sibling parent Alex <sascha.orlov gmail.com> writes:
On Thursday, 2 June 2016 at 23:35:53 UTC, ag0aep6g wrote:

 It's the Algebraic. The `get` method isn't  nogc. The 
 documentation [1] says that it may throw an exception, which is 
 most probably being allocated through the GC. So that's a 
 reason why it can't be  nogc.

 The alternative `peek` method is not documented to throw an 
 exception, but it's not  nogc either. No idea why. Maybe 
 Algebraic does GC allocations internally. I wouldn't know for 
 what, though. Or it misses a  nogc somewhere.





Yeah... thanks a lot!
Jun 02 2016
prev sibling parent reply ag0aep6g <anonymous example.com> writes:
On 06/03/2016 01:35 AM, ag0aep6g wrote:

 The alternative `peek` method is not documented to throw an exception,
 but it's not  nogc either. No idea why. Maybe Algebraic does GC
 allocations internally. I wouldn't know for what, though. Or it misses a
  nogc somewhere.


I've looked at the source to see if it's something simple, and 
Algebraic/VariantN seems to be terribly complicated. Writing a simpler 
 nogc tagged union may be easier than fixing the phobos one, if the 
phobos one can even be made  nogc.
Jun 02 2016
parent Alex <sascha.orlov gmail.com> writes:
On Thursday, 2 June 2016 at 23:44:49 UTC, ag0aep6g wrote:

 On 06/03/2016 01:35 AM, ag0aep6g wrote:

 The alternative `peek` method is not documented to throw an 
 exception,
 but it's not  nogc either. No idea why. Maybe Algebraic does GC
 allocations internally. I wouldn't know for what, though. Or 
 it misses a
  nogc somewhere.


 I've looked at the source to see if it's something simple, and 
 Algebraic/VariantN seems to be terribly complicated. Writing a 
 simpler  nogc tagged union may be easier than fixing the phobos 
 one, if the phobos one can even be made  nogc.


I'm also inside the source... yes, its not a simple one. I think 
I will try to write my own one...
Jun 02 2016
prev sibling parent ag0aep6g <anonymous example.com> writes:
On 06/02/2016 10:11 PM, Alex wrote:

 The cool thing about the Algebraic is as I expected, that it doesn't
 change it's type... And the hard thing is, that I'm not used to its
 Empty, Many, ... things yet.


I just made those up on the spot. Note that Many is not actually 
implemented at all. There is no check that the array has at least two 
elements. And Empty is just there, because I needed a type for the 
Algebraic.


 But the question remains how to keep this  nogc?


Apparently, it's Algebraic that isn't  nogc. I don't know what it 
allocates. Maybe it allocates space for large types (but there aren't 
any here), or maybe it can throw a GC-allocated exception.


 I wonder at the line
 with peek... and why it is not just returning the value...


I wouldn't expect that to be the problem with  nogc. As far as I see, 
the pointer is used as a way to return "not found" in the form of null. 
When you get a non-null pointer it's probably just into the Algebraic.
Jun 02 2016