www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Could we reserve void[T] for builtin set of T ?

reply deadalnix <deadalnix gmail.com> writes:
Pretty much as per title. I has that in the back of my mind for a 
while. Would that work ?
Mar 31 2016
next sibling parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Thu, Mar 31, 2016 at 07:24:14PM +0000, deadalnix via Digitalmars-d wrote:
 Pretty much as per title. I has that in the back of my mind for a
 while.  Would that work ?
What's a "builtin set of T"? T -- Век живи - век учись. А дураком помрёшь.
Mar 31 2016
next sibling parent deadalnix <deadalnix gmail.com> writes:
On Thursday, 31 March 2016 at 19:29:19 UTC, H. S. Teoh wrote:
 On Thu, Mar 31, 2016 at 07:24:14PM +0000, deadalnix via 
 Digitalmars-d wrote:
 Pretty much as per title. I has that in the back of my mind 
 for a while.  Would that work ?
What's a "builtin set of T"? T
https://en.wikipedia.org/wiki/Set_%28abstract_data_type%29
Mar 31 2016
prev sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2016-03-31 21:29, H. S. Teoh via Digitalmars-d wrote:
 On Thu, Mar 31, 2016 at 07:24:14PM +0000, deadalnix via Digitalmars-d wrote:
 Pretty much as per title. I has that in the back of my mind for a
 while.  Would that work ?
What's a "builtin set of T"?
int[string] is a built-in associative array, void[string] would be the same but a set [1] instead. "T" in his example of be "some type". [1] https://en.wikipedia.org/wiki/Set_%28abstract_data_type%29 -- /Jacob Carlborg
Mar 31 2016
parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Thu, Mar 31, 2016 at 09:39:53PM +0200, Jacob Carlborg via Digitalmars-d
wrote:
 On 2016-03-31 21:29, H. S. Teoh via Digitalmars-d wrote:
On Thu, Mar 31, 2016 at 07:24:14PM +0000, deadalnix via Digitalmars-d wrote:
Pretty much as per title. I has that in the back of my mind for a
while.  Would that work ?
What's a "builtin set of T"?
int[string] is a built-in associative array, void[string] would be the same but a set [1] instead. "T" in his example of be "some type". [1] https://en.wikipedia.org/wiki/Set_%28abstract_data_type%29
[...] Ah, makes sense. But what would aa[x] return? And how would you add elements to it? The current syntax doesn't seem to make sense for sets. T -- Bare foot: (n.) A device for locating thumb tacks on the floor.
Mar 31 2016
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 3/31/2016 12:44 PM, H. S. Teoh via Digitalmars-d wrote:
 Ah, makes sense.  But what would aa[x] return?
A bool indicating membership.
 And how would you add elements to it?
aa[x] = true; // add member x aa[x] = false; // remove member x x in aa; // compile error
Mar 31 2016
next sibling parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Thu, Mar 31, 2016 at 12:57:50PM -0700, Walter Bright via Digitalmars-d wrote:
 On 3/31/2016 12:44 PM, H. S. Teoh via Digitalmars-d wrote:
Ah, makes sense.  But what would aa[x] return?
A bool indicating membership.
And how would you add elements to it?
aa[x] = true; // add member x aa[x] = false; // remove member x x in aa; // compile error
How is this different from bool[T] then? Just the fact that you can't get a reference to the bool? T -- Don't throw out the baby with the bathwater. Use your hands...
Mar 31 2016
next sibling parent tsbockman <thomas.bockman gmail.com> writes:
On Thursday, 31 March 2016 at 19:58:54 UTC, H. S. Teoh wrote:
 How is this different from bool[T] then? Just the fact that you 
 can't get a reference to the bool?
void[T] could be more efficient, since it wouldn't need to allocate memory for a bool payload. I expect that alignment concerns typically require more than one byte per bool in a bool[T]. (I haven't studied the current implementation, though.)
Mar 31 2016
prev sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 3/31/2016 12:58 PM, H. S. Teoh via Digitalmars-d wrote:
 How is this different from bool[T] then? Just the fact that you can't
 get a reference to the bool?
Differences are: 1. it uses less storage, as the bool is implied 2. you cannot have a key in the set that has an associated value of false 3. as you said, you cannot get a reference to the bool (because it is implied)
Mar 31 2016
prev sibling next sibling parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Thursday, 31 March 2016 at 19:57:50 UTC, Walter Bright wrote:
 On 3/31/2016 12:44 PM, H. S. Teoh via Digitalmars-d wrote:
 Ah, makes sense.  But what would aa[x] return?
A bool indicating membership.
Ewww. If it looks like an AA, let's at least keep the AA interface. aa[x] returns void, which, having no value, would be a compile error.
 And how would you add elements to it?
