www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Asssociative Array by Key-Value-Pair

reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
Is there a combined property of AAs that combine keys and values 
typically

.pairs()

or

.byPairs()

I need to sort the elements of an AA by value and then retrieved 
corresponding keys in the order sorted.
Dec 15 2014
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Nordlöw:


 Is there a combined property of AAs that combine keys and 
 values typically

 .pairs()

 or

 .byPairs()

 I need to sort the elements of an AA by value and then 
 retrieved corresponding keys in the order sorted.


You can add an eager pairs() function to Phobos that returns an 
array of tuples.

byPairs can't be done in object.d for the dependency from tuples 
that aren't yet (and perhaps never) built-in in D, and it can't 
be done in Phobos because it needs access to unspecified runtime 
functions.

Bye,
bearophile
Dec 15 2014
next sibling parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
 You can add an eager pairs() function to Phobos that returns an 
 array of tuples.

 byPairs can't be done in object.d for the dependency from 
 tuples that aren't yet (and perhaps never) built-in in D, and 
 it can't be done in Phobos because it needs access to 
 unspecified runtime functions.

 Bye,
 bearophile


I think we should require byKeys and byValues to iterate the 
elements in the same order. Than we can just zip them for the 
pairwise iteration.

Would this impose a performance problem with the current 
implementation?
Dec 15 2014
parent reply ketmar via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
On Mon, 15 Dec 2014 17:37:13 +0000
Tobias Pankrath via Digitalmars-d-learn
<digitalmars-d-learn puremagic.com> wrote:


 I think we should require byKeys and byValues to iterate the=20
 elements in the same order. Than we can just zip them for the=20
 pairwise iteration.
=20
 Would this impose a performance problem with the current=20
 implementation?


i was always sure that they doing that in the same order. at least this
was true some time ago, but i see that runtime AA changed since, so i
don't sure if it works like this now. but i agree that this
requirement should be documented. and i bet it will not, 'cause this
will support principle of least astonishment, which is completely alien
for D.

the only way to get it into the specs is to write the useful library
that relies on that behavior and then scream "don't break our code,
it's regression!" then it eventually may be turned to requirement and
documented.
Dec 15 2014
next sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 12/15/14 12:52 PM, ketmar via Digitalmars-d-learn wrote:

 On Mon, 15 Dec 2014 17:37:13 +0000
 Tobias Pankrath via Digitalmars-d-learn
 <digitalmars-d-learn puremagic.com> wrote:


 I think we should require byKeys and byValues to iterate the
 elements in the same order. Than we can just zip them for the
 pairwise iteration.

 Would this impose a performance problem with the current
 implementation?


 i was always sure that they doing that in the same order. at least this
 was true some time ago, but i see that runtime AA changed since, so i
 don't sure if it works like this now.


It does work this way, the same structure and functions are used to do 
both byKey and byValue.


 but i agree that this
 requirement should be documented. and i bet it will not, 'cause this
 will support principle of least astonishment, which is completely alien
 for D.


Really? You done filling up that man with straw?

-Steve
Dec 15 2014
parent reply ketmar via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
On Mon, 15 Dec 2014 13:01:10 -0500
Steven Schveighoffer via Digitalmars-d-learn
<digitalmars-d-learn puremagic.com> wrote:


 but i agree that this
 requirement should be documented. and i bet it will not, 'cause this
 will support principle of least astonishment, which is completely alien
 for D.


=20
 Really? You done filling up that man with straw?


so it will be documented? that was the rhetorical question.
Dec 15 2014
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 12/15/14 1:10 PM, ketmar via Digitalmars-d-learn wrote:

 On Mon, 15 Dec 2014 13:01:10 -0500
 Steven Schveighoffer via Digitalmars-d-learn
 <digitalmars-d-learn puremagic.com> wrote:


 but i agree that this
 requirement should be documented. and i bet it will not, 'cause this
 will support principle of least astonishment, which is completely alien
 for D.


 Really? You done filling up that man with straw?


 so it will be documented? that was the rhetorical question.


