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, "Nordlw" 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, "Nordlw" 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