www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - DIP67: Associative Ranges

reply "Freddy" <Hexagonalstar64 gmail.com> writes:
http://wiki.dlang.org/DIP67
Abstraction over the build-in associative array(one type of range
for containers and another type for dynamic generators).
Plese criticize.
Oct 28 2014
next sibling parent reply "Brad Anderson" <eco gnuk.net> writes:
On Tuesday, 28 October 2014 at 22:44:32 UTC, Freddy wrote:

 http://wiki.dlang.org/DIP67
 Abstraction over the build-in associative array(one type of 
 range
 for containers and another type for dynamic generators).
 Plese criticize.


It's kind of a weird proposal to be honest. Ranges primitives are
normally things like popFront(), front, and empty. The primitives
here are methods that return other ranges.

I'd think an associative range would be one that had something
like frontKey and frontValue. Alternatively it could be anything
with a front which is a 2-element tuple  (a lot like how C++'s
associative iterators have a std::pair<KeyTy, ValueTy>
value_type) but tuples aren't in druntime so that'd be a problem.

I've always found byKey and byValue odd because you rarely want
to iterate through an associative array without having both the
key and the value on hand. Doing byKey requires you to do a
lookup to get the corresponding value which just takes up cycles
unnecessarily. It also makes multimaps, if we ever support them,
a bit problematic (that is, associative arrays which support
storing a key more than once).
Oct 28 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Brad Anderson:


 you rarely want
 to iterate through an associative array without having both the
 key and the value on hand.


This is very false. I have tons of cases where you only iterate 
on values or keys. On the other hand I have suggested several 
times that I'd like a byPairs (that yields keys-values tuple 
pairs).



 Doing byKey requires you to do a
 lookup to get the corresponding value which just takes up cycles
 unnecessarily.


Usually people use a "AA.byKey.zip(AA.byValue)" that is not 
reliable.

Bye,
bearophile
Oct 28 2014
parent reply "Brad Anderson" <eco gnuk.net> writes:
On Wednesday, 29 October 2014 at 06:59:09 UTC, bearophile wrote:

 This is very false. I have tons of cases where you only iterate 
 on values or keys. On the other hand I have suggested several 
 times that I'd like a byPairs (that yields keys-values tuple 
 pairs).


It happens to me too but it's very much a minority of uses. 
Having sets as well as maps would help replace some of these 
cases. Not all, of course.


 Doing byKey requires you to do a
 lookup to get the corresponding value which just takes up 
 cycles
 unnecessarily.


 Usually people use a "AA.byKey.zip(AA.byValue)" that is not 
 reliable.


Better than doing key lookups on every iteration but awfully ugly 
and should be unnecessary. byPairs sounds good.
Oct 29 2014
parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Wed, Oct 29, 2014 at 05:23:07PM +0000, Brad Anderson via Digitalmars-d wrote:

 On Wednesday, 29 October 2014 at 06:59:09 UTC, bearophile wrote:

This is very false. I have tons of cases where you only iterate on
values or keys. On the other hand I have suggested several times that
I'd like a byPairs (that yields keys-values tuple pairs).


 
 It happens to me too but it's very much a minority of uses. Having
 sets as well as maps would help replace some of these cases. Not all,
 of course.
 

Doing byKey requires you to do a lookup to get the corresponding
value which just takes up cycles unnecessarily.


Usually people use a "AA.byKey.zip(AA.byValue)" that is not reliable.


 
 Better than doing key lookups on every iteration but awfully ugly and
 should be unnecessary. byPairs sounds good.


I've submitted a PR for byPair before, but it was roadblocked by the
fact that people demand that it return std.typecons.Tuple, yet we're not
allowed to import Phobos in druntime. Other than this IMO nitpicky
issue, the code was already all ready to go many moons ago.


T

