www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Input Range addition to associative arrays

reply "Phil Lavoie" <maidenphil hotmail.com> writes:
Hi,

I am aware that you can iterate over associative arrays in 
multiple ways using the structure's opApply and different 
delegates returned by properties. I think adding a "range" 
property returning an input range to the associative array would 
benefit the users of the D language.

I'd like to justify this addition by pointing out that some 
standard library functional features, like filter, do not work on 
associative arrays as of right now. The reason for this is that 
filter returns a range that moves to the next appropriate value 
ON DEMAND rather than constructing the result. I think it is a 
great design choice. However, since no incremental (read on 
demand) iteration can be done on associative arrays, one cannot 
use features such as filter, nor make his own.

I think that the existing code can easily support such an 
addition, which makes it all the more attractive.

Imagine that "front()" would return an entry such that entry.key 
returns the key and entry.value returns the value. Here is an 
example of how one could use it:

float[ item ] itemsCost;
//Items whose price are lower than 5 dollars.
auto myFavoriteItems = filter!"a.value < 5.0"( itemsCost );
foreach( cheapItem; myFavoriteItems ) { 
theMoreComplicatedAlgorithmOnEarth( cheapItem); }

Now don't get me wrong, I am aware that you can do this multiple 
ways. It's just that ranges are so attractive in the way they 
"lazily" fetch values that it would make it easier to wrap 
associative arrays in struct that return relevant ranges based on 
the aa's content of constructing the result, than returning the 
range/or result. I also think it would merge well with D's way of 
doing things.

What are your thoughts?
Dec 06 2012
next sibling parent "Phil Lavoie" <maidenphil hotmail.com> writes:
 It's just that ranges are so attractive in the way they 
 "lazily" fetch values that it would make it easier to wrap 
 associative arrays in struct that return relevant ranges based 
 on the aa's content of constructing the result, than returning 
 the range/or result.


Typos, read:
It's just that ranges are so attractive in the
way they "lazily" fetch values that it would make it easier to
wrap associative arrays in struct that return relevant ranges
based on the aa's content INSTEAD of constructing the result, THEN
returning a range/or said result (which implies the decision of 
what structure holds the result, rather than just delegating this 
part to the person using the struct).
Dec 06 2012
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/6/12 2:03 PM, Phil Lavoie wrote:

 Hi,

 I am aware that you can iterate over associative arrays in multiple ways
 using the structure's opApply and different delegates returned by
 properties. I think adding a "range" property returning an input range
 to the associative array would benefit the users of the D language.


[snip]

 What are your thoughts?


I also think we should add a forward range interface to AAs.

Andrei
Dec 06 2012
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 6 December 2012 at 20:43:06 UTC, Andrei Alexandrescu 
wrote:

 On 12/6/12 2:03 PM, Phil Lavoie wrote:

 Hi,

 I am aware that you can iterate over associative arrays in 
 multiple ways
 using the structure's opApply and different delegates returned 
 by
 properties. I think adding a "range" property returning an 
 input range
 to the associative array would benefit the users of the D 
 language.


 [snip]

 What are your thoughts?


 I also think we should add a forward range interface to AAs.

 Andrei


input -> forward

...

Why stop there when you can have bidirectional?
Dec 06 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/6/12 3:51 PM, monarch_dodra wrote:

 On Thursday, 6 December 2012 at 20:43:06 UTC, Andrei Alexandrescu wrote:

 On 12/6/12 2:03 PM, Phil Lavoie wrote:

 Hi,

 I am aware that you can iterate over associative arrays in multiple ways
 using the structure's opApply and different delegates returned by
 properties. I think adding a "range" property returning an input range
 to the associative array would benefit the users of the D language.


 [snip]

 What are your thoughts?


 I also think we should add a forward range interface to AAs.

 Andrei


 input -> forward

 ...

 Why stop there when you can have bidirectional?


We wouldn't want to impose too much on the implementation (e.g. doubly- 
instead of singly-linked lists for collision handling).

Andrei
Dec 06 2012
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 6 December 2012 at 21:10:37 UTC, Andrei Alexandrescu 
wrote:

 On 12/6/12 3:51 PM, monarch_dodra wrote:

 On Thursday, 6 December 2012 at 20:43:06 UTC, Andrei 
 Alexandrescu wrote:

 On 12/6/12 2:03 PM, Phil Lavoie wrote:

 Hi,

 I am aware that you can iterate over associative arrays in 
 multiple ways
 using the structure's opApply and different delegates 
 returned by
 properties. I think adding a "range" property returning an 
 input range
 to the associative array would benefit the users of the D 
 language.


 [snip]

 What are your thoughts?


 I also think we should add a forward range interface to AAs.

 Andrei


 input -> forward

 ...

 Why stop there when you can have bidirectional?


 We wouldn't want to impose too much on the implementation (e.g. 
 doubly- instead of singly-linked lists for collision handling).

 Andrei


Oh yeah... Good point.
Dec 06 2012
parent reply "Phil Lavoie" <maidenphil hotmail.com> writes:
Cool, I can see that we all (us three) agree then! Now, I am new 
to this forum (and forums in general in fact) and I am unaware if 
there is a different approach for suggesting changes (that are 
not bugs) to the D language/runtime. Should I submit a form of 
some sort elsewhere or will mentioning it here suffice?

