www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Is there any reason why in can't work with dynamic arrays?

reply Brett <Brett gmail.com> writes:
T[] x;

if (y in x) ...

It just checks to see if y is in between 0 and length. Clearly y 
has to be an int and clearly the semantics are equivalent to AA 
and so it all works out rather than having an arbitrary special 
case.

This is helpful when one has generate algorithms that can work 
with AA's or DA's that use in.
Sep 17
next sibling parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Tuesday, 17 September 2019 at 17:43:39 UTC, Brett wrote:
 T[] x;

 if (y in x) ...

 It just checks to see if y is in between 0 and length.
Most people asking for this want it to check that the *value* y is in the array x, which is rejected for requiring a linear search. But your idea could be done quickly, just I expect it would cause confusion with the people asking for the other. I like to just check if y >= 0 && y < x.length which is more clear anyway.
Sep 17
next sibling parent reply Brett <Brett gmail.com> writes:
On Tuesday, 17 September 2019 at 17:46:09 UTC, Adam D. Ruppe 
wrote:
 On Tuesday, 17 September 2019 at 17:43:39 UTC, Brett wrote:
 T[] x;

 if (y in x) ...

 It just checks to see if y is in between 0 and length.
Most people asking for this want it to check that the *value* y is in the array x, which is rejected for requiring a linear search. But your idea could be done quickly, just I expect it would cause confusion with the people asking for the other. I like to just check if y >= 0 && y < x.length which is more clear anyway.
Yes, I could see that, but it doesn't do that with AA's so but I could see how it could be problematic. Alternatively, have a keys for a DA: then one can do if (y in x.keys) and this is far more expressive so there is no confusion and also works with AA's(and would not result in keys having to be created because it is semantically the same as (y in x) if x is an AA).
Sep 17
next sibling parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Tuesday, 17 September 2019 at 18:10:40 UTC, Brett wrote:
 Alternatively, have a keys for a DA:

 then one can do

 if (y in x.keys)
Indeed. Actually, fun fact: you can do that in your own code. Write a function `keys` that returns a struct implementing `opBinaryRight`. Like so: ``` import std.stdio; struct KeyRange { size_t max; bool opBinaryRight(string op : "in")(size_t v) { return v >= 0 && v < max; // the < 0 never passes but meh clearer code } } KeyRange keys(T)(T[] t) { return KeyRange(t.length); } alias keys = object.keys; // also bring in the runtime library's keys for AA; this line lets both work together in the same module without name conflicts void main() { int[] x = [0, 2]; int y = 1; writeln(y in x.keys); // works! writeln(y+5 in x.keys); // this too } ``` The language features used there are UFCS (allowing x.keys), operator overloading (opBinaryRight), and overload set merging (the alias line with the comment). Searching those terms on this website should give more information if you'd like to learn more.
Sep 17
next sibling parent reply jmh530 <john.michael.hall gmail.com> writes:
On Wednesday, 18 September 2019 at 01:27:09 UTC, Adam D. Ruppe 
wrote:
 [snip]
 alias keys = object.keys; // also bring in the runtime [snip]
This line doesn't compile for me.
Sep 18
parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Wednesday, 18 September 2019 at 20:07:38 UTC, jmh530 wrote:
 alias keys = object.keys; // also bring in the runtime [snip]
This line doesn't compile for me.
what's the error? and compiler version too
Sep 18
parent reply jmh530 <john.michael.hall gmail.com> writes:
On Wednesday, 18 September 2019 at 20:12:32 UTC, Adam D. Ruppe 
wrote:
 On Wednesday, 18 September 2019 at 20:07:38 UTC, jmh530 wrote:
 alias keys = object.keys; // also bring in the runtime [snip]