aa[x] = true; // add member x aa[x] = false; // remove member x x in aa; // compile error
aa[x] is a compile error since it is of type void. x in aa returns void*, null if it is not there, not-null if it is there. Dereferencing a void* is illegal anyway so its value is irrelevant. (I'd say just use null and cast(void*) 1) It is actually just a bool, but with consistent typing to other AAs. Phobos's RedBlackTree works with a literal bool from opIn: http://dpldocs.info/experimental-docs/std.container.rbtree.RedBlackTree.opBinaryRight.html
Mar 31 2016
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 3/31/16 4:11 PM, Adam D. Ruppe wrote:
 On Thursday, 31 March 2016 at 19:57:50 UTC, Walter Bright wrote:
 On 3/31/2016 12:44 PM, H. S. Teoh via Digitalmars-d wrote:
 Ah, makes sense.  But what would aa[x] return?
A bool indicating membership.
Ewww. If it looks like an AA, let's at least keep the AA interface. aa[x] returns void, which, having no value, would be a compile error.
 And how would you add elements to it?
aa[x] = true; // add member x aa[x] = false; // remove member x x in aa; // compile error
aa[x] is a compile error since it is of type void. x in aa returns void*, null if it is not there, not-null if it is there. Dereferencing a void* is illegal anyway so its value is irrelevant. (I'd say just use null and cast(void*) 1) It is actually just a bool, but with consistent typing to other AAs. Phobos's RedBlackTree works with a literal bool from opIn: http://dpldocs.info/experimental-docs/std.container.rbtree.RedBlackTree.opBinaryRight.html
But how do you add a key to the set? Currently only allowed via: a[x] = ...; -Steve
Mar 31 2016
next sibling parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 03/31/2016 01:39 PM, Steven Schveighoffer wrote:

 But how do you add a key to the set? Currently only allowed via:

 a[x] = ...;
Expanding on Walter's idea: a[x] = shared(void); // add a[x] = void; // remove Ali "ducks and runs for cover" :)
Mar 31 2016
next sibling parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Thu, Mar 31, 2016 at 02:09:30PM -0700, Ali ehreli via Digitalmars-d wrote:
 On 03/31/2016 01:39 PM, Steven Schveighoffer wrote:
 
 But how do you add a key to the set? Currently only allowed via:

 a[x] = ...;
Expanding on Walter's idea: a[x] = shared(void); // add a[x] = void; // remove Ali "ducks and runs for cover" :)
Yes you better run, that syntax is so atrocious I'm reaching for my rotten tomatoes... :-P T -- Don't modify spaghetti code unless you can eat the consequences.
Mar 31 2016
prev sibling next sibling parent tsbockman <thomas.bockman gmail.com> writes:
On Thursday, 31 March 2016 at 21:09:30 UTC, Ali Çehreli wrote:
 Expanding on Walter's idea:

   a[x] = shared(void);    // add
   a[x] = void;            // remove

 Ali
 "ducks and runs for cover" :)
And shared(void)[T] declares an add-only set, right?
Mar 31 2016
prev sibling next sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 3/31/16 5:09 PM, Ali Çehreli wrote:
 On 03/31/2016 01:39 PM, Steven Schveighoffer wrote:

  > But how do you add a key to the set? Currently only allowed via:
  >
  > a[x] = ...;

 Expanding on Walter's idea:

    a[x] = shared(void);    // add
    a[x] = void;            // remove

 Ali
 "ducks and runs for cover" :)
hm... I suppose: a[x] = void; could add. Removal is never done by assigning, only by aa.remove. -Steve
Mar 31 2016
parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Thursday, March 31, 2016 17:44:15 Steven Schveighoffer via Digitalmars-d 
wrote:
 hm... I suppose:

 a[x] = void;

 could add. Removal is never done by assigning, only by aa.remove.
Well, from the standpoint of it being a map, you could argue that _every_ key is in the set. It's just that some of them map to true and most of them map to false. But that's just trying to find a way to think about it that makes Walter's suggestion consistent with what we have now, I guess. Still, while it's true that aa.remove is how you'd normally do it, I think that Walter's suggestion of assigning true or false makes by far the most sense of the ones made thus far - and you could just make aa.remove(key); and aa[key] = false; equivalent for void[T] to make it more consistent. - Jonathan M Davis
Mar 31 2016
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 3/31/2016 2:09 PM, Ali Çehreli wrote:
 Expanding on Walter's idea:

    a[x] = shared(void);    // add
    a[x] = void;            // remove
For shame!
 Ali
 "ducks and runs for cover" :)
The internet is forever :-)
Mar 31 2016
parent reply Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Thursday, March 31, 2016 14:45:18 Walter Bright via Digitalmars-d wrote:
 On 3/31/2016 2:09 PM, Ali ehreli wrote:
 Expanding on Walter's idea:
    a[x] = shared(void);    // add
    a[x] = void;            // remove
For shame!
 Ali
 "ducks and runs for cover" :)
The internet is forever :-)
LOL. Except that as with everything, Murphy is at work. If it's something that you want to be around forever, it probably won't be, but if it's something that you don't want to be around, then it probably will be until the end of time. :) Either way, there's no running from bad suggestions in the newsgroup. We have the proof! ;) - Jonathan M Davis
Mar 31 2016
parent Walter Bright <newshound2 digitalmars.com> writes:
On 3/31/2016 7:31 PM, Jonathan M Davis via Digitalmars-d wrote:
 LOL. Except that as with everything, Murphy is at work. If it's something
 that you want to be around forever, it probably won't be, but if it's
 something that you don't want to be around, then it probably will be until
 the end of time. :)

 Either way, there's no running from bad suggestions in the newsgroup. We
 have the proof! ;)
