www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - [Feature Request] Adding to D lang "set" built-in

reply bioinfornatics <bioinfornatics fedoraproject.org> writes:
Dear, i hope i will got some answer from druntime/phobos dev .
A set is an array of unique element:
 set( 1, 5, 7, 1, 7)



Currently in D the hack it is to use an associative array with any value. byte[size_t] a =3D [ 1:0, 5:0, 7:0, 1:0, 7:0 ]; then it is easy to have a set in D just add a syntax or a built-in where use associative array without using value. I hope really this little feature and seem really easy to add thanks a lot for your great works
May 05 2012
next sibling parent Gor Gyolchanyan <gor.f.gyolchanyan gmail.com> writes:
I think a much more realistic suggestion would be to add it to phobos
as a struct, which wraps this no-value AA solution.

On Sat, May 5, 2012 at 9:14 PM, bioinfornatics
<bioinfornatics fedoraproject.org> wrote:
 Dear, i hope i will got some answer from druntime/phobos dev .
 A set is an array of unique element:
 set( 1, 5, 7, 1, 7)



Currently in D the hack it is to use an associative array with any value. byte[size_t] a = [ 1:0, 5:0, 7:0, 1:0, 7:0 ]; then it is easy to have a set in D just add a syntax or a built-in where use associative array without using value. I hope really this little feature and seem really easy to add thanks a lot for your great works

-- Bye, Gor Gyolchanyan.
May 05 2012
prev sibling next sibling parent "Chris Cain" <clcain uncg.edu> writes:
There's a few ways to implement your own Sets right now, if 
needed. You found one way (using the built in AAs), but that's 
not all.

* You could use Array!bool (which efficiently stores bools) to 
store whether integers are in or out of your set.
* You can use std.container's redBlackTree to make a set which 
would work better if your items are objects or you're dealing 
with a sparse array.

There's probably a few other extremely simple methods, but those 
are the two I had on the top of my head. I'm not really sure 
having a particular "Set" in the library would be all that 
useful. Generally, if I want a set, I have a particular idea of 
how one should be implemented for my particular data.
May 05 2012
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sat, May 05, 2012 at 07:14:27PM +0200, bioinfornatics wrote:
 Dear, i hope i will got some answer from druntime/phobos dev .
 A set is an array of unique element:
 set( 1, 5, 7, 1, 7)



Currently in D the hack it is to use an associative array with any value. byte[size_t] a = [ 1:0, 5:0, 7:0, 1:0, 7:0 ]; then it is easy to have a set in D just add a syntax or a built-in where use associative array without using value. I hope really this little feature and seem really easy to add

It's not too hard to implement something like this yourself. One of the first projects I did when I started learning D was to implement an integer set (basically a bit array). It supports full set operations, like union, intersection, difference, optimized filling with first n numbers, foreach, etc.. Some of the operations use bit-twiddling tricks to maximize performance. The only flaw is that it's essentially just a bit array, so it only works well for sets whose elements are relatively small numbers. If you want sparse sets, you may be better off adapting D's AA implementation to have an AA that consists of just keys. Basically, you still have the hash table and buckets, just without the value field in each slot. (I wonder if it's possible for the new AA implementation to support this by specifying void as the value type.) T -- Klein bottle for rent ... inquire within. -- Stephen Mulraney
May 06 2012
prev sibling next sibling parent "Chris Cain" <clcain uncg.edu> writes:
On Sunday, 6 May 2012 at 22:10:03 UTC, H. S. Teoh wrote:
 slot. (I
 wonder if it's possible for the new AA implementation to 
 support this by
 specifying void as the value type.)

That would actually be very nice if it were the case.
May 06 2012
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 5/7/12, Andrej Mitrovic <andrej.mitrovich gmail.com> wrote:
 just write an
 some

Beautiful way to start a sentence. :P
May 06 2012
prev sibling next sibling parent Russel Winder <russel winder.org.uk> writes:
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Mon, 2012-05-07 at 00:42 +0200, Andrej Mitrovic wrote:
 On 5/7/12, H. S. Teoh <hsteoh quickfur.ath.cx> wrote:
 you may be better off adapting D's AA implementation
 to have an AA that consists of just keys.