This line doesn't compile for me.
what's the error? and compiler version too
I just ran it on run.dlang.org as that is my go-to for trying any quick D code. It compiles with dmd-nightly, but not dmd, dmd-beta, ldc, ldc-beta. https://run.dlang.io/is/fCwIIG The error was: onlineapp.d(11): Error: alias `onlineapp.keys` conflicts with template onlineapp.keys(T)(T[] t) at onlineapp.d(10)
Sep 18
parent Adam D. Ruppe <destructionator gmail.com> writes:
On Wednesday, 18 September 2019 at 20:57:34 UTC, jmh530 wrote:
 The error was:
 onlineapp.d(11): Error: alias `onlineapp.keys` conflicts with 
 template onlineapp.keys(T)(T[] t) at onlineapp.d(10)
huh yeah, it looks like it only works on the dmd 2.088 and above, probably because the template overloading rules changed. well regardless you can just leave it out to get the same idea too. maybe rename to avoid any potential conflict. (though even if a name does conflict, you can always use the full object.keys name to disambiguate)
Sep 18
prev sibling parent Brett <Brett gmail.com> writes:
On Wednesday, 18 September 2019 at 01:27:09 UTC, Adam D. Ruppe 
wrote:
 On Tuesday, 17 September 2019 at 18:10:40 UTC, Brett wrote:
 Alternatively, have a keys for a DA:

 then one can do

 if (y in x.keys)
Indeed. Actually, fun fact: you can do that in your own code. Write a function `keys` that returns a struct implementing `opBinaryRight`. Like so: ``` import std.stdio; struct KeyRange { size_t max; bool opBinaryRight(string op : "in")(size_t v) { return v >= 0 && v < max; // the < 0 never passes but meh clearer code } } KeyRange keys(T)(T[] t) { return KeyRange(t.length); } alias keys = object.keys; // also bring in the runtime library's keys for AA; this line lets both work together in the same module without name conflicts void main() { int[] x = [0, 2]; int y = 1; writeln(y in x.keys); // works! writeln(y+5 in x.keys); // this too } ``` The language features used there are UFCS (allowing x.keys), operator overloading (opBinaryRight), and overload set merging (the alias line with the comment). Searching those terms on this website should give more information if you'd like to learn more.
Thanks. I guess I should have realize that UFCS could solve it. Probably should be added to phobos?
Sep 18
prev sibling next sibling parent reply Daniel Kozak <kozzi11 gmail.com> writes:
On Tue, Sep 17, 2019 at 8:15 PM Brett via Digitalmars-d
<digitalmars-d puremagic.com> wrote:
 ...

 Alternatively, have a keys for a DA:

 then one can do

 if (y in x.keys)

 and this is far more expressive so there is no confusion and also
 works with AA's(and would not result in keys having to be created
 because it is semantically the same as (y in x) if x is an AA).
No this would not work, because on AAs (keys) it will return dynamic array and you are back with same issue. You will need to use something with different name and write some UFCS helper for both DA and AA, for AA it could just return itself, for DA you can use Adam's example
Sep 18
parent Brett <Brett gmail.com> writes:
On Wednesday, 18 September 2019 at 08:24:17 UTC, Daniel Kozak 
wrote:
 On Tue, Sep 17, 2019 at 8:15 PM Brett via Digitalmars-d 
 <digitalmars-d puremagic.com> wrote:
 ...

 Alternatively, have a keys for a DA:

 then one can do

 if (y in x.keys)

 and this is far more expressive so there is no confusion and 
 also
 works with AA's(and would not result in keys having to be 
 created
 because it is semantically the same as (y in x) if x is an AA).