Sorta like how a dropped peanut butter and jelly sandwich always lands face down!
Mar 31 2016
prev sibling parent Adam D. Ruppe <destructionator gmail.com> writes:
On Thursday, 31 March 2016 at 20:39:36 UTC, Steven Schveighoffer 
wrote:
 But how do you add a key to the set? Currently only allowed via:

 a[x] = ...;
Oh yeah... when I use a built in AA as a set now, I either set it to true or to itself: string[string] lameSet; lameSet[a] = a; lameSet.remove(a); so i guess one of those could happen
Mar 31 2016
prev sibling next sibling parent reply Q. Schroll <qs.il.paperinik gmail.com> writes:
On Thursday, 31 March 2016 at 19:57:50 UTC, Walter Bright wrote:
 aa[x] = true;  // add member x
 aa[x] = false; // remove member x
 x in aa; // compile error
On Friday, 1 April 2016 at 02:36:35 UTC, Jonathan M Davis wrote:
 Still, while it's true that aa.remove is how you'd normally do 
 it, I think that Walter's suggestion of assigning true or false 
 makes by far the most sense of the ones made thus far - and you 
 could just make

 aa.remove(key);

 and

 aa[key] = false;

 equivalent for void[T] to make it more consistent.

 - Jonathan M Davis
The basic idea is great. But how could the details look like? What do we want in detail? We want simple and suggestive operations on sets, like modification of single elements, iteration, union, intersection, (relative) complement, cartesian product, pointwise function application, filtering and much more. Maybe even suggestive set comprehension is possible. About the special case: We encounter (yet another) special case for something built of void. This is not a major deal. Everyone knows (should know) that void is a special case nearly everywhere it emerges: • void returning functions. • void* is much different from any other pointer. • void[] and void[n] are different from usual arrays. Now we add • void[T] is different from K[T] (for K != void). From the view of a D programmer, this is not a big deal to accept. From the view of a D learner, this is yet another void special case, maybe even easier to fully understand than void*. First of all, we do not use the term associative array for sets. This is wrong and confusing at least for the beginners. We can have AA declaration syntax without AA indexing syntax. The set indexing syntax will be a bit different. void[T] s; // declare s as a set of T s.add(x); // add x of type T s.remove(x); // remove x of type T auto r1 = x in s; // r1 is of type bool; r1 == true iff x is --- in s. auto r2 = x !in s; // r2 is of type bool; r2 == true iff x is not in s. Further we allow not only for convenience s[x] = true; // Same side effect of add. s[x] = false; // Same side effect of remove. This is not AA indexing syntax so let's call it set indexing and nothing else. It looks similar to bool[T] syntax, but a void[T] is different from bool[T] by design and idea. The methods add and remove return bool values that indicate the state being changed: • add returns true iff key has not been already present. • remove returns true iff key has been already present. The opIndexAssign should return the assigned bool; everything else would be totally unexpected. It is a bit like assigning the expression x in s which is an rvalue. It is illegal to use the opIndex with parameters. The only legal indexing expressions will be • s[]: legally used to operate on the set pointwise (see later). • s[x] = b • s[x] op= b, where op is one of |, &, ^: s[x] op= b does s[x] = (x in s) op b. I don't see an application of the latter, but there is no reason to disallow it; rather discourage it. When assigning bool literals with set indexing syntax where the value of the assignment is not used, the compiler should emit a warning and suggest using add or remove respectively. bool b = expression(); s[x] = true; // compiler suggests using add. s[x] = false; // compiler suggests using remove. s[x] = b; // ok, b is not a literal. s[x] = expression(); // ok. s[x] = s[y] = true; // ok; for s[y] = true, the value (true) is being used, // for s[x] we have s[y] = true as expression. Known from AAs we also will have • sizeof • length • dup • rehash • clear in the expected form, but we won't have • keys • values • byKey() • byValue() That is because to be it is odd to call the elements keys. And what are the values then? We don't even need these. New/changed ones: • singelton (new) • get (known from AA, but other sematics) For a singelton set, singelton returns the only element. Otherwise RangeError. get returns a pointer to the only element of a singelton set or null for the empty set. If the set contains more than one element, RangeError. get can be useful with if (auto xp = s.get) { /+ use the unique element x = *p +/ } else { /+ empty set handling +/ } [Aside: There is no add for AAs for a good reason.] Iteration: foreach (ref x; s) // ref is optional! { ... } Because the pseudo index type is void, there are no index values. So indexed iteration is illegal. foreach (i, ref x; s) // compile-time error. { ... } Sets cannot be lockstepped over; that would need canoncial order. But it makes sense to chain sets etc. Initialization: The set can also be initialized by a value of T, T[] or bool[T]. void[T] s; // makes empty set. void[T] s = x; // x of type T: Makes singleton set. void[T] s = [ a, b ]; // x in s iff x == a or x == b void[T] s = [ a:true, b:false ]; // x in s iff x == a. If a set is initialized by an AA literal with only literal bools, the compiler should suggest using an array instead. There is no need for a special set literal. We could allow void[T] s = [ a:, b: ]; The colon is from the AA literal syntax, with no value to the key as void has no values. We could allow assigning any AA and taking the keys only. That would make the usage of bool[T] inconsistent. It is better to use void[T] s = aa.keys; // if aa of type S[T] void[T] s = aa.values; // if aa of type T[S] We could allow further s[x, y] = b; // nothing different from s[x] = s[y] = b; and void[T] t s[t] = b; // foreach (x; t) s[x] = b; Set operations (oh, no... maths): void[int] s = [ 0, 1 ]; void[int] t = [ 0, 2 ]; void[int] u = [ 0, 1, 2 ]; // s ∪ t void[int] i = [ 0 ]; // s ∩ t void[int] d = [ 1, 2 ]; // s Δ t void[int] m1 = [ 1 ]; // s \ t void[int] m2 = [ 2 ]; // t \ s assert (s | t == u); // union assert (s & t == i); // intersection assert (s ^ t == d); // symmetric difference assert (s - t == m1); // relative complement assert (s / t == m2); // reverse relative complement assert (s ~ t == u); // union (alias); compiler should suggest using |. Rationale for using bit/logic operators? Let op be one of |, & or ^. Then x in (s op t) == (x in s) op (x in t) This is very consistent with assigning bools in indexing expressions. Rationale for better not using ~ for sets at all: Sets are different from arrays by idea. It is fundamental for arrays that int[] a, b; assert ((a ~ b).length == a.length + b.length); holds. For sets it does not. Maybe this is interesting: • s[t] = true does s |= t. • s[t] = false does s -= t. [I have thought about the disjoint union of sets. One problem is the two meanings of this term. There seems not to be a perfect solution to this issue.] Union and intersection: void[void[T]] ss; // set of sets. auto u = join(ss); // u is of type void[T] auto i = intersect(ss); // i is of type void[T] Also we have disjoint, that returns if either a single set of sets has disjoint elements or when given more than one parameter, tests if the given sets are disjoint. auto r1 = disjoint(ss); // set of sets void[S] s; void[T] t; // Assume the comapaison x == y is legal for S x; T y; auto r2 = disjoint(s, t); // some sets Pointwise application of a function: In math there is f[s] for { f(x) | x in s }. We cannot use this great notation directly. What can be done is auto r = pointwise(&f, s); // f.pointwise(s); and/or auto r = pointwise(s, &f); // s.pointwise(f); It is possible to distinguish sets and functions perfectly. The option s[f] is open, but looks very odd. Another way to go is struct pointwise(alias f) if (!is(Parameters!f == AliasSeq!())) { alias T = Parameters!f[0]; alias Args = Parameters!f[1 .. $]; static opCall(T x, Args args) { return f(x, args); } static opIndex(void[T] s, Args args) { alias R = typeof(f(s.singelton)); void[R] result; foreach (x; s) result.add(f(s, args)); return result; } } alias f = pointwise!fBase; f(x, args); // simple application f[s, args]; // pointwise application on a set. Further we should provide a mechanism for f[[S]] = { f[s] | s in S }, i.e. alias f = pointwise!(pointwise!fBase); f(x, args); // simple application f[ss, args]; // pointwise application on a set of sets. // pointwise application on a set not possible via f. The main problem is that a function can be overloaded with R f(void[T] s, Args) and R f( T x, Args) It is possible but not desirable to make pointwise detect these cases and forward opIndex to opCall. For this, there can be a separate solution. We can have pointwise operator application rather easily. void[S] s; void[T] t; for any overloadable unary operator op: op s[] is like { op x | x in s } alias R = typeof(op s.singelton); void[R] r; foreach (x; s) r.add(op x); for any overloadable binary operator op: s[] op t[] is like { x op y | x in s, y in t }, alias R = typeof(s.singelton op t.singelton); void[R] r; foreach (x; s) foreach (y; t) r.add(x op y); These can be computed lazily under certain circumstands, e.g. if the sets are immutable or in foreach (x; s[] + t[]) { ... } if s and t are not changed in the foreach body. We can allow filtering a set by condition via auto t = s(predicate); // typeof(t) == typeof(s) Set comprehension: The mathematical notation is not unambiguous and partly informal. The minimal support of set comprehension is { f(x1,..., xn) | x1 in s1,..., xn in sn, predicate1(x1,..., xn) ... predicatem(x1,..., xn) } We have an expression on the left, bindings and predicates on the right. Maybe one way is a template function setComp!("f(x1, ..., xn)", "x1 in s1, ..., xn in sn", "predicate1(x1, ..., xn) ... predicatem(x1, ..., xn)") with predicates optional. One thing I have left out? Yes, the complement. void[T] s; void[T] t = ~s; We can decide, wether the complement is referentially bound to the original or not. This is an issue but not the major one. Let's say no, use a copy and go on. As some types are infinite, we must simulate complements. The easiest one is having a private bool isComplement to indicate wether the content semantically is the set or the complement. For a complement, the operations • x in s • s[x] = b • s | t, s & t, s ^ t, etc. can be emulated perfectly. The great issue is iteration over complements. One solution is making complements another type, because being able to iterate a set just sometimes is inacceptable. For some types of sets, like void[bool] which has the four values [ ], [ false ], [ true ], [ false, true ], complements are easy. This holds for all finite types, but is impracticable for lange ones like long. It makes sense to have special treatment for small enums. In addition, one of D's goals is to fit user defined types best into the language. We need an interface for user defined types that tell that the complement operation on sets of them is a meaningful thing and not just a coated set.
Apr 01 2016
next sibling parent reply cym13 <cpicard openmailbox.org> writes:
On Friday, 1 April 2016 at 08:52:40 UTC, Q. Schroll wrote:
 [...]