Does it need to be? I don't see a reason for anyone to go out of their 
way to make the implementation inconsistent. Do you? The principal of 
least astonishment means that the least astonishing path is chosen. In 
this case, the least astonishing path has been chosen. Does it need 
documenting for you to believe it?

But my larger beef with your statement is that you assume D opts never 
to take that path, which is absolutely untrue.

-Steve
Dec 15 2014
next sibling parent ketmar via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
On Mon, 15 Dec 2014 13:47:58 -0500
Steven Schveighoffer via Digitalmars-d-learn
<digitalmars-d-learn puremagic.com> wrote:


 On 12/15/14 1:10 PM, ketmar via Digitalmars-d-learn wrote:

 On Mon, 15 Dec 2014 13:01:10 -0500
 Steven Schveighoffer via Digitalmars-d-learn
 <digitalmars-d-learn puremagic.com> wrote:


 but i agree that this
 requirement should be documented. and i bet it will not, 'cause this
 will support principle of least astonishment, which is completely ali=








en

 for D.


 Really? You done filling up that man with straw?


 so it will be documented? that was the rhetorical question.


=20
 Does it need to be? I don't see a reason for anyone to go out of their=20
 way to make the implementation inconsistent. Do you? The principal of=20
 least astonishment means that the least astonishing path is chosen. In=20
 this case, the least astonishing path has been chosen. Does it need=20
 documenting for you to believe it?
=20
 But my larger beef with your statement is that you assume D opts never=20
 to take that path, which is absolutely untrue.


maybe after five years of talking and after alot of people will relay
on the current behavior, it will be documented.
Dec 15 2014
prev sibling parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
 so it will be documented? that was the rhetorical question.


 Does it need to be? I don't see a reason for anyone to go out 
 of their way to make the implementation inconsistent. Do you?


At least I would prefer not to rely on undefined behaviour. If we 
ever do change the AA implementation in an inconsistent way, it 
will at least prevent the "but this code was broken all 
along"-argument.

On the other hand adding just one sentence to the documentation 
would cost us nothing.
Dec 16 2014
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 12/16/14 10:33 AM, Tobias Pankrath wrote:

 so it will be documented? that was the rhetorical question.


 Does it need to be? I don't see a reason for anyone to go out of their
 way to make the implementation inconsistent. Do you?


 At least I would prefer not to rely on undefined behaviour. If we ever
 do change the AA implementation in an inconsistent way, it will at least
 prevent the "but this code was broken all along"-argument.

 On the other hand adding just one sentence to the documentation would
 cost us nothing.


I can never ever see a reason to implement 2 different ways to traverse 
the elements, just to piss off people?

If you make a PR that adds that to documentation, I will pull it if it 
makes you feel better. I don't think it hurts, but don't think it's 
worth my time to make such a PR.

-Steve
Dec 16 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Tuesday, 16 December 2014 at 16:08:09 UTC, Steven 
Schveighoffer wrote:

 I can never ever see a reason to implement 2 different ways to 
 traverse the elements, just to piss off people?

 If you make a PR that adds that to documentation, I will pull 
 it if it makes you feel better. I don't think it hurts, but 
 don't think it's worth my time to make such a PR.

 -Steve


I can do PR for adding

https://github.com/nordlow/justd/blob/master/range_ex.d#L527

to Phobos.

Were should I put it/them?
Dec 16 2014
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 12/16/14 11:47 AM, "Nordlöw" wrote:

 On Tuesday, 16 December 2014 at 16:08:09 UTC, Steven Schveighoffer wrote:

 I can never ever see a reason to implement 2 different ways to
 traverse the elements, just to piss off people?

 If you make a PR that adds that to documentation, I will pull it if it
 makes you feel better. I don't think it hurts, but don't think it's
 worth my time to make such a PR.

 -Steve


 I can do PR for adding

 https://github.com/nordlow/justd/blob/master/range_ex.d#L527

 to Phobos.

 Were should I put it/them?


