www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Sets

reply Michiel <nomail hotmail.com> writes:
Is there a built-in way to create a set in D? Like an associative array, only
without the value?

I tried: void[KeyType] setName;

It compiled. But there doesn't seem to be a way to add an item to the set.

Am I missing something? Or is it just a bug that this even compiled?

I know I could just use a dummy value, but that's just not very elegant.

Thanks!
Feb 05 2007
next sibling parent reply Derek Parnell <derek psych.ward> writes:
On Mon, 5 Feb 2007 17:44:10 +0000 (UTC), Michiel wrote:

 Is there a built-in way to create a set in D? Like an associative array, only
 without the value?
 
 I tried: void[KeyType] setName;
 
 It compiled. But there doesn't seem to be a way to add an item to the set.
 
 Am I missing something? Or is it just a bug that this even compiled?
 
 I know I could just use a dummy value, but that's just not very elegant.
 
 Thanks!

I just use: bool[Keytype] setName;
Feb 05 2007
parent reply Michiel <nomail hotmail.com> writes:
Derek Parnell wrote:

 I just use: bool[Keytype] setName;

The problem is that the set of possible keys isn't fixed (I'll often use char[] as key-type). So with your idea, there are two possibilities for elements not in the set. Either they're not in the array at all, or they are, but their value is false. This gives me a very PHPish feeling. :) I'd feel better about it if sets were built into D. But I know using a dummy value is an option. And that's what I'll use if I have no other choice.
Feb 05 2007
next sibling parent reply Sean Kelly <sean f4.ca> writes:
Michiel wrote:
 Derek Parnell wrote:
 
 I just use: bool[Keytype] setName;

The problem is that the set of possible keys isn't fixed (I'll often use char[] as key-type). So with your idea, there are two possibilities for elements not in the set. Either they're not in the array at all, or they are, but their value is false. This gives me a very PHPish feeling. :) I'd feel better about it if sets were built into D. But I know using a dummy value is an option. And that's what I'll use if I have no other choice.

The behavior for sets was cleaner before their behavior was changed such that an opIndex lookup throws an exception if the lookup fails. Previously, it would return the default value, which for bool would be 'false'. Insertions were still a bit messy as setName[key] = true, but it was better than nothing. Personally, I'm not fond of how AA indexing and 'in' works now. It feels like a kludge. Sean
Feb 05 2007
parent reply Michiel <nomail hotmail.com> writes:
Sean Kelly wrote:

 The behavior for sets was cleaner before their behavior was changed such
 that an opIndex lookup throws an exception if the lookup fails.
 Previously, it would return the default value, which for bool would be
 'false'.  Insertions were still a bit messy as setName[key] = true, but
 it was better than nothing.  Personally, I'm not fond of how AA indexing
 and 'in' works now.  It feels like a kludge.

Ah, I see. I understand how the old behavior was handy for faking sets. But to be honest, I like the new behavior better in general. That old behavior was much more ambiguous. And the 'in' notation is more intuitive for people with a background in basic set theory. My problems are: * Declaring the set: You have to give a value type, even though you don't really need it. * Adding to the set: You have to assign a dummy value, which isn't very elegant. I think the void[KeyType] notation for sets is very intuitive. All it further needs is an add(KeyType element) function. I think it can be well defined and would be a nice addition to the D language. Do the D developers read this newsgroup? Or should I mail them with this suggestion?
Feb 05 2007
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Michiel wrote:
 Sean Kelly wrote:
 
 The behavior for sets was cleaner before their behavior was changed such
 that an opIndex lookup throws an exception if the lookup fails.
 Previously, it would return the default value, which for bool would be
 'false'.  Insertions were still a bit messy as setName[key] = true, but
 it was better than nothing.  Personally, I'm not fond of how AA indexing
 and 'in' works now.  It feels like a kludge.

Ah, I see. I understand how the old behavior was handy for faking sets. But to be honest, I like the new behavior better in general. That old behavior was much more ambiguous. And the 'in' notation is more intuitive for people with a background in basic set theory. My problems are: * Declaring the set: You have to give a value type, even though you don't really need it. * Adding to the set: You have to assign a dummy value, which isn't very elegant. I think the void[KeyType] notation for sets is very intuitive. All it further needs is an add(KeyType element) function. I think it can be well defined and would be a nice addition to the D language. Do the D developers read this newsgroup? Or should I mail them with this suggestion?

Walter reads this newsgroup, so there's nothing in particular you need to do. The lack of a set type and the use of void[KeyType] for sets has been discussed a few times in the past, I think. It makes sense to me too, at first glance. But I suspect it would require a whole different codepath in the compiler to deal with because you can't have arrays of voids etc. You really want a different data structure to store a set. And as you mentioned it should have an 'add' method which would be meaningless for ordinary AA's. Following AA syntax could also lead to annoying special cases for generic templates that would have to be prepared for the V==void case: foo(K,V)(V[K] aa) { ...V val; // whoops V could be void! } Anyway, all that says to me that void[KeyType] for sets is not really a slam dunk, and a simple set() class in the std library might be a better option. I'm surprised Sean didn't mention it, but the Tango replacement for the standard library does have Set as well as Bag (aka "multi-set") collection types. --bb
Feb 05 2007
parent reply Michiel <nomail hotmail.com> writes:
 The lack of a set type and the use of void[KeyType] for sets has been
 discussed a few times in the past, I think.  It makes sense to me too,
 at first glance.  But I suspect it would require a whole different
 codepath in the compiler to deal with because you can't have arrays of
 voids etc. You really want a different data structure to store a set.