I most of what is said here, assigning true or false makes for an aweful API compared to add() and remove(). I agree with Adam Ruppe that if we are to use AA-like syntax we have to keep a coherent API. Also, I don't like join etc... Please, just take the python semantics. Sets have been a builtin type for a long time now in that language and they just make sense, they are very polished. Not to mention that many people that expect sets to be part of the language itself seem to come from python. https://docs.python.org/3/library/stdtypes.html?highlight=set#set
Apr 01 2016
parent Q. Schroll <qs.il.paperinik gmail.com> writes:
On Friday, 1 April 2016 at 09:55:58 UTC, cym13 wrote:
 On Friday, 1 April 2016 at 08:52:40 UTC, Q. Schroll wrote:
 [...]
I most of what is said here, assigning true or false makes for an aweful API compared to add() and remove(). I agree with Adam Ruppe that if we are to use AA-like syntax we have to keep a coherent API.
I don't like the AA-like syntax also. But in some sense it is straightforward. Look at s[x, y] = true; You can have a overload of add making s.add(x, y) do that. But wait, add has a return value. Let x be already present in s and y not. What would you expect s.add(x, y) to return? This is unclear and ambiguous. In this case, I find the AA-like syntax nicer. I've read through the thread without exactly tracking who said what. On Thursday, 31 March 2016 at 20:11:39 UTC, Adam D. Ruppe wrote:
 aa[x] returns void, which, having no value, would be a compile 
 error.