I think to be clear, the PR I said I will pull is for the documentation 
update. A doc change has no effect on the code.

I will certainly review one that adds iteration of both key and value 
(as that is pretty much a free addition given the existing code), but it 
will have to go through normal review process.

Note, the range you have referenced would not be accepted as it requires 
an unnecessary AA lookup for the value, and it requires access to phobos 
(this should be added to druntime). Take a look at object.di and see how 
the byKey and byValue ranges work. It would be trivial to add a byPair 
range (don't really like that name). The large controversy is regarding 
how it returns the "front" element.

It would have to satisfy 3 requirements I think:

1. I should be able to do foreach(k, v; r) on it.
2. I should be able to access both key and value separately for each 
element.
3. It cannot depend on phobos.

-Steve
Dec 16 2014
next sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Tuesday, 16 December 2014 at 16:56:20 UTC, Steven 
Schveighoffer wrote:

 I can do PR for adding

 https://github.com/nordlow/justd/blob/master/range_ex.d#L527

 to Phobos.

 Were should I put it/them?


 I think to be clear, the PR I said I will pull is for the 
 documentation update. A doc change has no effect on the code.

 I will certainly review one that adds iteration of both key and 
 value (as that is pretty much a free addition given the 
 existing code), but it will have to go through normal review 
 process.

 Note, the range you have referenced would not be accepted as it 
 requires an unnecessary AA lookup for the value, and it 
 requires access to phobos (this should be added to druntime). 
 Take a look at object.di and see how the byKey and byValue 
 ranges work. It would be trivial to add a byPair range (don't 
 really like that name). The large controversy is regarding how 
 it returns the "front" element.

 It would have to satisfy 3 requirements I think:

 1. I should be able to do foreach(k, v; r) on it.
 2. I should be able to access both key and value separately for 
 each element.
 3. It cannot depend on phobos.

 -Steve


Got it.
Dec 16 2014
prev sibling parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Tue, Dec 16, 2014 at 11:56:20AM -0500, Steven Schveighoffer via
Digitalmars-d-learn wrote:

 On 12/16/14 11:47 AM, "Nordlöw" wrote:

On Tuesday, 16 December 2014 at 16:08:09 UTC, Steven Schveighoffer wrote:

I can never ever see a reason to implement 2 different ways to
traverse the elements, just to piss off people?

If you make a PR that adds that to documentation, I will pull it if it
makes you feel better. I don't think it hurts, but don't think it's
worth my time to make such a PR.

-Steve


I can do PR for adding

https://github.com/nordlow/justd/blob/master/range_ex.d#L527

to Phobos.

Were should I put it/them?


 
 I think to be clear, the PR I said I will pull is for the
 documentation update. A doc change has no effect on the code.
 
 I will certainly review one that adds iteration of both key and value
 (as that is pretty much a free addition given the existing code), but
 it will have to go through normal review process.
 
 Note, the range you have referenced would not be accepted as it
 requires an unnecessary AA lookup for the value, and it requires
 access to phobos (this should be added to druntime). Take a look at
 object.di and see how the byKey and byValue ranges work. It would be
 trivial to add a byPair range (don't really like that name). The large
 controversy is regarding how it returns the "front" element.
 
 It would have to satisfy 3 requirements I think:
 
 1. I should be able to do foreach(k, v; r) on it.
 2. I should be able to access both key and value separately for each
 element.
 3. It cannot depend on phobos.


[...]

This has already been implemented, btw, but it was rejected because it
did not use Phobos' Tuple type for .front. The code is here:

	https://github.com/D-Programming-Language/druntime/pull/574

One possibility is that we resurrect this PR and also add a new Phobos
PR that wraps around .front to return Tuple instead (perhaps also rename
byPair to something else in the process).


T

-- 
One Word to write them all, One Access to find them, One Excel to count them
all, And thus to Windows bind them. -- Mike Champion
Dec 16 2014
parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Tuesday, 16 December 2014 at 17:47:18 UTC, H. S. Teoh via 
Digitalmars-d-learn wrote:

 also rename
 byPair to something else in the process).


What about by Python's byItem() and items()?
Dec 16 2014
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
ketmar:


 the only way to get it into the specs is to write the useful 
 library that relies on that behavior and then scream "don't
 break our code, it's regression!" then it eventually may be
 turned to requirement and documented.


This is a bad idea.

Bye,
bearophile
Dec 15 2014
parent ketmar via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
On Mon, 15 Dec 2014 18:42:11 +0000
bearophile via Digitalmars-d-learn <digitalmars-d-learn puremagic.com>
wrote:


 ketmar:
=20

 the only way to get it into the specs is to write the useful=20
 library that relies on that behavior and then scream "don't
 break our code, it's regression!" then it eventually may be
 turned to requirement and documented.


=20
 This is a bad idea.


this is a VERY BAD idea, but nothing else works. anything other will be
either rejected with random reason or talked to death.
Dec 15 2014
prev sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Monday, 15 December 2014 at 14:41:43 UTC, bearophile wrote:

 Nordlöw:


 Is there a combined property of AAs that combine keys and 
 values typically

 .pairs()

 or

 .byPairs()

 I need to sort the elements of an AA by value and then 
 retrieved corresponding keys in the order sorted.


 You can add an eager pairs() function to Phobos that returns an 
 array of tuples.

 byPairs can't be done in object.d for the dependency from 
 tuples that aren't yet (and perhaps never) built-in in D, and 
 it can't be done in Phobos because it needs access to 
 unspecified runtime functions.

 Bye,
 bearophile


Ok. Thanks.

Is

Tuple!(Key,Value)[] pairs(Key,Value)(Value[Key] aa);

a suitable contender for now?

I especially wonder about the mutability of parameter aa.

BTW: Why doesn't aa.byKey.map work?
Dec 15 2014
next sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Monday, 15 December 2014 at 22:58:43 UTC, Nordlöw wrote:

 Tuple!(Key,Value)[] pairs(Key,Value)(Value[Key] aa);

 a suitable contender for now?

 I especially wonder about the mutability of parameter aa.


More specifically is

https://github.com/nordlow/justd/blob/master/range_ex.d#L545

ok?
Dec 15 2014
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Nordlöw:


 BTW: Why doesn't aa.byKey.map work?


It currently works.

Bye,
bearophile
Dec 15 2014
parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Monday, 15 December 2014 at 23:21:44 UTC, bearophile wrote:

 Nordlöw:


 BTW: Why doesn't aa.byKey.map work?


 It currently works.

 Bye,
 bearophile


My mistake. Now both are at

https://github.com/nordlow/justd/blob/master/range_ex.d#L527
Dec 16 2014
prev sibling parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Mon, Dec 15, 2014 at 02:27:52PM +0000, "Nordlöw" via Digitalmars-d-learn
wrote:

 Is there a combined property of AAs that combine keys and values
 typically
 
 .pairs()
 
 or
 
 .byPairs()
 
 I need to sort the elements of an AA by value and then retrieved
 corresponding keys in the order sorted.


I implemented this before, but it got rejected because people insisted
that it must return a range of Tuple, but Tuple is defined in Phobos and
druntime can't have dependencies on Phobos. :-(

Maybe I'll take another shot at this, since this question keeps coming
up.


T

-- 
LINUX = Lousy Interface for Nefarious Unix Xenophobes.
Dec 15 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
H. S. Teoh:


 I implemented this before, but it got rejected because people 
 insisted
 that it must return a range of Tuple, but Tuple is defined in 
 Phobos and
 druntime can't have dependencies on Phobos. :-(

 Maybe I'll take another shot at this, since this question keeps 
 coming up.


One possible solution: have a hidden but documented runtime 
function that yields 2-item structs, and add a 
"std.range.byPairs" range and a "std.range.pairs" function to 
Phobos that yield the tuples (byPairs could use a cast to convert 
the runtime struct to the Phobos tuple).

Bye,
bearophile
Dec 15 2014
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
 One possible solution:


Another idea is to make "byPair" and "pairs" templates that by 
default return 2-structs and use a Tuple on request (so you have 
to import Phobos Tuple if you want them, so byPair doesn't depend 
on Phobos and you can put in druntime):

int[string] aa;
assert(aa.byPair.array == aa.pairs);

byPair yields something like:
struct Pair { string key; value int; }

Now this yields tuples:
assert(aa.byPair!Tuple.array == aa.pairs!Tuple);

Bye,
bearophile
Dec 15 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
 Now this yields tuples:
 assert(aa.byPair!Tuple.array == aa.pairs!Tuple);


But I'd really like tuples as built-ins for D -.- This is a 
work-around that cements the ugly Phobos tuples in the 
language... -.-

Bye,
bearophile
Dec 15 2014
parent reply "Meta" <jared771 gmail.com> writes:
On Monday, 15 December 2014 at 18:55:13 UTC, bearophile wrote:

 Now this yields tuples:
 assert(aa.byPair!Tuple.array == aa.pairs!Tuple);


 But I'd really like tuples as built-ins for D -.- This is a 
 work-around that cements the ugly Phobos tuples in the 
 language... -.-

 Bye,
 bearophile


Kenji has had a pull for full built-in Tuple support sitting in 
Github for years now 
(https://github.com/D-Programming-Language/dmd/pull/341). The 
syntax obviously won't work as it is, but that aside there's very 
little stopping built-in tuples in D.

Don't forget, he also made a DIP about it as well: 
http://forum.dlang.org/thread/mailman.372.1364547485.4724.digitalmars-d puremagic.com
Dec 15 2014
parent ketmar via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
On Mon, 15 Dec 2014 21:32:23 +0000
Meta via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> wrote:


 On Monday, 15 December 2014 at 18:55:13 UTC, bearophile wrote:

 Now this yields tuples:
 assert(aa.byPair!Tuple.array =3D=3D aa.pairs!Tuple);


 But I'd really like tuples as built-ins for D -.- This is a=20
 work-around that cements the ugly Phobos tuples in the=20
 language... -.-

 Bye,
 bearophile


=20
 Kenji has had a pull for full built-in Tuple support sitting in=20
 Github for years now=20
 (https://github.com/D-Programming-Language/dmd/pull/341). The=20
 syntax obviously won't work as it is, but that aside there's very=20
 little stopping built-in tuples in D.
=20
 Don't forget, he also made a DIP about it as well:=20
 http://forum.dlang.org/thread/mailman.372.1364547485.4724.digitalmars-d p=


uremagic.com

wow, thank you. i missed that PR and i really like it. will try to add
it to my patchset. ;-)
Dec 15 2014
prev sibling parent "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Mon, Dec 15, 2014 at 06:46:20PM +0000, bearophile via Digitalmars-d-learn
wrote:

 H. S. Teoh:
 

I implemented this before, but it got rejected because people
insisted that it must return a range of Tuple, but Tuple is defined
in Phobos and druntime can't have dependencies on Phobos. :-(

Maybe I'll take another shot at this, since this question keeps
coming up.


 
 One possible solution: have a hidden but documented runtime function
 that yields 2-item structs, and add a "std.range.byPairs" range and a
 "std.range.pairs" function to Phobos that yield the tuples (byPairs
 could use a cast to convert the runtime struct to the Phobos tuple).


[...]

That's exactly what I plan to do. :-)


T

-- 
Let's call it an accidental feature. -- Larry Wall
Dec 15 2014