digitalmars.D - DIP67: Associative Ranges
- Freddy (4/4) Oct 28 2014 http://wiki.dlang.org/DIP67
- Brad Anderson (16/21) Oct 28 2014 It's kind of a weird proposal to be honest. Ranges primitives are
- bearophile (9/15) Oct 28 2014 This is very false. I have tons of cases where you only iterate
- Brad Anderson (6/16) Oct 29 2014 It happens to me too but it's very much a minority of uses.
- H. S. Teoh via Digitalmars-d (8/26) Oct 29 2014 I've submitted a PR for byPair before, but it was roadblocked by the
- John Colvin (4/40) Oct 29 2014 Can byPair be implemented in phobos, or does it need to access
- Freddy (4/47) Oct 29 2014 I don't see why not,It could be put into std.range and accept a
- Freddy (2/52) Oct 29 2014 or std.array.
- H. S. Teoh via Digitalmars-d (5/22) Oct 29 2014 And how would it be implemented in a way that is stable across AA
- bearophile (5/7) Oct 29 2014 Adding tuples as first-class entities in the language, and
- Freddy (11/40) Oct 29 2014 in std.range
- H. S. Teoh via Digitalmars-d (19/32) Oct 29 2014 This is not stable across AA implementations. There is no guarantee
- Xinok (8/50) Oct 29 2014 It's already covered by the DIP. Simply, it's one of the
- Freddy (3/8) Oct 29 2014 Does any one now a better way to implement lazy associative
- Jakob Ovrum (15/20) Oct 31 2014 Any examples of what this actually accomplishes? Maybe an example
- Jakob Ovrum (2/3) Oct 31 2014 Correction: opBinaryRight!"in"
- Freddy (6/26) Oct 31 2014 The pull request has already been denied. I didn't know about
- H. S. Teoh via Digitalmars-d (21/43) Oct 31 2014 I think a better name would be "associative array concept" rather than
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
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
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
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.Better than doing key lookups on every iteration but awfully ugly and should be unnecessary. byPairs sounds good.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.
Oct 29 2014
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: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??? -- RLThis 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.Better than doing key lookups on every iteration but awfully ugly and should be unnecessary. byPairs sounds good.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.
Oct 29 2014
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:Can byPair be implemented in phobos, or does it need to access private/package stuff in druntime?On Wednesday, 29 October 2014 at 06:59:09 UTC, bearophile 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. TThis 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.Better than doing key lookups on every iteration but awfully ugly and should be unnecessary. byPairs sounds good.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.
Oct 29 2014
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 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).On Wed, Oct 29, 2014 at 05:23:07PM +0000, Brad Anderson via Digitalmars-d wrote:Can byPair be implemented in phobos, or does it need to access private/package stuff in druntime?On Wednesday, 29 October 2014 at 06:59:09 UTC, bearophile 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. TThis 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.Better than doing key lookups on every iteration but awfully ugly and should be unnecessary. byPairs sounds good.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.
Oct 29 2014
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:or std.array.On Wednesday, 29 October 2014 at 17:36:41 UTC, H. S. Teoh via Digitalmars-d wrote: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).On Wed, Oct 29, 2014 at 05:23:07PM +0000, Brad Anderson via Digitalmars-d wrote:Can byPair be implemented in phobos, or does it need to access private/package stuff in druntime?On Wednesday, 29 October 2014 at 06:59:09 UTC, bearophile 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. TThis 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.Better than doing key lookups on every iteration but awfully ugly and should be unnecessary. byPairs sounds good.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.
Oct 29 2014
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:And how would it be implemented in a way that is stable across AA implementations? --TI 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).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. TCan byPair be implemented in phobos, or does it need to access private/package stuff in druntime?
Oct 29 2014
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
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: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?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:And how would it be implemented in a way that is stable across AA implementations? --TI 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).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. TCan byPair be implemented in phobos, or does it need to access private/package stuff in druntime?
Oct 29 2014
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:[...]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.And how would it be implemented in a way that is stable across AA implementations? --Tin std.range ---- auto byKeyPair(R)(R r) if(isAssociativeRange!R){ return zip(r.byKey,r.byValue); } ----
Oct 29 2014
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: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.On Wednesday, 29 October 2014 at 19:55:14 UTC, H. S. Teoh via Digitalmars-d wrote:[...]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.And how would it be implemented in a way that is stable across AA implementations? --Tin std.range ---- auto byKeyPair(R)(R r) if(isAssociativeRange!R){ return zip(r.byKey,r.byValue); } ----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
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
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
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
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: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.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
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: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 Conwayhttp://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