The idea is great and I've adopted it in some sense. I don't know the API, so I cannot tell if something slightly hurts it. Is the add-funtion coherent API?
 Also, I don't like join etc... Please, just take the python 
 semantics.
Interestingly, I've never seen meaningful Python code -- you can believe it or not. Most of the proposal is very near to Python, right? The link let's me at least believe it is. Actually this proves the stuff is natural to people. Unfortunately, union is a keyword in D, so we just can't use it. You can propose another name for set union if you are dissatisfied with join. I don't stick very much to that. Syntax highlighting does a good job here to tell someone union will likely not compile. Is this all? What does your "etc." mean?
 Sets have been a builtin type for a long time now in that 
 language and they just
 make sense, they are very polished.
Sounds like we should have sets too and profit from the experience.
 Not to mention that many people that expect sets to be part of 
 the language itself seem to come from python.
Apr 01 2016
prev sibling parent Q. Schroll <qs.il.paperinik gmail.com> writes:
On Friday, 1 April 2016 at 08:52:40 UTC, Q. Schroll wrote:
 The methods add and remove return bool values that indicate the 
 state being changed:
 • add    returns true iff key has not been already present.
 • remove returns true iff key has     been already present.
Should have been
 The methods add and remove return bool values that indicate the 
 state being changed:
  • add    returns true iff element has not been already present.
  • remove returns true iff element has     been already present.
as we shouldn't call the elements of a set its "keys".
Apr 01 2016
prev sibling parent Jacob Carlborg <doob me.com> writes:
On 2016-03-31 21:57, Walter Bright wrote:
 On 3/31/2016 12:44 PM, H. S. Teoh via Digitalmars-d wrote:
 Ah, makes sense.  But what would aa[x] return?
A bool indicating membership.
 And how would you add elements to it?
aa[x] = true; // add member x aa[x] = false; // remove member x x in aa; // compile error
Looks really weird to me. I was thinking something like this: void[int] set; set ~= 3; set ~= 4; set.remove(3); bool present = 4 in set; // returns a bool and not a pointer -- /Jacob Carlborg
Apr 02 2016
prev sibling next sibling parent tsbockman <thomas.bockman gmail.com> writes:
On Thursday, 31 March 2016 at 19:24:14 UTC, deadalnix wrote:
 Pretty much as per title. I has that in the back of my mind for 
 a while. Would that work ?
I like this idea. I actually thought of it myself before, which suggests that the syntax would be somewhat intuitive and therefore easy to remember.
Mar 31 2016
prev sibling next sibling parent reply Jack Stouffer <jack jackstouffer.com> writes:
On Thursday, 31 March 2016 at 19:24:14 UTC, deadalnix wrote:
 Pretty much as per title. I has that in the back of my mind for 
 a while. Would that work ?