-- 
We are in class, we are supposed to be learning, we have a teacher... Is it too
much that I expect him to teach me??? -- RL
Oct 29 2014
parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Wednesday, 29 October 2014 at 17:36:41 UTC, H. S. Teoh via 
Digitalmars-d wrote:

 On Wed, Oct 29, 2014 at 05:23:07PM +0000, Brad Anderson via 
 Digitalmars-d wrote:

 On Wednesday, 29 October 2014 at 06:59:09 UTC, bearophile 
 wrote:

This is very false. I have tons of cases where you only 
iterate on
values or keys. On the other hand I have suggested several 
times that
I'd like a byPairs (that yields keys-values tuple pairs).


 
 It happens to me too but it's very much a minority of uses. 
 Having
 sets as well as maps would help replace some of these cases. 
 Not all,
 of course.
 

Doing byKey requires you to do a lookup to get the 
corresponding
value which just takes up cycles unnecessarily.


Usually people use a "AA.byKey.zip(AA.byValue)" that is not 
reliable.


 
 Better than doing key lookups on every iteration but awfully 
 ugly and
 should be unnecessary. byPairs sounds good.


 I've submitted a PR for byPair before, but it was roadblocked 
 by the
 fact that people demand that it return std.typecons.Tuple, yet 
 we're not
 allowed to import Phobos in druntime. Other than this IMO 
 nitpicky
 issue, the code was already all ready to go many moons ago.


 T


Can byPair be implemented in phobos, or does it need to access 
private/package stuff in druntime?
Oct 29 2014
parent reply "Freddy" <Hexagonalstar64 gmail.com> writes:
On Wednesday, 29 October 2014 at 18:04:30 UTC, John Colvin wrote:

 On Wednesday, 29 October 2014 at 17:36:41 UTC, H. S. Teoh via 
 Digitalmars-d wrote:

 On Wed, Oct 29, 2014 at 05:23:07PM +0000, Brad Anderson via 
 Digitalmars-d wrote:

 On Wednesday, 29 October 2014 at 06:59:09 UTC, bearophile 
 wrote:

This is very false. I have tons of cases where you only 
iterate on
values or keys. On the other hand I have suggested several 
times that
I'd like a byPairs (that yields keys-values tuple pairs).


 
 It happens to me too but it's very much a minority of uses. 
 Having
 sets as well as maps would help replace some of these cases. 
 Not all,
 of course.
 

Doing byKey requires you to do a lookup to get the 
corresponding
value which just takes up cycles unnecessarily.


Usually people use a "AA.byKey.zip(AA.byValue)" that is not 
reliable.


 
 Better than doing key lookups on every iteration but awfully 
 ugly and
 should be unnecessary. byPairs sounds good.


 I've submitted a PR for byPair before, but it was roadblocked 
 by the
 fact that people demand that it return std.typecons.Tuple, yet 
 we're not
 allowed to import Phobos in druntime. Other than this IMO 
 nitpicky
 issue, the code was already all ready to go many moons ago.


 T


 Can byPair be implemented in phobos, or does it need to access 
 private/package stuff in druntime?


I don't see why not,It could be put into std.range and accept a
generic associative range(which includes the build-in associative
array).
Oct 29 2014
next sibling parent "Freddy" <Hexagonalstar64 gmail.com> writes:
On Wednesday, 29 October 2014 at 18:40:51 UTC, Freddy wrote:

 On Wednesday, 29 October 2014 at 18:04:30 UTC, John Colvin 
 wrote:

 On Wednesday, 29 October 2014 at 17:36:41 UTC, H. S. Teoh via 
 Digitalmars-d wrote:

 On Wed, Oct 29, 2014 at 05:23:07PM +0000, Brad Anderson via 
 Digitalmars-d wrote:

 On Wednesday, 29 October 2014 at 06:59:09 UTC, bearophile 
 wrote:

This is very false. I have tons of cases where you only 
iterate on
values or keys. On the other hand I have suggested several 
times that
I'd like a byPairs (that yields keys-values tuple pairs).


 
 It happens to me too but it's very much a minority of uses. 
 Having
 sets as well as maps would help replace some of these cases. 
 Not all,
 of course.
 

