www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - extend "in" to all array types

reply "pplantinga" <plantinga.peter gmail.com> writes:
In python, I really like the ability to check if an element is in 
an array:

if x in array:


D has this, but only for associative arrays. Is there any chance 
we could extend this to every kind of array?
Jan 15 2014
next sibling parent reply "Adam D. Ruppe" <destructionator gmail.com> writes:
On Wednesday, 15 January 2014 at 15:30:35 UTC, pplantinga wrote:

 Is there any chance we could extend this to every kind of array?


Probably not, since there's a significant speed difference 
between in associative array and in regular array. For a regular 
array, it means potentially looping over every item in the array. 
As a general rule, D likes to make long loops obvious in some 
way, like a different function name.

There are functions which do the same thing. Notably, 
std.algorithm.canFind

import std.algorithm;
if(array.canFind(x)) { /* do something */ }


You could also define your own function In if you wanted to keep 
the order that way:

bool In(T)(T lookFor, T[] lookIn) {
     import std.algorithm;
     return lookIn.canFind(lookFor);
}

if(x.In(array)) { /* do something */ }

It is capitalized so it doesn't clash with the keyword, and still 
uses the dot - it is a function called with dot syntax instead of 
an operator -  but it works.
Jan 15 2014
next sibling parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Wednesday, 15 January 2014 at 15:38:19 UTC, Adam D. Ruppe 
wrote:

 On Wednesday, 15 January 2014 at 15:30:35 UTC, pplantinga wrote:

 Is there any chance we could extend this to every kind of 
 array?


 Probably not, since there's a significant speed difference 
 between in associative array and in regular array. For a 
 regular array, it means potentially looping over every item in 
 the array. As a general rule, D likes to make long loops 
 obvious in some way, like a different function name.

 There are functions which do the same thing. Notably, 
 std.algorithm.canFind

 import std.algorithm;
 if(array.canFind(x)) { /* do something */ }


 You could also define your own function In if you wanted to 
 keep the order that way:

 bool In(T)(T lookFor, T[] lookIn) {
     import std.algorithm;
     return lookIn.canFind(lookFor);
 }

 if(x.In(array)) { /* do something */ }

 It is capitalized so it doesn't clash with the keyword, and 
 still uses the dot - it is a function called with dot syntax 
 instead of an operator -  but it works.


or:

import std.functional : binaryReverseArgs;
import std.algorithm : canFind;

alias In = binaryReverseArgs!canFind;
Jan 15 2014
parent "Meta" <jared771 gmail.com> writes:
On Wednesday, 15 January 2014 at 15:51:06 UTC, John Colvin wrote:

 On Wednesday, 15 January 2014 at 15:38:19 UTC, Adam D. Ruppe 
 wrote:

 On Wednesday, 15 January 2014 at 15:30:35 UTC, pplantinga 
 wrote:

 Is there any chance we could extend this to every kind of 
 array?


 Probably not, since there's a significant speed difference 
 between in associative array and in regular array. For a 
 regular array, it means potentially looping over every item in 
 the array. As a general rule, D likes to make long loops 
 obvious in some way, like a different function name.

 There are functions which do the same thing. Notably, 
 std.algorithm.canFind

 import std.algorithm;
 if(array.canFind(x)) { /* do something */ }


 You could also define your own function In if you wanted to 
 keep the order that way:

 bool In(T)(T lookFor, T[] lookIn) {
    import std.algorithm;
    return lookIn.canFind(lookFor);
 }

 if(x.In(array)) { /* do something */ }

 It is capitalized so it doesn't clash with the keyword, and 
 still uses the dot - it is a function called with dot syntax 
 instead of an operator -  but it works.


 or:

 import std.functional : binaryReverseArgs;
 import std.algorithm : canFind;

 alias In = binaryReverseArgs!canFind;


Programming in D is constantly mind-blowing as you realize how 
powerful the language is.
Jan 15 2014
prev sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 01/15/2014 07:38 AM, Adam D. Ruppe wrote:


 Probably not, since there's a significant speed difference between in
 associative array and in regular array. For a regular array, it means
 potentially looping over every item in the array.


And a specialization for std.range.SortedRange would use binary search:



Ali
Jan 15 2014
next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Jan 15, 2014 at 10:57:14AM -0800, Ali Çehreli wrote:

 On 01/15/2014 07:38 AM, Adam D. Ruppe wrote:
 

 Probably not, since there's a significant speed difference between in
 associative array and in regular array. For a regular array, it means
 potentially looping over every item in the array.


 
 And a specialization for std.range.SortedRange would use binary search:
 