Wouldn't just be better to use a std.allocator backed set container instead over special casing the AA syntax like this?
Mar 31 2016
parent BLM768 <blm768 gmail.com> writes:
On Thursday, 31 March 2016 at 20:51:53 UTC, Jack Stouffer wrote:
 Wouldn't just be better to use a std.allocator backed set 
 container instead over special casing the AA syntax like this?
Syntactically, that makes more sense. Or there's always ubyte[0][T].
Mar 31 2016
prev sibling next sibling parent reply Daniel Murphy <yebbliesnospam gmail.com> writes:
On 1/04/2016 6:24 AM, deadalnix wrote:
 Pretty much as per title. I has that in the back of my mind for a while.
 Would that work ?
Don't forget that builtin AAs have been an epic disaster, and this would require an appalling amount of effort to implement in the compiler types, ctfe, druntime, new traits etc. Phobos seems like a better place - and while not quite as concise, the syntax should still be pretty intuitive.
Apr 01 2016
next sibling parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Fri, Apr 01, 2016 at 07:26:46PM +1100, Daniel Murphy via Digitalmars-d wrote:
 On 1/04/2016 6:24 AM, deadalnix wrote:
Pretty much as per title. I has that in the back of my mind for a
while.  Would that work ?
Don't forget that builtin AAs have been an epic disaster, and this would require an appalling amount of effort to implement in the compiler types, ctfe, druntime, new traits etc. Phobos seems like a better place - and while not quite as concise, the syntax should still be pretty intuitive.
Yeah, having yet another language builtin is a bad idea, it complicates the compiler and ties you to a specific implementation of sets. Why not just Set!T instead, implemented in Phobos? Sets behave pretty much like bit arrays, so for operations you can have: Set!T s1, s2, s3 T e; s1.add(e); s2.remove(e); auto s3 = s1 | s2; // union auto s4 = s1 & s2; // intersection auto s5 = s1 * s2; // cartesian product auto s6 = s1 - s2; // set difference auto s7 = s1 ^ s2; // symmetric difference which gives us nice enough syntax for standard set operations, perfectly implementable via operator overloading in a library. (Note: above operators are only suggestions.) I don't think AA syntax is very well-suited for sets. (What on earth is `set[x] = true` supposed to mean?! You want to add an element to the set, not to set an element to true in the set. It doesn't make sense mnemonically.) T -- What did the alien say to Schubert? "Take me to your lieder."
Apr 01 2016
prev sibling parent reply Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Friday, April 01, 2016 19:26:46 Daniel Murphy via Digitalmars-d wrote:
 On 1/04/2016 6:24 AM, deadalnix wrote:
 Pretty much as per title. I has that in the back of my mind for a while.
 Would that work ?
Don't forget that builtin AAs have been an epic disaster, and this would require an appalling amount of effort to implement in the compiler types, ctfe, druntime, new traits etc. Phobos seems like a better place - and while not quite as concise, the syntax should still be pretty intuitive.
Given that we already have built-in AA's, I like the idea of adding sets like this, but it wouldn't surprise me at all if it were ultimately a bad idea. Certainly, I agree that having AA's built into the language has turned into a disaster even though it's theoretically very nice to have - and it has turned out quite well for the basic use cases. It just falls apart completely once you start caring about stuff like const and immutable and anything complicated. As it stands, if someone wants a set with Phobos, we have RedBlackTree in std.container. So, we actually have sets already. But all of that will presumably be getting an overhaul with what Andrei has been up to. - Jonathan M Davis
Apr 01 2016
parent reply matovitch <camille.brugel laposte.net> writes:
On Friday, 1 April 2016 at 12:45:23 UTC, Jonathan M Davis wrote:
 On Friday, April 01, 2016 19:26:46 Daniel Murphy via 
 Digitalmars-d wrote:
 On 1/04/2016 6:24 AM, deadalnix wrote:
 Pretty much as per title. I has that in the back of my mind 
 for a while. Would that work ?
Don't forget that builtin AAs have been an epic disaster, and this would require an appalling amount of effort to implement in the compiler types, ctfe, druntime, new traits etc. Phobos seems like a better place - and while not quite as concise, the syntax should still be pretty intuitive.
Given that we already have built-in AA's, I like the idea of adding sets like this, but it wouldn't surprise me at all if it were ultimately a bad idea. Certainly, I agree that having AA's built into the language has turned into a disaster even though it's theoretically very nice to have - and it has turned out quite well for the basic use cases. It just falls apart completely once you start caring about stuff like const and immutable and anything complicated. As it stands, if someone wants a set with Phobos, we have RedBlackTree in std.container. So, we actually have sets already. But all of that will presumably be getting an overhaul with what Andrei has been up to. - Jonathan M Davis
I don't know about the implementation of redblack tree in phobos, but I am willing to bet on a large performance drawback if you compare it against an optimized hash table (for example using robin-hood open addressing techniques). And I guess it is for sorted set (like a heap) with O(log N) insertion and deletion (although this may be just a theoretical worry)...Furthermore, the template constraint indicate the need of a less predicate which you may not need or want to define.
Apr 01 2016
next sibling parent reply Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Friday, April 01, 2016 12:57:12 matovitch via Digitalmars-d wrote:
 On Friday, 1 April 2016 at 12:45:23 UTC, Jonathan M Davis wrote:
 As it stands, if someone wants a set with Phobos, we have
 RedBlackTree in std.container. So, we actually have sets
 already. But all of that will presumably be getting an overhaul
 with what Andrei has been up to.