Thanks
Dec 06 2012
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 6 December 2012 at 21:56:34 UTC, Phil Lavoie wrote:

 Cool, I can see that we all (us three) agree then! Now, I am 
 new to this forum (and forums in general in fact) and I am 
 unaware if there is a different approach for suggesting changes 
 (that are not bugs) to the D language/runtime. Should I submit 
 a form of some sort elsewhere or will mentioning it here 
 suffice?

 Thanks


You can submit an "Enhancement request" in the bug tracker 
(http://d.puremagic.com/issues/enter_bug.cgi). While we all agree 
the change would be good, no one has yet stepped up to say they'd 
implement it.

By creating an entry in the bug tracker, you are creating a 
permanent entry for the desired change. Someone might happen 
along and actually do it.
Dec 06 2012
parent "Phil Lavoie" <maidenphil hotmail.com> writes:
All right, thanks for your reply buddy!
Dec 06 2012
prev sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 12/06/2012 11:03 AM, Phil Lavoie wrote:

 Hi,

 I am aware that you can iterate over associative arrays in multiple ways
 using the structure's opApply and different delegates returned by
 properties. I think adding a "range" property returning an input range
 to the associative array would benefit the users of the D language.

 I'd like to justify this addition by pointing out that some standard
 library functional features, like filter, do not work on associative
 arrays as of right now. The reason for this is that filter returns a
 range that moves to the next appropriate value ON DEMAND rather than
 constructing the result. I think it is a great design choice. However,
 since no incremental (read on demand) iteration can be done on
 associative arrays, one cannot use features such as filter, nor make his
 own.

 I think that the existing code can easily support such an addition,
 which makes it all the more attractive.

 Imagine that "front()" would return an entry such that entry.key returns
 the key and entry.value returns the value. Here is an example of how one
 could use it:

 float[ item ] itemsCost;
 //Items whose price are lower than 5 dollars.
 auto myFavoriteItems = filter!"a.value < 5.0"( itemsCost );
 foreach( cheapItem; myFavoriteItems ) {
 theMoreComplicatedAlgorithmOnEarth( cheapItem); }

 Now don't get me wrong, I am aware that you can do this multiple ways.
 It's just that ranges are so attractive in the way they "lazily" fetch
 values that it would make it easier to wrap associative arrays in struct
 that return relevant ranges based on the aa's content of constructing
 the result, than returning the range/or result. I also think it would
 merge well with D's way of doing things.

 What are your thoughts?


Makes sense.

Here is a quick and dirty implementation that is based on the assumption 
that byKey and byValue visit the elements in the same order:

import std.stdio;
import std.traits;
import std.algorithm;
import std.array;

struct Element(K, V)
{
     K key;
     V value;
}

struct ByElement(AA)
{
     alias typeof(AA.byKey()) KeyRange;
     alias typeof(AA.byValue()) ValueRange;
     alias Element!(KeyType!AA, ValueType!AA) ElementType;

     KeyRange keys;
     ValueRange values;

     this(AA aa)
     {
         this.keys = aa.byKey();
         this.values = aa.byValue();
     }

     bool empty() const  property
     {
         return keys.empty;
     }

     ElementType front() /* const */  property
     {
         return ElementType(keys.front, values.front);
     }

     void popFront()
     {
         keys.popFront;
         values.popFront;
     }

     ByElement save()
     {
         return this;
     }
}

ByElement!AA byElement(AA)(AA aa)
{
     return ByElement!AA(aa);
}

void main()
{
     auto aa = [ "one" : 1, "two" : 2, "three" : 3, "four" : 4, "five" : 
5 ];

     writeln(aa
             .byElement
             .filter!(a => a.value % 2)
             .filter!(a => a.key.front == 'o'));
}

Ali
Dec 06 2012
next sibling parent reply "Phil Lavoie" <maidenphil hotmail.com> writes:
I tested your code and it seems to work correctly. However, what 
I find troubling is that I would never have thought of trying 
this out. This is because those two properties are said to return 
DELEGATES, according to this page: 
http://dlang.org/hash-map.html, but it does not seem to be 
correct. Now, I had a look at those properties' implementation 
and found out that they, in fact, return ranges, which 
contradicts documentation :(. I think it is safe to assume that  
both byValue and byKey return results in the same order, given 
that they use the same underlying range struct for popFront() and 
empty(). Thank you for pointing this out.
Dec 07 2012
parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 12/07/2012 07:40 AM, Phil Lavoie wrote:


 I tested your code and it seems to work correctly.


As bearophile also pointed out, it is based on an assumption that may be 
incorrect on obscure system ;) but it is trivial to fix. One way is by 
storing the original aa and doing a lookup of the value:

     ElementType front() /* const */  property
     {
         return ElementType(keys.front, aa[keys.front]);
     }


 However, what I find
 troubling is that I would never have thought of trying this out. This is
 because those two properties are said to return DELEGATES, according to
 this page: http://dlang.org/hash-map.html


That is a documentation bug. Please improve it by either using the 
"Improve this page" button on that page or by filing a bug report at 
http://d.puremagic.com/issues/enter_bug.cgi

Thank you,
Ali
Dec 07 2012
prev sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Ali Çehreli:


 Here is a quick and dirty implementation that is based on the 
 assumption that byKey and byValue visit the elements in the 
 same order:


I think that currently the D specs do not assert that quality of 
byKey/byValue. So your code is not portable.

Bye,
bearophile
Dec 07 2012