Doing byKey requires you to do a lookup to get the 
corresponding
value which just takes up cycles unnecessarily.


Usually people use a "AA.byKey.zip(AA.byValue)" that is not 
reliable.


 
 Better than doing key lookups on every iteration but awfully 
 ugly and
 should be unnecessary. byPairs sounds good.


 I've submitted a PR for byPair before, but it was roadblocked 
 by the
 fact that people demand that it return std.typecons.Tuple, 
 yet we're not
 allowed to import Phobos in druntime. Other than this IMO 
 nitpicky
 issue, the code was already all ready to go many moons ago.


 T


 Can byPair be implemented in phobos, or does it need to access 
 private/package stuff in druntime?


 I don't see why not,It could be put into std.range and accept a
 generic associative range(which includes the build-in 
 associative
 array).


or std.array.
Oct 29 2014
prev sibling parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Wed, Oct 29, 2014 at 06:40:50PM +0000, Freddy via Digitalmars-d wrote:

 On Wednesday, 29 October 2014 at 18:04:30 UTC, John Colvin wrote:

On Wednesday, 29 October 2014 at 17:36:41 UTC, H. S. Teoh via
Digitalmars-d wrote:




[...]

I've submitted a PR for byPair before, but it was roadblocked by the
fact that people demand that it return std.typecons.Tuple, yet we're
not allowed to import Phobos in druntime. Other than this IMO
nitpicky issue, the code was already all ready to go many moons ago.


T


Can byPair be implemented in phobos, or does it need to access
private/package stuff in druntime?


 
 I don't see why not,It could be put into std.range and accept a
 generic associative range(which includes the build-in associative
 array).


And how would it be implemented in a way that is stable across AA
implementations?


--T
Oct 29 2014
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
H. S. Teoh:


 And how would it be implemented in a way that is stable across 
 AA implementations?


Adding tuples as first-class entities in the language, and 
deprecating std.typecons.Tuple :-)

Bye,
bearophile
Oct 29 2014
prev sibling parent reply "Freddy" <Hexagonalstar64 gmail.com> writes:
On Wednesday, 29 October 2014 at 19:55:14 UTC, H. S. Teoh via
Digitalmars-d wrote:

 On Wed, Oct 29, 2014 at 06:40:50PM +0000, Freddy via 
 Digitalmars-d wrote:

 On Wednesday, 29 October 2014 at 18:04:30 UTC, John Colvin 
 wrote:

On Wednesday, 29 October 2014 at 17:36:41 UTC, H. S. Teoh via
Digitalmars-d wrote:




 [...]

I've submitted a PR for byPair before, but it was 
roadblocked by the
fact that people demand that it return std.typecons.Tuple, 
yet we're
not allowed to import Phobos in druntime. Other than this IMO
nitpicky issue, the code was already all ready to go many 
moons ago.


T


Can byPair be implemented in phobos, or does it need to access
private/package stuff in druntime?


 
 I don't see why not,It could be put into std.range and accept a
 generic associative range(which includes the build-in 
 associative
 array).


 And how would it be implemented in a way that is stable across 
 AA
 implementations?


 --T


in std.range
----
auto byKeyPair(R)(R r) if(isAssociativeRange!R){
	return zip(r.byKey,r.byValue);
}
----
Although it will not be possible for lazy associative ranges
because they don't allow iteration
b.t.w should I add this to by PR?
Oct 29 2014
parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Wed, Oct 29, 2014 at 11:33:53PM +0000, Freddy via Digitalmars-d wrote:

 On Wednesday, 29 October 2014 at 19:55:14 UTC, H. S. Teoh via
 Digitalmars-d wrote:


[...]

And how would it be implemented in a way that is stable across AA
implementations?