I don't know about the implementation of redblack tree in phobos, but I am willing to bet on a large performance drawback if you compare it against an optimized hash table (for example using robin-hood open addressing techniques). And I guess it is for sorted set (like a heap) with O(log N) insertion and deletion (although this may be just a theoretical worry)...Furthermore, the template constraint indicate the need of a less predicate which you may not need or want to define.
RedBlackTree is a red-black-tree, so it's a sorted set with whatever pros and cons come with that. Having a hash set would have different pros and cons. Ideally, we would have both, and I expect that we will eventually, but at the moment, we just have RedBlackTree, but that's more than nothing, and it's exactly what would be needed for many use cases even if a hash set were available. - Jonathan M Davis
Apr 01 2016
parent reply matovitch <camille.brugel laposte.net> writes:
On Friday, 1 April 2016 at 15:39:05 UTC, Jonathan M Davis wrote:
 On Friday, April 01, 2016 12:57:12 matovitch via Digitalmars-d 
 wrote:
 On Friday, 1 April 2016 at 12:45:23 UTC, Jonathan M Davis 
 wrote:
 As it stands, if someone wants a set with Phobos, we have 
 RedBlackTree in std.container. So, we actually have sets 
 already. But all of that will presumably be getting an 
 overhaul with what Andrei has been up to.