Yeah I do that in my code right now. It's pretty easy, just write an some opApply/opBinary functions, add to!string(innerhash.keys) for good measure and you're set (heh, set).

Any language with which the programmer has to develop their own set implementation is sadly lacking. It is true that set can be implemented using a map, but this should be seen as implementation detail, not as programmer level tool. It indicates that set should exist where set does. So for C++ it is in the standard library, for Python it is a built-in (*). The conclusion for D is straightforward. Which issue to I go to to vote? (*) Although set was a second class citizen in Python 2, it is a first class citizen in Python 3. There are even set comprehensions, just as there are list comprehensions and dictionary comprehensions. I just love the influence of functional programming: be data evolution focused, not control flow focused. --=20 Russel. =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.winder ekiga.n= et 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
May 06 2012
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, May 07, 2012 06:49:00 Russel Winder wrote:
 On Mon, 2012-05-07 at 00:42 +0200, Andrej Mitrovic wrote:
 On 5/7/12, H. S. Teoh <hsteoh quickfur.ath.cx> wrote:
 you may be better off adapting D's AA implementation
 to have an AA that consists of just keys.

Yeah I do that in my code right now. It's pretty easy, just write an some opApply/opBinary functions, add to!string(innerhash.keys) for good measure and you're set (heh, set).

Any language with which the programmer has to develop their own set implementation is sadly lacking. It is true that set can be implemented using a map, but this should be seen as implementation detail, not as programmer level tool. It indicates that set should exist where set does. So for C++ it is in the standard library, for Python it is a built-in (*). The conclusion for D is straightforward. Which issue to I go to to vote?

We have RedBlackTree, so we have a set already. What we don't have is a HashSet. However, once the custom allocator stuff has been sorted out, I'd fully expect to have one in std.container along with a variety of other container types which we really should have but don't. - Jonathan M Davis
May 06 2012
prev sibling next sibling parent Russel Winder <russel winder.org.uk> writes:
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Sun, 2012-05-06 at 22:53 -0700, Jonathan M Davis wrote:
[...]
 We have RedBlackTree, so we have a set already. What we don't have is a=

 HashSet. However, once the custom allocator stuff has been sorted out, I'=

 fully expect to have one in std.container along with a variety of other=

 container types which we really should have but don't.

I certainly went immediately to std.container to look for the work set, map, etc. in some guise. I only posted after finding nothing appropriate. I guess the issue here is that maps (aka dictionaries, aka associative arrays) are in the D language core (as in Python) rather than being is the library (as in C++). This indicates set should be in the core rather than in the library. I wonder if the tradition of exposing HashMap and TreeMap was a disservice by C++ and Java? Map and Set are programmer level concepts. Where there are algorithmic issues that require knowing about trees or has tables then the programmer is not working at the map or set level. And the programmer has no control over how D's associative arrays work. And let's not mention Java's LinkedHashMap. :-) --=20 Russel. =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.winder ekiga.n= et 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
May 06 2012
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, May 07, 2012 07:05:28 Russel Winder wrote:
 I wonder if the tradition of exposing HashMap and TreeMap was a
 disservice by C++ and Java? Map and Set are programmer level concepts.
 Where there are algorithmic issues that require knowing about trees or
 has tables then the programmer is not working at the map or set level.

??? There are multiple ways to implement a set or a map. If a programmer knows their data structures (as one would hope that they would), then they know the difference between a hash set and a tree set (or hash map and tree map), and they'll pick the one that's most appropriate for what they're doing. And because the containers are very similar, it should be quite possible in many cases to replace one with the other quite easily - especially if you're using templates. That's one of the reasons that Java has the Set interface with HashSet and TreeSet implenting it. std.container is designed with the idea that containers will be named after their data structures and _not_ what they're used for. Programmers can then select the data structure that best serves their purposes. And I'd be worried about any professional programmer who didn't know that you can use a red-black tree as a set or a map.
 And the programmer has no control over how D's associative arrays work.