--T


 in std.range
 ----
 auto byKeyPair(R)(R r) if(isAssociativeRange!R){
 	return zip(r.byKey,r.byValue);
 }
 ----


This is not stable across AA implementations.  There is no guarantee
that byKey and byValue will return elements in the same order. The
current implementation does, but it's a shaky assumption.

Besides, it wastefully keeps two iterators over the AA, whereas a proper
native implementation would only need a single one.

In any case, this is a backwards approach. What we *should* have started
with, is an iteration over key/value pairs, with byKey and byValue
implemented on top of that, rather than the other way round.

If it weren't for the std.typecons.Tuple issue, we'd already have a
proper AA byPair by now. But perhaps there is a way to work around this,
if the AA interface can export a "raw" iteration function that can be
wrapped in Phobos to produce a range of key/value Tuples... It wouldn't
be the prettiest solution, but might be the best we can do right now
since we can't import Phobos from druntime.


T

-- 
Windows 95 was a joke, and Windows 98 was the punchline.
Oct 29 2014
parent "Xinok" <xinok live.com> writes:
On Thursday, 30 October 2014 at 00:10:47 UTC, H. S. Teoh via 
Digitalmars-d wrote:

 On Wed, Oct 29, 2014 at 11:33:53PM +0000, Freddy via 
 Digitalmars-d wrote:

 On Wednesday, 29 October 2014 at 19:55:14 UTC, H. S. Teoh via
 Digitalmars-d wrote:


 [...]

And how would it be implemented in a way that is stable 
across AA
implementations?


--T


 in std.range
 ----
 auto byKeyPair(R)(R r) if(isAssociativeRange!R){
 	return zip(r.byKey,r.byValue);
 }
 ----


 This is not stable across AA implementations.  There is no 
 guarantee
 that byKey and byValue will return elements in the same order. 
 The
 current implementation does, but it's a shaky assumption.


It's already covered by the DIP. Simply, it's one of the 
requirements of an associative range: "byKey and byValue must be 
align to the same Pair when iterating." While the compiler can't 
enforce this, there are many things about ranges which the 
compiler is unable to check, so we merely expect the 
implementation to follow the rules.


 Besides, it wastefully keeps two iterators over the AA, whereas 
 a proper
 native implementation would only need a single one.

 In any case, this is a backwards approach. What we *should* 
 have started
 with, is an iteration over key/value pairs, with byKey and 
 byValue
 implemented on top of that, rather than the other way round.

 If it weren't for the std.typecons.Tuple issue, we'd already 
 have a
 proper AA byPair by now. But perhaps there is a way to work 
 around this,
 if the AA interface can export a "raw" iteration function that 
 can be
 wrapped in Phobos to produce a range of key/value Tuples... It 
 wouldn't
 be the prettiest solution, but might be the best we can do 
 right now
 since we can't import Phobos from druntime.


 T
Oct 29 2014
prev sibling next sibling parent "Freddy" <Hexagonalstar64 gmail.com> writes:
On Tuesday, 28 October 2014 at 22:44:32 UTC, Freddy wrote:

 http://wiki.dlang.org/DIP67
 Abstraction over the build-in associative array(one type of 
 range
 for containers and another type for dynamic generators).
 Plese criticize.


Does any one now a better way to implement lazy associative
ranges other than my KeyType and ValueType hack?
Oct 29 2014
prev sibling parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Tuesday, 28 October 2014 at 22:44:32 UTC, Freddy wrote:

 http://wiki.dlang.org/DIP67
 Abstraction over the build-in associative array(one type of 
 range
 for containers and another type for dynamic generators).
 Plese criticize.


Any examples of what this actually accomplishes? Maybe an example 
of an algorithm that can do something useful with these 
primitives? A rationale for why these are the chosen primitives?

As the proposed "associative range" isn't consumable like other 
ranges, this seems more like a specific kind of *container*, not 
a *range*; indeed the text of the DIP seems to conflate the 
concepts, but they are separate by necessity.