I don't know about the implementation of redblack tree in phobos, but I am willing to bet on a large performance drawback if you compare it against an optimized hash table (for example using robin-hood open addressing techniques). And I guess it is for sorted set (like a heap) with O(log N) insertion and deletion (although this may be just a theoretical worry)...Furthermore, the template constraint indicate the need of a less predicate which you may not need or want to define.
RedBlackTree is a red-black-tree, so it's a sorted set with whatever pros and cons come with that. Having a hash set would have different pros and cons. Ideally, we would have both, and I expect that we will eventually, but at the moment, we just have RedBlackTree, but that's more than nothing, and it's exactly what would be needed for many use cases even if a hash set were available. - Jonathan M Davis
Indeed, just wanted to point that out. (I guess that's why the set was introduced before the unordered one in the c++ stl as well). I feel like containers are an old topic. Last time I asked I was told : wait for the allocators. What is the advancement on this side ? Are there any plan at writing more containers for phobos ? (I know that I am in the bad position of complaining...but if there is no obstacle...I am ready to write a draft of hashset in D, although surely not to phobos standards)
Apr 01 2016
parent reply Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Friday, April 01, 2016 15:52:49 matovitch via Digitalmars-d wrote:
 Indeed, just wanted to point that out. (I guess that's why the
 set was introduced before the unordered one in the c++ stl as
 well). I feel like containers are an old topic. Last time I asked
 I was told : wait for the allocators. What is the advancement on
 this side ? Are there any plan at writing more containers for
 phobos ? (I know that I am in the bad position of
 complaining...but if there is no obstacle...I am ready to write a
 draft of hashset in D, although surely not to phobos standards)
Now that Andrei has finished the allocators, he's redesigning the containers, and supposedly, std.container is going to be replaced with what he's working on (it'll probably called something like std.collection). How far along he is, or when he'll actually present anything approaching a final design, I don't know. He's posted a container or two for discussion previously, but they were more esoteric things, and he was clearly still working on a lot of the overall design of how the containers in general would be put together (e.g. how they would handle Big-O in their API). Once Andrei is farther along, I'm sure that he'll be looking for contributions towards filling out a full set of containers based on his general container API, but for now I'd suggest that folks just use the EMSI containers. - Jonathan M Davis
Apr 01 2016
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 04/01/2016 02:29 PM, Jonathan M Davis via Digitalmars-d wrote:
 On Friday, April 01, 2016 15:52:49 matovitch via Digitalmars-d wrote:
 Indeed, just wanted to point that out. (I guess that's why the
 set was introduced before the unordered one in the c++ stl as
 well). I feel like containers are an old topic. Last time I asked
 I was told : wait for the allocators. What is the advancement on
 this side ? Are there any plan at writing more containers for
 phobos ? (I know that I am in the bad position of
 complaining...but if there is no obstacle...I am ready to write a
 draft of hashset in D, although surely not to phobos standards)
Now that Andrei has finished the allocators, he's redesigning the containers, and supposedly, std.container is going to be replaced with what he's working on (it'll probably called something like std.collection). How far along he is, or when he'll actually present anything approaching a final design, I don't know. He's posted a container or two for discussion previously, but they were more esoteric things, and he was clearly still working on a lot of the overall design of how the containers in general would be put together (e.g. how they would handle Big-O in their API). Once Andrei is farther along, I'm sure that he'll be looking for contributions towards filling out a full set of containers based on his general container API, but for now I'd suggest that folks just use the EMSI containers.
Work on containers has been on hold for three reasons: 1. Paper submission to a conference (more details soon) 2. DConf organizing stuff 3. RCString work, which can proceed in the current language 4. Work on a DIP that allows safe reference counting. I am confident we'll have good results for all of the above (and containers too). Andrei
Apr 02 2016
next sibling parent w0rp <devw0rp gmail.com> writes:
Has no one mentioned void[0][T] yet?

alias Set(T) = void[0][T];

void add(T)(ref void[0][T] set, T key) {
     set[key] = (void[0]).init;
}

bool contains(T)(inout(void[0][T]) set, T key) {
     return (key in set) !is null;
}

void main() {
     Set!int set;

     set.add(1);

     assert(set.contains(1));

     set.remove(1);

     assert(!set.contains(1));
}
Apr 04 2016
prev sibling parent matovitch <camille.brugel laposte.net> writes:
On Saturday, 2 April 2016 at 16:00:29 UTC, Andrei Alexandrescu 
wrote:
 Work on containers has been on hold for three reasons:

 1. Paper submission to a conference (more details soon)

 2. DConf organizing stuff

 3. RCString work, which can proceed in the current language

 4. Work on a DIP that allows safe reference counting.

 I am confident we'll have good results for all of the above 
 (and containers too).


 Andrei
Thanks for the updates (and for your work !), can't wait for DConf ! :)
Apr 06 2016
prev sibling parent reply Jack Stouffer <jack jackstouffer.com> writes:
On Friday, 1 April 2016 at 12:57:12 UTC, matovitch wrote:
 I don't know about the implementation of redblack tree in 
 phobos, but I am willing to bet on a large performance drawback 
 if you compare it against an optimized hash table (for example 
 using robin-hood open addressing techniques). And I guess it is 
 for sorted set (like a heap) with O(log N) insertion and 
 deletion (although this may be just a theoretical 
 worry)...Furthermore, the template constraint indicate the need 
 of a less predicate which you may not need or want to define.
https://economicmodeling.github.io/containers/containers/hashset.HashSet.html There, save everyone the trouble of implementing this in the compiler and complicating the language with special casing by just using that.
Apr 01 2016
parent matovitch <camille.brugel laposte.net> writes:
On Friday, 1 April 2016 at 15:45:13 UTC, Jack Stouffer wrote:
 On Friday, 1 April 2016 at 12:57:12 UTC, matovitch wrote:
 I don't know about the implementation of redblack tree in 
 phobos, but I am willing to bet on a large performance 
 drawback if you compare it against an optimized hash table 
 (for example using robin-hood open addressing techniques). And 
 I guess it is for sorted set (like a heap) with O(log N) 
 insertion and deletion (although this may be just a 
 theoretical worry)...Furthermore, the template constraint 
 indicate the need of a less predicate which you may not need 
 or want to define.
https://economicmodeling.github.io/containers/containers/hashset.HashSet.html There, save everyone the trouble of implementing this in the compiler and complicating the language with special casing by just using that.
Yep ! The code is even there.
Apr 01 2016
prev sibling next sibling parent reply Dejan Lekic <dejan.lekic gmail.com> writes:
On Thursday, 31 March 2016 at 19:24:14 UTC, deadalnix wrote:
 Pretty much as per title. I has that in the back of my mind for 
 a while. Would that work ?
I am not sure about that... I would rather have a completely new type (`set`) for this purpose.
Apr 01 2016
parent matovitch <camille.brugel laposte.net> writes:
On Friday, 1 April 2016 at 11:59:29 UTC, Dejan Lekic wrote:
 On Thursday, 31 March 2016 at 19:24:14 UTC, deadalnix wrote:
 Pretty much as per title. I has that in the back of my mind 
 for a while. Would that work ?
I am not sure about that... I would rather have a completely new type (`set`) for this purpose.
Agreed, although it looked like a good idea at first, void[T] is kind of obscture when you compare it to std::unordered_set<T> in C++. Although unordered_map are really practical to the point lua made it its only data structure (behind the scene of a dynamic language), when I first encountered D I thought this was sad to have add it as a build-in construct (phobos would have done fine). This thread point out one don't have a satifactory way to insert or erase keys and code a specific behavior for void[T] just remove all the interest of the similarty with AAs that we are looking for in the first place.
Apr 01 2016
prev sibling next sibling parent Meta <jared771 gmail.com> writes:
On Thursday, 31 March 2016 at 19:24:14 UTC, deadalnix wrote:
 Pretty much as per title. I has that in the back of my mind for 
 a while. Would that work ?
We could do something similar as what's done with string and add an `alias set(T) = void[T]`, then provide the necessary helper functions such as add and remove. However, that still leaves no way to initialize a set with a literal.
Apr 01 2016
prev sibling parent Jacob Carlborg <doob me.com> writes:
On 2016-03-31 21:24, deadalnix wrote:
 Pretty much as per title. I has that in the back of my mind for a while.
 Would that work ?
An alternative syntax for declaring a set could be: [int] set; Not sure if that conflicts with any existing syntax. -- /Jacob Carlborg
Apr 02 2016