I think creating a whole different data structure just for the set isn't worth the trouble. For now, I've created the following simple code, which I will use for now. It still uses dummy values, but hides this behind a template and an array function: --------------------------------- template Set(T) { alias bit[T] Set; } void add(T)(inout bit[T] set, T element) { set[element] = 1; } --------------------------------- Set!(char[]) set; set.add("one"); set.add("two"); assert("one" in set); assert("two" in set); assert(!("fortytwo" in set)); ---------------------------------
 And as you mentioned it should have an 'add' method which would be
 meaningless for ordinary AA's.

For ordinary AA's, another parameter could be passed for the value, which could default to the type's init value.
 Following AA syntax could also lead to
 annoying special cases for generic templates that would have to be
 prepared for the V==void case:
     foo(K,V)(V[K] aa) { ...V val; // whoops V could be void! }

Isn't the same thing true for many situations? What if you wanted to compare a V object with an integer? The compiler would generate an error for any V for which no such comparison is defined. I would simply expect the compiler to complain in your example. I'm not saying it's easy. But it should be worth it for the same reason that associative arrays are included into the core language.
Feb 05 2007
next sibling parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Michiel wrote:
 The lack of a set type and the use of void[KeyType] for sets has been
 discussed a few times in the past, I think.  It makes sense to me too,
 at first glance.  But I suspect it would require a whole different
 codepath in the compiler to deal with because you can't have arrays of
 voids etc. You really want a different data structure to store a set.


 
 I think creating a whole different data structure just for the set isn't worth
the
 trouble.

Maybe not for casual use, but if for some reason you are creating huge sets, you'll probably care whether it uses 1GB or 2GB of memory. It's not a "whole different" data structure that's required, just a modified version of the AA data structure that doesn't store values. But still that makes it a different data structure that will require different code in D. I'm kinda just playing devil's advocate here. I was actually one of the people who previously commented that void[KeyType] should just work. But if it's going into the core language it better be a slam dunk.
 For now, I've created the following simple code, which I will use for now. It
 still uses dummy values, but hides this behind a template and an array
function:
 
 ---------------------------------
 template Set(T) {
 	alias bit[T] Set;
 }
 
 void add(T)(inout bit[T] set, T element) {
 	set[element] = 1;
 }
 ---------------------------------
 Set!(char[]) set;
 
 set.add("one");
 set.add("two");
 
 assert("one" in set);
 assert("two" in set);
 assert(!("fortytwo" in set));
 ---------------------------------

I think the type 'bit' is deprecated. Anyway, it's just an alias for 'bool' (see phobos/object.d) so you might as well use bool rather than a type that isn't even listed in the spec: http://www.digitalmars.com/d/type.html
 
 And as you mentioned it should have an 'add' method which would be
 meaningless for ordinary AA's.

For ordinary AA's, another parameter could be passed for the value, which could default to the type's init value.

True.
 
 Following AA syntax could also lead to
 annoying special cases for generic templates that would have to be
 prepared for the V==void case:
     foo(K,V)(V[K] aa) { ...V val; // whoops V could be void! }

Isn't the same thing true for many situations? What if you wanted to compare a V object with an integer? The compiler would generate an error for any V for which no such comparison is defined. I would simply expect the compiler to complain in your example.

Yeh, despite what I said, you could also see sets having AA syntax as being a *good* thing for templates, since it would let any template that only cares about keys to match both sets and AA's. But really it's kind of a bogus argument anyway. Templates should use duck typing wherever possible. I.e. the template should be written such that it supports any object with the necessary interface, like .keys and .values methods or a[x] syntax.
 I'm not saying it's easy. But it should be worth it for the same reason that
 associative arrays are included into the core language.

One issue with sets as AAs is that really one typically thinks of sets as a collection of "values" not a collection of "keys". If you make a set type from scratch, you'd be more likely to have a "set.values" member than a "set.keys" member. Here's a thought - one way to deal with that would be for the implementation of void[KeyType] to just return the key itself for any attempts to access an existing key. So myset["key"] would return "key" if key was in the array, or throw an exception if not. That way you could also use ".values" on a void[KeyType] set instead of ".keys", and handle the issue of what auto = foo in myset; should return. It looks like a number of things in dmd/src/phobos/internal/aaA.d would have to be rewritten with special versions for handling void. But it doesn't look like it would be a huge amount of code. In particular the main data structure already seems to allocate nodes as a big void* with size of keysize+valuesize, so that should still be ok with valuesize==0. Then you'd also need some conditionals added to the code that calls into the aaA.d code. --bb
Feb 05 2007
prev sibling parent "d" <d nomail.com> writes:
 I think creating a whole different data structure just for the set isn't

 trouble.

Sets done properly: type TCarManufacturer = (cmFord, cmRenault, cmVauxhall, cmFiat); // enumeration - each element has an ordinal // value - not numerical type TCarManufacturers = set of TCarManufacturer; const DEFAULT_CAR_MANUF = [cmFord, cmVauhall]; //square brackets denote "set" in code var myset: TCarManufacturers; myintersection: TCarManufacturers; begin myset := [cmFord]; //Assign "ford" to the set myset := myset + DEFAULT_CAR_MANUF; //still only contains one "cmFord" myintersection := []; //empty set - sets don't need to be initialised however... myintersection := myset * [cmFord]; //intersection myset := myset - myintersection; //removes the common values end; The following operators take sets as operands. Operator Operation Operand types Result type Example + union set set Set1 + Set2 - difference set set S - T * intersection set set S * T <= subset set Boolean Q <= MySet
=               superset         set                      Boolean       S1
= S2

S2 = MySet <> inequality set Boolean MySet <> S1 in membership ordinal, set Boolean A in Set1
Feb 08 2007
prev sibling parent reply BCS <ao pathlink.com> writes:
Reply to Michiel,

 Derek Parnell wrote:
 
 I just use: bool[Keytype] setName;
 

use char[] as key-type). So with your idea, there are two possibilities for elements not in the set. Either they're not in the array at all, or they are, but their value is false. This gives me a very PHPish feeling. :) I'd feel better about it if sets were built into D. But I know using a dummy value is an option. And that's what I'll use if I have no other choice.

you might look at the (<key> "in" <set>) syntax bool[Keys] set; set[key1] = false; set[key2] = true; (key1 in set) // is true (!= null to be totally correct) (key2 in set) // is true (key3 in set) // is false (== null) a good set syntax would be nice void[key] set; // no storage for each member set[key1] = true; // adds member set[key1] = false; // removes member if(set[key1]) // test for member set.keys // get set ...
Feb 05 2007
parent Fredrik Olsson <peylow gmail.com> writes:
BCS skrev:
 Reply to Michiel,
 
 Derek Parnell wrote:

 I just use: bool[Keytype] setName;

use char[] as key-type). So with your idea, there are two possibilities for elements not in the set. Either they're not in the array at all, or they are, but their value is false. This gives me a very PHPish feeling. :) I'd feel better about it if sets were built into D. But I know using a dummy value is an option. And that's what I'll use if I have no other choice.