It's clearly a hash map. If they want a tree map, then we have RedBlackTree (though we should probably provide a wrapper that makes it easier to use RedBlackTree as a map, since it's a bit unwieldy to do that at the moment). I don't see the problem. - Jonathan M Davis
May 06 2012
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sat, 05 May 2012 13:14:27 -0400, bioinfornatics  
<bioinfornatics fedoraproject.org> wrote:

 Dear, i hope i will got some answer from druntime/phobos dev .
 A set is an array of unique element:
 set( 1, 5, 7, 1, 7)



Currently in D the hack it is to use an associative array with any value. byte[size_t] a = [ 1:0, 5:0, 7:0, 1:0, 7:0 ]; then it is easy to have a set in D just add a syntax or a built-in where use associative array without using value. I hope really this little feature and seem really easy to add thanks a lot for your great works

http://www.dsource.org/projects/dcollections -Steve
May 07 2012
prev sibling next sibling parent "David Nadlinger" <see klickverbot.at> writes:
On Monday, 7 May 2012 at 06:05:47 UTC, Russel Winder wrote:
 I wonder if the tradition of exposing HashMap and TreeMap was a
 disservice by C++ and Java? Map and Set are programmer level 
 concepts.
 Where there are algorithmic issues that require knowing about 
 trees or
 has tables then the programmer is not working at the map or set 
 level.

Some people say that abstracting away big-O complexity should be a capital offense, and I agree (preferably in slightly less drastic words, though). Additionally, a tree-based map is naturally ordered, whereas a hash map is not – for me, that's enough to warrant exposing what seems to be a »detail«, at least in languages like C++ and D. David
May 07 2012
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 07 May 2012 08:52:56 -0400, David Nadlinger <see klickverbot.at>=
  =

wrote:

 On Monday, 7 May 2012 at 06:05:47 UTC, Russel Winder wrote:
 I wonder if the tradition of exposing HashMap and TreeMap was a
 disservice by C++ and Java? Map and Set are programmer level concepts=


 Where there are algorithmic issues that require knowing about trees o=


 has tables then the programmer is not working at the map or set level=


 Some people say that abstracting away big-O complexity should be a  =

 capital offense, and I agree (preferably in slightly less drastic word=

 though). Additionally, a tree-based map is naturally ordered, whereas =

 hash map is not =E2=80=93 for me, that's enough to warrant exposing wh=

 to be a =C2=BBdetail=C2=AB, at least in languages like C++ and D.

Yes, I fully agree. That being said, I think it's also important that some = functions/structures should not have to care what algorithm is used. = That's one of the reasons I like having the interface design that = dcollections uses. -Steve
May 07 2012
prev sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Monday, 7 May 2012 at 05:54:04 UTC, Jonathan M Davis wrote:
 On Monday, May 07, 2012 06:49:00 Russel Winder wrote:
 Any language with which the programmer has to develop their  
 own set implementation is sadly lacking.
 
 It is true that set can be implemented using a map, but this  
 should be seen as implementation detail, not as programmer 
 level tool. It indicates that set should exist where set does. 
 So for C++ it  is in the standard library, for Python it is a 
 built-in (*).
 
 The conclusion for D is straightforward. Which issue to I go  
 to to vote?

We have RedBlackTree, so we have a set already. What we don't have is a HashSet. However, once the custom allocator stuff has been sorted out, I'd fully expect to have one in std.container along with a variety of other container types which we really should have but don't.

Been thinking about this a little. With arrays, fixed arrays and associative arrays being built in, you don't need set to be built in. First it's already hash-map like so it's going to be O(1), and the data being kinda useless can either be a byte, and int (offset to an array perhaps), or to itself. It has the added benefit of being a sparse array when asked of it. So aside from a slight loss in memory space which is only going to be critical in embedded systems. The only thing the builtins don't offer is a way to automatically sort the data, which the libraries and RedBlackTree's do quite well so far as I can see.
May 07 2012