No this would not work, because on AAs (keys) it will return dynamic array and you are back with same issue. You will need to use something with different name and write some UFCS helper for both DA and AA, for AA it could just return itself, for DA you can use Adam's example
No, because x.keys would return EXACTLY a dynamic array and not work(exactly as you said)... so the compiler knows that it works! That is, x.keys is a semantic rule to check in the keys, it actually does not return any dynamic array ever! Because of that the compiler can make the semantic work. y in x.keys is ALWAYS invalid! Right? For arrays, for associative arrays and that is all it works on! So if it is always invalid, it can always be made invalid(to rewrite the semantic). There can be no misinterpretation because it's always invalid. For example, to make it clear too you, what if we extended the compiler so it looked like this: y in x#keys Then could it work? Could the semantic make sense to you? Sure it changes the language, but imagine a D 3.4383 where it was added, possible? The compiler would have no issue extending the grammar to accept x.keys as a semantic and to do "magic" and people that learn the in keyword would just have to learn how it works, simple as that. That is, WE DEFINE `a in x.keys` to be a range check. This then works for DA's because x.keys just is an "alias" to x and x.keys is just a DA when x is an AA(to to the first case). To make it clear: we want to do y in x for DA, right? But we can't because this can be confusing. so we make a rule that when we have the syntax y in x.keys it does a range check as if the first case, but it is not confusing now. but if x is an AA, x.keys returns a DA, and now we are back in the first case... so we do y in x.keys.keys but still in the first case... but now the compiler sees, effectively y in (x.keys).keys and knows to do a range check ala the first case... but it is redundant to write x.keys.keys so it can be simplified. It works, trust me, think about it!
Sep 18
prev sibling parent reply Alex <sascha.orlov gmail.com> writes:
On Tuesday, 17 September 2019 at 18:10:40 UTC, Brett wrote:
 I like to just check if y >= 0 && y < x.length which is more 
 clear  anyway.
Yes, I could see that, but it doesn't do that with AA's so but I could see how it could be problematic. Alternatively, have a keys for a DA: then one can do if (y in x.keys) and this is far more expressive so there is no confusion and also works with AA's(and would not result in keys having to be created because it is semantically the same as (y in x) if x is an AA).
It is also expressive to define size_t y; and to check y only for being < x.length. An array does not have keys. It has indices.
Sep 18
parent Brett <Brett gmail.com> writes:
On Wednesday, 18 September 2019 at 10:25:57 UTC, Alex wrote:
 On Tuesday, 17 September 2019 at 18:10:40 UTC, Brett wrote:
 I like to just check if y >= 0 && y < x.length which is more 
 clear  anyway.
Yes, I could see that, but it doesn't do that with AA's so but I could see how it could be problematic. Alternatively, have a keys for a DA: then one can do if (y in x.keys) and this is far more expressive so there is no confusion and also works with AA's(and would not result in keys having to be created because it is semantically the same as (y in x) if x is an AA).
It is also expressive to define size_t y; and to check y only for being < x.length. An array does not have keys. It has indices.
That is called parsing language to be pedantic with out loss of generality. It means nothing. A rose by any name is a rose. In fact, it means one understands less of the problem than they think.
Sep 18
prev sibling parent Vladimir Panteleev <thecybershadow.lists gmail.com> writes:
On Tuesday, 17 September 2019 at 17:46:09 UTC, Adam D. Ruppe 
wrote:
 On Tuesday, 17 September 2019 at 17:43:39 UTC, Brett wrote:
 T[] x;

 if (y in x) ...

 It just checks to see if y is in between 0 and length.
Most people asking for this want it to check that the *value* y is in the array x, which is rejected for requiring a linear search. But your idea could be done quickly, just I expect it would cause confusion with the people asking for the other.
It would definitely be very confusing to Python users, where "x in [a, b, c]" does check if the value is in the list using a linear search.
Sep 17
prev sibling next sibling parent reply Patrick Schluter <Patrick.Schluter bbox.fr> writes:
On Tuesday, 17 September 2019 at 17:43:39 UTC, Brett wrote:
 T[] x;

 if (y in x) ...

 It just checks to see if y is in between 0 and length. Clearly 
 y has to be an int and clearly the semantics are equivalent to 
 AA and so it all works out rather than having an arbitrary 
 special case.

 This is helpful when one has generate algorithms that can work 
 with AA's or DA's that use in.