you might look at the (<key> "in" <set>) syntax bool[Keys] set; set[key1] = false; set[key2] = true; (key1 in set) // is true (!= null to be totally correct) (key2 in set) // is true (key3 in set) // is false (== null) a good set syntax would be nice void[key] set; // no storage for each member set[key1] = true; // adds member set[key1] = false; // removes member if(set[key1]) // test for member set.keys // get set ...

Steal the Pascal way! It works marvelously. Do not invent another mechanism for sets, do not make it a template/library implementation. For implementation most Pascal implementations uses bitfields for small sets, and trees for larger sets. To declare a set pascal uses: set of type I have previously suggests D could use: type<> Set literals in Pascal are declared as for example: [1, 3..5] I have previously suggested D could use: <1, 3..5> Pascal uses the in-operator to test for set membership, I say do the same with D. ch in <'w', 't', 'f'> Pascal uses +-operator for set unions, --operator for difference, and *- operator for intersection. GNUPascal add many more useful operators: http://tinyurl.com/37efbm Steal as many as is ever possible! I think it is very unintuitive to use say mySet.add(foo) and mySet.remove(foo) when I can use mySet += foo and mySet -= foo. Oooh well... one could dream. Oh, and the usual disclaimer: DO NO NITPICK ON SYNTAX, THEY ARE SUGGESTIONS, AND IF TECHNICAL RESTRICTIONS APPLY; WHATEVER! I WANT THE FUNCTIONALITY BEHIND THE SYNTAX, NOT THE SYNTAX ITSELF!!! // Fredrik Olsson
 

Feb 06 2007
prev sibling parent reply Dawid =?UTF-8?B?Q2nEmcW8YXJraWV3aWN6?= <dawid.ciezarkiewicz asn.pl> writes:
Michiel wrote:

 Is there a built-in way to create a set in D? Like an associative array,
 only without the value?

Sets are so useful, and aa with void value could work as sets quite well. Walter ... pleeease? :)
Feb 05 2007
parent Gregor Richards <Richards codu.org> writes:
Dawid Ciężarkiewicz wrote:
 Michiel wrote:
 
 
Is there a built-in way to create a set in D? Like an associative array,
only without the value?

Sets are so useful, and aa with void value could work as sets quite well. Walter ... pleeease? :)

Hear, hear! - Gregor Richards
Feb 05 2007