[...]

Does std.algorithm.find have a specialization for SortedRange? I know
that some algorithms do, I just don't remember which.


T

-- 
What do you get if you drop a piano down a mineshaft? A flat minor.
Jan 15 2014
parent "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Wednesday, 15 January 2014 at 19:10:27 UTC, H. S. Teoh wrote:

 Does std.algorithm.find have a specialization for SortedRange? 
 I know
 that some algorithms do, I just don't remember which.


 T


Not yet, SortedRange could need some attention. Judging by a 
certain old but recently relevant pull request[1], I think Andrei 
has some work on it.

[1] https://github.com/D-Programming-Language/phobos/pull/1184
Jan 15 2014
prev sibling parent "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Wednesday, 15 January 2014 at 18:57:15 UTC, Ali Çehreli wrote:

 On 01/15/2014 07:38 AM, Adam D. Ruppe wrote:


 Probably not, since there's a significant speed difference


 between in

 associative array and in regular array. For a regular array,


 it means

 potentially looping over every item in the array.


 And a specialization for std.range.SortedRange would use binary 
 search:



 Ali


I'm for it, but it would have to have the explicit caveat that it 
would only return a pointer to the *first* equal element in the 
list, as there may be duplicates. If we instead return a range, 
then suddenly we have `std.algorithm.find`.

Maybe `findSplit` should also have a specialization for 
`SortedRange` that uses `SortedRange.trisect`.
Jan 15 2014
prev sibling next sibling parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Wednesday, 15 January 2014 at 15:30:35 UTC, pplantinga wrote:

 In python, I really like the ability to check if an element is 
 in an array:

 if x in array:


 D has this, but only for associative arrays. Is there any 
 chance we could extend this to every kind of array?


import std.algorithm: canFind;

if(array.canFind(x))
     //do something


alternatively, something like this:

struct InWrapper(T)
{
     T unwrapped;
     alias unwrapped this;

     auto opBinaryRight(string op, T)(T el)
         if(op == "in")
     {
         import std.algorithm : canFind;
         return unwrapped.canFind(el);
     }
}

unittest
{
     InWrapper!(int[]) arr;
     arr = [1,2,3,4];

     assert(4 in arr);
     assert(!(5 in arr));
}
Jan 15 2014
parent reply "Meta" <jared771 gmail.com> writes:
On Wednesday, 15 January 2014 at 15:48:13 UTC, John Colvin wrote:

 On Wednesday, 15 January 2014 at 15:30:35 UTC, pplantinga wrote:

 In python, I really like the ability to check if an element is 
 in an array:

 if x in array:


 D has this, but only for associative arrays. Is there any 
 chance we could extend this to every kind of array?


 import std.algorithm: canFind;

 if(array.canFind(x))
     //do something


 alternatively, something like this:

 struct InWrapper(T)
 {
     T unwrapped;
     alias unwrapped this;

     auto opBinaryRight(string op, T)(T el)
         if(op == "in")
     {
         import std.algorithm : canFind;
         return unwrapped.canFind(el);
     }
 }

 unittest
 {
     InWrapper!(int[]) arr;
     arr = [1,2,3,4];

     assert(4 in arr);
     assert(!(5 in arr));
 }


auto inWrap(T)(T[] arr)
{
     static struct InWrapper
     {
         import std.typecons: Nullable;

         private T[] payload;

         Nullable!size_t opBinaryRight(string op: "in")(T val)
         {
             Nullable!size_t index;
             foreach (i, element; payload)
             {
                 if (element == val)
                 {
                     index = i;
					
					return index;
                 }
             }

             return index;
         }
     }

     return InWrapper(arr);
}

void main()
{
     auto arr = [0, 1, 2, 3, 4];
	auto i = 2 in arr.inWrap;
     assert(!i.isNull);
	assert(i == 2);
}
Jan 15 2014
parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
On Wednesday, 15 January 2014 at 17:13:37 UTC, Meta wrote:

 auto inWrap(T)(T[] arr)
 {
     static struct InWrapper
     {
         import std.typecons: Nullable;

         private T[] payload;

         Nullable!size_t opBinaryRight(string op: "in")(T val)
         {
             Nullable!size_t index;
             foreach (i, element; payload)
             {
                 if (element == val)
                 {
                     index = i;
 					
 					return index;
                 }
             }

             return index;
         }
     }

     return InWrapper(arr);
 }

 void main()
 {
     auto arr = [0, 1, 2, 3, 4];
 	auto i = 2 in arr.inWrap;
     assert(!i.isNull);
 	assert(i == 2);
 }