Note that opIndex and opBinaryRight are already container 
primitives (see std.container). There's also the additional 
relevant primitive `removeKey`. Beyond that though, associative 
containers could need some more fleshing out in the container 
concept.

As it is, I think this proposal suffers both from lack of 
substance and confusing terminology.
Oct 31 2014
next sibling parent "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Saturday, 1 November 2014 at 00:04:18 UTC, Jakob Ovrum wrote:

 ... opIndex and opBinaryRight are already container ...


Correction: opBinaryRight!"in"
Oct 31 2014
prev sibling next sibling parent "Freddy" <Hexagonalstar64 gmail.com> writes:
On Saturday, 1 November 2014 at 00:04:18 UTC, Jakob Ovrum wrote:

 On Tuesday, 28 October 2014 at 22:44:32 UTC, Freddy wrote:

 http://wiki.dlang.org/DIP67
 Abstraction over the build-in associative array(one type of 
 range
 for containers and another type for dynamic generators).
 Plese criticize.


 Any examples of what this actually accomplishes? Maybe an 
 example of an algorithm that can do something useful with these 
 primitives? A rationale for why these are the chosen primitives?

 As the proposed "associative range" isn't consumable like other 
 ranges, this seems more like a specific kind of *container*, 
 not a *range*; indeed the text of the DIP seems to conflate the 
 concepts, but they are separate by necessity.

 Note that opIndex and opBinaryRight are already container 
 primitives (see std.container). There's also the additional 
 relevant primitive `removeKey`. Beyond that though, associative 
 containers could need some more fleshing out in the container 
 concept.

 As it is, I think this proposal suffers both from lack of 
 substance and confusing terminology.


The pull request has already been denied. I didn't know about
std.container's definitions.

They can't be consumable, built-in associative arrays overload
foreach(key,value;array) adding input range primitives would
conflict.
Oct 31 2014
prev sibling parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Sat, Nov 01, 2014 at 12:04:16AM +0000, Jakob Ovrum via Digitalmars-d wrote:

 On Tuesday, 28 October 2014 at 22:44:32 UTC, Freddy wrote:

http://wiki.dlang.org/DIP67
Abstraction over the build-in associative array(one type of range
for containers and another type for dynamic generators).
Plese criticize.


 
 Any examples of what this actually accomplishes? Maybe an example of
 an algorithm that can do something useful with these primitives? A
 rationale for why these are the chosen primitives?
 
 As the proposed "associative range" isn't consumable like other
 ranges, this seems more like a specific kind of *container*, not a
 *range*; indeed the text of the DIP seems to conflate the concepts,
 but they are separate by necessity.
 
 Note that opIndex and opBinaryRight are already container primitives
 (see std.container). There's also the additional relevant primitive
 `removeKey`.  Beyond that though, associative containers could need
 some more fleshing out in the container concept.
 
 As it is, I think this proposal suffers both from lack of substance
 and confusing terminology.


I think a better name would be "associative array concept" rather than
"associative range".

Basically, this DIP is proposing a set of primitives that can be used to
identify some given type as AA-like, so that generic code that expect
AA-like objects would be able to work with any type that implements the
expected interface. Ostensibly, one could then implement generic
algorithms that work with AA-like objects.

It's not a bad idea, really, except perhaps for the name. And the API
could use more careful thought to boil it down to the essentials, rather
than throwing in everything current AA syntax supports, just because AA
syntax supports it. If we can boil down AA's and AA-like types into a
small but expressive set of primitive operations, it could turn out to
be a very useful abstraction that generic code could use. The current AA
syntactic sugar can then be implemented in terms of the minimal
primitives, and one could easily build AA-like objects by implementing
the primitives, and automatically get all the syntactic sugar "for free"
via UFCS and so on.


T

-- 
Why waste time reinventing the wheel, when you could be reinventing the engine?
-- Damian Conway
Oct 31 2014