This is the wrong forum for this kind of questions. Go to the learn forum.
Sep 17
next sibling parent Brett <Brett gmail.com> writes:
On Tuesday, 17 September 2019 at 19:59:24 UTC, Patrick Schluter 
wrote:
 On Tuesday, 17 September 2019 at 17:43:39 UTC, Brett wrote:
 T[] x;

 if (y in x) ...

 It just checks to see if y is in between 0 and length. Clearly 
 y has to be an int and clearly the semantics are equivalent to 
 AA and so it all works out rather than having an arbitrary 
 special case.

 This is helpful when one has generate algorithms that can work 
 with AA's or DA's that use in.
This is the wrong forum for this kind of questions. Go to the learn forum.
Perhaps you need to go to the learn forum Boss?
Sep 17
prev sibling parent reply Brett <Brett gmail.com> writes:
On Tuesday, 17 September 2019 at 19:59:24 UTC, Patrick Schluter 
wrote:
 On Tuesday, 17 September 2019 at 17:43:39 UTC, Brett wrote:
 T[] x;

 if (y in x) ...

 It just checks to see if y is in between 0 and length. Clearly 
 y has to be an int and clearly the semantics are equivalent to 
 AA and so it all works out rather than having an arbitrary 
 special case.

 This is helpful when one has generate algorithms that can work 
 with AA's or DA's that use in.
This is the wrong forum for this kind of questions. Go to the learn forum.
Only if you go first Boss.
Sep 17
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 09/17/2019 06:19 PM, Brett wrote:

 This is the wrong forum for this kind of questions. Go to the learn
 forum.
Only if you go first
In case it's not clear, the reason why these questions are better suited to the Learn forum is because many of us are hanging out over in that forum, hungry for answers to such questions. Ali
Sep 17
parent Brett <Brett gmail.com> writes:
On Wednesday, 18 September 2019 at 04:38:09 UTC, Ali Çehreli 
wrote:
 On 09/17/2019 06:19 PM, Brett wrote:

 This is the wrong forum for this kind of questions. Go to
the learn
 forum.
Only if you go first
In case it's not clear, the reason why these questions are better suited to the Learn forum is because many of us are hanging out over in that forum, hungry for answers to such questions. Ali
Well, I was thinking that it would probably require a compiler modification given the nature of in so it's not so much about learning as it is about compiler details. That is, I'm more interested in get it part of D officially as it is a useful semantic... not just for my own benefit.
Sep 18
prev sibling parent reply JN <666total wp.pl> writes:
On Tuesday, 17 September 2019 at 17:43:39 UTC, Brett wrote:
 T[] x;

 if (y in x) ...

 It just checks to see if y is in between 0 and length. Clearly 
 y has to be an int and clearly the semantics are equivalent to 
 AA and so it all works out rather than having an arbitrary 
 special case.

 This is helpful when one has generate algorithms that can work 
 with AA's or DA's that use in.
Wow! Does really in work like that with arrays? This is terrible. I'd never expect in to check if index is in range. In every language in existence (that I know of) that has 'in', 'in' is a search for existence of value, whether a linear search is required or not.
Sep 18
parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Wednesday, September 18, 2019 1:08:23 AM MDT JN via Digitalmars-d wrote:
 On Tuesday, 17 September 2019 at 17:43:39 UTC, Brett wrote:
 T[] x;

 if (y in x) ...

 It just checks to see if y is in between 0 and length. Clearly
 y has to be an int and clearly the semantics are equivalent to
 AA and so it all works out rather than having an arbitrary
 special case.

 This is helpful when one has generate algorithms that can work
 with AA's or DA's that use in.
Wow! Does really in work like that with arrays? This is terrible. I'd never expect in to check if index is in range. In every language in existence (that I know of) that has 'in', 'in' is a search for existence of value, whether a linear search is required or not.
No, in does not work that way with dynamic arrays. It doesn't work with them at all. That's just what the OP wants it to do. If in worked with arrays, it would definitely check for the existence of a value in the array, because that's what it does with other types, but its big-o complexity is supposed to be no worse than O(log n) (which is what it costs to look up a value in a balanced, binary tree such as a red-black tree) so that its complexity can be relied upon in generic code. However, to look up a value in a dynamic array would cost O(n), so it's not supported. - Jonathan M Davis
Sep 18