The in-operator should return T* for consistency with the 
build-in ones.
Jan 15 2014
next sibling parent reply "Namespace" <rswhite4 googlemail.com> writes:
On Wednesday, 15 January 2014 at 17:29:07 UTC, Tobias Pankrath 
wrote:

 On Wednesday, 15 January 2014 at 17:13:37 UTC, Meta wrote:

 auto inWrap(T)(T[] arr)
 {
    static struct InWrapper
    {
        import std.typecons: Nullable;

        private T[] payload;

        Nullable!size_t opBinaryRight(string op: "in")(T val)
        {
            Nullable!size_t index;
            foreach (i, element; payload)
            {
                if (element == val)
                {
                    index = i;
 					
 					return index;
                }
            }

            return index;
        }
    }

    return InWrapper(arr);
 }

 void main()
 {
    auto arr = [0, 1, 2, 3, 4];
 	auto i = 2 in arr.inWrap;
    assert(!i.isNull);
 	assert(i == 2);
 }


 The in-operator should return T* for consistency with the 
 build-in ones.


That was exactly my thoughts:

----
auto each(T)(T[] arr) pure nothrow {
     static struct InWrapper {
         private T[] payload;
		
         T* opBinaryRight(string op : "in")(T val) pure nothrow {
             foreach (ref T element; payload) {
				if (element == val)
					return &element;
             }

             return null;
         }
     }

     return InWrapper(arr);
}

void main() {
     int[] arr = [0, 1, 2, 3, 4];
     auto i = 2 in arr.each;
     assert(i !is null);
     assert(*i == 2);
}
----

Something like that should really be in std.array.
Jan 15 2014
parent "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Wednesday, 15 January 2014 at 17:33:27 UTC, Namespace wrote:

 Something like that should really be in std.array.


This is gratuitous operator overloading. We have 
std.algorithm.find that does this in an equally powerful but more 
transparent way.
Jan 15 2014
prev sibling parent "Brad Anderson" <eco gnuk.net> writes:
On Wednesday, 15 January 2014 at 17:29:07 UTC, Tobias Pankrath 
wrote:

 On Wednesday, 15 January 2014 at 17:13:37 UTC, Meta wrote:

 auto inWrap(T)(T[] arr)
 {
    static struct InWrapper
    {
        import std.typecons: Nullable;

        private T[] payload;

        Nullable!size_t opBinaryRight(string op: "in")(T val)
        {
            Nullable!size_t index;
            foreach (i, element; payload)
            {
                if (element == val)
                {
                    index = i;
 					
 					return index;
                }
            }

            return index;
        }
    }

    return InWrapper(arr);
 }

 void main()
 {
    auto arr = [0, 1, 2, 3, 4];
 	auto i = 2 in arr.inWrap;
    assert(!i.isNull);
 	assert(i == 2);
 }


 The in-operator should return T* for consistency with the 
 build-in ones.


I was thinking recently it'd be even more convenient if it 
returned std.typecons.Nullable. Then you get alias this and 
aren't having to constantly dereference it yourself.
Jan 15 2014
prev sibling parent reply luka8088 <luka8088 owave.net> writes:
On 15.1.2014. 16:30, pplantinga wrote:

 In python, I really like the ability to check if an element is in an array:
 
 if x in array:

 
 D has this, but only for associative arrays. Is there any chance we
 could extend this to every kind of array?


D array uses this operator for checking against array keys, not values.
Jan 15 2014
parent "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Thursday, 16 January 2014 at 07:28:43 UTC, luka8088 wrote:

 On 15.1.2014. 16:30, pplantinga wrote:

 In python, I really like the ability to check if an element is 
 in an array:
 
 if x in array:

 
 D has this, but only for associative arrays. Is there any 
 chance we
 could extend this to every kind of array?


 D array uses this operator for checking against array keys, not 
 values.


It makes sense for sorted arrays, as they make good sets.

That said, it makes the most sense to limit opBinaryRight!"in" to 
SortedRange.
Jan 16 2014