digitalmars.D - Associative Ranges
- Freddy (4/4) Aug 01 2014 I just curious, do Associative Ranges exist. If so where can i
- Xinok (3/7) Aug 02 2014 Unfortunately not, but I do wonder if we should generalize an
- bearophile (4/6) Aug 02 2014 First of all you need some use cases and usage examples.
- Freddy (3/7) Aug 02 2014 I started a phobos fork for this, what do you think so far
- "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> (14/21) Aug 03 2014 Nice!
- Freddy (5/26) Aug 03 2014 Alright i fixed it, although should the implict range be a
- Freddy (3/24) Aug 03 2014 Also won't the implicit range make it hard to implement function
- "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> (14/22) Aug 04 2014 I guess when you iterate over it, you just get tuples. So, `map`
I just curious, do Associative Ranges exist. If so where can i find them. I started thinking about them when i asked this question: http://forum.dlang.org/thread/vauuognmhvtjrktazyeb forum.dlang.org
Aug 01 2014
On Friday, 1 August 2014 at 23:57:37 UTC, Freddy wrote:I just curious, do Associative Ranges exist. If so where can i find them. I started thinking about them when i asked this question: http://forum.dlang.org/thread/vauuognmhvtjrktazyeb forum.dlang.orgUnfortunately not, but I do wonder if we should generalize an interface for these types of ranges.
Aug 02 2014
Xinok:I do wonder if we should generalize an interface for these types of ranges.First of all you need some use cases and usage examples. Bye, bearophile
Aug 02 2014
On Saturday, 2 August 2014 at 14:49:49 UTC, bearophile wrote:Xinok:The most obvious use case is generic functions that can operate on associative ranges of any type, regardless of implementation. There are various ways to implement and optimize hash tables for specific use cases, so it would be convenient not to be restricted to a single container. As for usage examples, I don't have any because I'm not sure what the primitives should be. I will emphasize that "associative ranges" should be distinguishable from random-access ranges. If they weren't, then we would have to comb through Phobos and add checks everywhere, e.g. (!isAssociativeRange!Range). I don't think forward ranges and bidirectional ranges would be an issue though.I do wonder if we should generalize an interface for these types of ranges.First of all you need some use cases and usage examples. Bye, bearophile
Aug 02 2014
"Freddy" <Hexagonalstar64 gmail.com> On Saturday, 2 August 2014 at 15:46:31 UTC, Xinok wrote:On Saturday, 2 August 2014 at 14:49:49 UTC, bearophile wrote:It might be a ploblem if you have an Associative Range where the key is size_t unless Associative ranges are not Input/Forward RangesXinok:The most obvious use case is generic functions that can operate on associative ranges of any type, regardless of implementation. There are various ways to implement and optimize hash tables for specific use cases, so it would be convenient not to be restricted to a single container. As for usage examples, I don't have any because I'm not sure what the primitives should be. I will emphasize that "associative ranges" should be distinguishable from random-access ranges. If they weren't, then we would have to comb through Phobos and add checks everywhere, e.g. (!isAssociativeRange!Range). I don't think forward ranges and bidirectional ranges would be an issue though.I do wonder if we should generalize an interface for these types of ranges.First of all you need some use cases and usage examples. Bye, bearophile
Aug 02 2014
On Saturday, 2 August 2014 at 15:46:31 UTC, Xinok wrote:On Saturday, 2 August 2014 at 14:49:49 UTC, bearophile wrote:+1, I'd like to add that compiler is a good example of were this is useful. You'll have quick/small/throwaway and only growing map - to keep track of unwinding infos, break/continue/labels status, switch processing -, long lived one that only grow (and can grow big) - template instance cache, symbol table - as well as map where element goes in and out all the time - for internal machinery -. Optimal algorithms for these use case are different, and it'd be great if part of the code could be factorized. For info, SDC only uses out of the box hashmaps for now, but could benefit from better implementations - and doing so is waaaayyyyyy down the priority queue.Xinok:The most obvious use case is generic functions that can operate on associative ranges of any type, regardless of implementation. There are various ways to implement and optimize hash tables for specific use cases, so it would be convenient not to be restricted to a single container.I do wonder if we should generalize an interface for these types of ranges.First of all you need some use cases and usage examples. Bye, bearophile
Aug 04 2014
On Friday, 1 August 2014 at 23:57:37 UTC, Freddy wrote:I just curious, do Associative Ranges exist. If so where can i find them. I started thinking about them when i asked this question: http://forum.dlang.org/thread/vauuognmhvtjrktazyeb forum.dlang.orgI started a phobos fork for this, what do you think so far https://github.com/Superstar64/phobos/blob/60d3472b1056b298319976f105aa3b9b3f165e97/std/range.d#L1357-1420
Aug 02 2014
On Sunday, 3 August 2014 at 06:19:12 UTC, Freddy wrote:On Friday, 1 August 2014 at 23:57:37 UTC, Freddy wrote:Nice! A few comments after a cursory glance: 1) "aligns" sounds strange, use "corresponds" instead. 2) It would be preferable that associative ranges mimic built-in associative arrays as closely as possible, i.e. the range members should be called `byKey` and `byValue`, and it should allow iteration over the associative range directly, instead of using the `range` member. 3) For the value and key ranges, there should be a guarantee that they can be zipped through, i.e. that the elements in them are in the same order so keys and values correspond to each other. The built-in associative arrays provide `byKey` and `byValue`, which satisfy this condition.I just curious, do Associative Ranges exist. If so where can i find them. I started thinking about them when i asked this question: http://forum.dlang.org/thread/vauuognmhvtjrktazyeb forum.dlang.orgI started a phobos fork for this, what do you think so far https://github.com/Superstar64/phobos/blob/60d3472b1056b298319976f105aa3b9b3f165e97/std/range.d#L1357-1420
Aug 03 2014
On Sunday, 3 August 2014 at 08:50:47 UTC, Marc Schütz wrote:On Sunday, 3 August 2014 at 06:19:12 UTC, Freddy wrote:Alright i fixed it, although should the implict range be a forward range, an input range or something else and how do you implement front,popFront, and empty on a built-in associative array.On Friday, 1 August 2014 at 23:57:37 UTC, Freddy wrote:Nice! A few comments after a cursory glance: 1) "aligns" sounds strange, use "corresponds" instead. 2) It would be preferable that associative ranges mimic built-in associative arrays as closely as possible, i.e. the range members should be called `byKey` and `byValue`, and it should allow iteration over the associative range directly, instead of using the `range` member. 3) For the value and key ranges, there should be a guarantee that they can be zipped through, i.e. that the elements in them are in the same order so keys and values correspond to each other. The built-in associative arrays provide `byKey` and `byValue`, which satisfy this condition.I just curious, do Associative Ranges exist. If so where can i find them. I started thinking about them when i asked this question: http://forum.dlang.org/thread/vauuognmhvtjrktazyeb forum.dlang.orgI started a phobos fork for this, what do you think so far https://github.com/Superstar64/phobos/blob/60d3472b1056b298319976f105aa3b9b3f165e97/std/range.d#L1357-1420
Aug 03 2014
On Sunday, 3 August 2014 at 08:50:47 UTC, Marc Schütz wrote:On Sunday, 3 August 2014 at 06:19:12 UTC, Freddy wrote:Also won't the implicit range make it hard to implement function like map (should you map to whole range or to the value)On Friday, 1 August 2014 at 23:57:37 UTC, Freddy wrote:Nice! A few comments after a cursory glance: 1) "aligns" sounds strange, use "corresponds" instead. 2) It would be preferable that associative ranges mimic built-in associative arrays as closely as possible, i.e. the range members should be called `byKey` and `byValue`, and it should allow iteration over the associative range directly, instead of using the `range` member. 3) For the value and key ranges, there should be a guarantee that they can be zipped through, i.e. that the elements in them are in the same order so keys and values correspond to each other. The built-in associative arrays provide `byKey` and `byValue`, which satisfy this condition.I just curious, do Associative Ranges exist. If so where can i find them. I started thinking about them when i asked this question: http://forum.dlang.org/thread/vauuognmhvtjrktazyeb forum.dlang.orgI started a phobos fork for this, what do you think so far https://github.com/Superstar64/phobos/blob/60d3472b1056b298319976f105aa3b9b3f165e97/std/range.d#L1357-1420
Aug 03 2014
On Sunday, 3 August 2014 at 18:38:51 UTC, Freddy wrote:On Sunday, 3 August 2014 at 08:50:47 UTC, Marc Schütz wrote:I guess when you iterate over it, you just get tuples. So, `map` would return a normal range of tuples, not an associative range. There could then be a method to convert such a range to an associative range (although it would need to assume that the first tuple elements = keys are unique). I'm not sure whether this is the right thing to do. In any case I don't think it's good to map the keys, because they mustn't be modified, or otherwise you could get duplicate keys. An alternative would be that `map` takes both a the key and the value, but returns only the new value. The same goes for the other range operations (e.g. reduce). But on the other hand, this doesn't seem to scale, because all range algorithms would then have to be specialized for associative ranges...3) For the value and key ranges, there should be a guarantee that they can be zipped through, i.e. that the elements in them are in the same order so keys and values correspond to each other. The built-in associative arrays provide `byKey` and `byValue`, which satisfy this condition.Also won't the implicit range make it hard to implement function like map (should you map to whole range or to the value)
Aug 04 2014
On Monday, 4 August 2014 at 09:21:40 UTC, Marc Schütz wrote:On Sunday, 3 August 2014 at 18:38:51 UTC, Freddy wrote:The way I have it now is that type doesn't matter when you iterate over a assciative range, all that matters is that that type has a .key and .value. This allow custom opAssign and other bonuses. Should I switch to use type tuples. A lot of the functions that take Input/Forward ranges don't need specialization because you could use byValue and zip with byKey(however then we might need to add a default .key and .value to type tuples if we go with my original idea).On Sunday, 3 August 2014 at 08:50:47 UTC, Marc Schütz wrote:I guess when you iterate over it, you just get tuples. So, `map` would return a normal range of tuples, not an associative range. There could then be a method to convert such a range to an associative range (although it would need to assume that the first tuple elements = keys are unique). I'm not sure whether this is the right thing to do. In any case I don't think it's good to map the keys, because they mustn't be modified, or otherwise you could get duplicate keys. An alternative would be that `map` takes both a the key and the value, but returns only the new value. The same goes for the other range operations (e.g. reduce). But on the other hand, this doesn't seem to scale, because all range algorithms would then have to be specialized for associative ranges...3) For the value and key ranges, there should be a guarantee that they can be zipped through, i.e. that the elements in them are in the same order so keys and values correspond to each other. The built-in associative arrays provide `byKey` and `byValue`, which satisfy this condition.Also won't the implicit range make it hard to implement function like map (should you map to whole range or to the value)
Aug 04 2014
On Tuesday, 5 August 2014 at 00:11:21 UTC, Freddy wrote:On Monday, 4 August 2014 at 09:21:40 UTC, Marc Schütz wrote:Wait, the build-in associative arrays already a opApply with a single element, this makes them unable to be an associate range (depending on priority we would break backwards compatabily or be unable to use them as a range) unless we change the associtive range interface to be an input/forward range of the value type and ask users to zip byKeys and the rangeOn Sunday, 3 August 2014 at 18:38:51 UTC, Freddy wrote:The way I have it now is that type doesn't matter when you iterate over a assciative range, all that matters is that that type has a .key and .value. This allow custom opAssign and other bonuses. Should I switch to use type tuples. A lot of the functions that take Input/Forward ranges don't need specialization because you could use byValue and zip with byKey(however then we might need to add a default .key and .value to type tuples if we go with my original idea).On Sunday, 3 August 2014 at 08:50:47 UTC, Marc Schütz wrote:I guess when you iterate over it, you just get tuples. So, `map` would return a normal range of tuples, not an associative range. There could then be a method to convert such a range to an associative range (although it would need to assume that the first tuple elements = keys are unique). I'm not sure whether this is the right thing to do. In any case I don't think it's good to map the keys, because they mustn't be modified, or otherwise you could get duplicate keys. An alternative would be that `map` takes both a the key and the value, but returns only the new value. The same goes for the other range operations (e.g. reduce). But on the other hand, this doesn't seem to scale, because all range algorithms would then have to be specialized for associative ranges...3) For the value and key ranges, there should be a guarantee that they can be zipped through, i.e. that the elements in them are in the same order so keys and values correspond to each other. The built-in associative arrays provide `byKey` and `byValue`, which satisfy this condition.Also won't the implicit range make it hard to implement function like map (should you map to whole range or to the value)
Aug 04 2014
On Monday, 4 August 2014 at 09:21:40 UTC, Marc Schütz wrote:On Sunday, 3 August 2014 at 18:38:51 UTC, Freddy wrote:I have come up with a new interface: ---- R r=void; auto v=r.front;//r is an input range auto k=r.byKey.front;//byKey is an input range v=r[k];//opIndex of k v=*(k in r);//opBinearyRight!"in" of k ---- The allows function like map to not alter key(similar to how map can't alter the postioning of random access ranges), and it shouldn't conflit with the build-in associative array's opApplyOn Sunday, 3 August 2014 at 08:50:47 UTC, Marc Schütz wrote:I guess when you iterate over it, you just get tuples. So, `map` would return a normal range of tuples, not an associative range. There could then be a method to convert such a range to an associative range (although it would need to assume that the first tuple elements = keys are unique). I'm not sure whether this is the right thing to do. In any case I don't think it's good to map the keys, because they mustn't be modified, or otherwise you could get duplicate keys. An alternative would be that `map` takes both a the key and the value, but returns only the new value. The same goes for the other range operations (e.g. reduce). But on the other hand, this doesn't seem to scale, because all range algorithms would then have to be specialized for associative ranges...3) For the value and key ranges, there should be a guarantee that they can be zipped through, i.e. that the elements in them are in the same order so keys and values correspond to each other. The built-in associative arrays provide `byKey` and `byValue`, which satisfy this condition.Also won't the implicit range make it hard to implement function like map (should you map to whole range or to the value)
Aug 04 2014