digitalmars.D - Could we reserve void[T] for builtin set of T ?
- deadalnix (2/2) Mar 31 2016 Pretty much as per title. I has that in the back of my mind for a
- H. S. Teoh via Digitalmars-d (5/7) Mar 31 2016 What's a "builtin set of T"?
- deadalnix (2/8) Mar 31 2016 https://en.wikipedia.org/wiki/Set_%28abstract_data_type%29
- Jacob Carlborg (6/10) Mar 31 2016 int[string] is a built-in associative array, void[string] would be the
- H. S. Teoh via Digitalmars-d (7/18) Mar 31 2016 [...]
- Walter Bright (5/7) Mar 31 2016 aa[x] = true; // add member x
- H. S. Teoh via Digitalmars-d (6/16) Mar 31 2016 How is this different from bool[T] then? Just the fact that you can't
- tsbockman (5/7) Mar 31 2016 void[T] could be more efficient, since it wouldn't need to
- Walter Bright (5/7) Mar 31 2016 Differences are:
- Adam D. Ruppe (13/20) Mar 31 2016 Ewww. If it looks like an AA, let's at least keep the AA
- Steven Schveighoffer (4/23) Mar 31 2016 But how do you add a key to the set? Currently only allowed via:
- =?UTF-8?Q?Ali_=c3=87ehreli?= (6/8) Mar 31 2016 Expanding on Walter's idea:
- H. S. Teoh via Digitalmars-d (6/19) Mar 31 2016 Yes you better run, that syntax is so atrocious I'm reaching for my
- tsbockman (2/7) Mar 31 2016 And shared(void)[T] declares an add-only set, right?
- Steven Schveighoffer (5/14) Mar 31 2016 hm... I suppose:
- Jonathan M Davis via Digitalmars-d (14/17) Mar 31 2016 Well, from the standpoint of it being a map, you could argue that _every...
- Walter Bright (3/8) Mar 31 2016 The internet is forever :-)
- Jonathan M Davis via Digitalmars-d (8/16) Mar 31 2016 LOL. Except that as with everything, Murphy is at work. If it's somethin...
- Walter Bright (2/8) Mar 31 2016 Sorta like how a dropped peanut butter and jelly sandwich always lands f...
- Adam D. Ruppe (8/10) Mar 31 2016 Oh yeah... when I use a built in AA as a set now, I either set it
- Q. Schroll (273/285) Apr 01 2016 The basic idea is great. But how could the details look like?
- cym13 (14/15) Apr 01 2016 I most of what is said here, assigning true or false makes for an
- Q. Schroll (29/44) Apr 01 2016 I don't like the AA-like syntax also. But in some sense it is
- Q. Schroll (3/11) Apr 01 2016 as we shouldn't call the elements of a set its "keys".
- Jacob Carlborg (9/16) Apr 02 2016 Looks really weird to me. I was thinking something like this:
- tsbockman (4/6) Mar 31 2016 I like this idea. I actually thought of it myself before, which
- Jack Stouffer (3/5) Mar 31 2016 Wouldn't just be better to use a std.allocator backed set
- BLM768 (3/5) Mar 31 2016 Syntactically, that makes more sense.
- Daniel Murphy (6/8) Apr 01 2016 Don't forget that builtin AAs have been an epic disaster, and this would...
- H. S. Teoh via Digitalmars-d (24/34) Apr 01 2016 Yeah, having yet another language builtin is a bad idea, it complicates
- Jonathan M Davis via Digitalmars-d (12/20) Apr 01 2016 Given that we already have built-in AA's, I like the idea of adding sets
- matovitch (9/34) Apr 01 2016 I don't know about the implementation of redblack tree in phobos,
- Jonathan M Davis via Digitalmars-d (8/21) Apr 01 2016 RedBlackTree is a red-black-tree, so it's a sorted set with whatever pro...
- matovitch (9/35) Apr 01 2016 Indeed, just wanted to point that out. (I guess that's why the
- Jonathan M Davis via Digitalmars-d (13/21) Apr 01 2016 Now that Andrei has finished the allocators, he's redesigning the
- Andrei Alexandrescu (9/29) Apr 02 2016 Work on containers has been on hold for three reasons:
- Jack Stouffer (5/13) Apr 01 2016 https://economicmodeling.github.io/containers/containers/hashset.HashSet...
- matovitch (2/16) Apr 01 2016 Yep ! The code is even there.
- Dejan Lekic (3/5) Apr 01 2016 I am not sure about that... I would rather have a completely new
- matovitch (11/16) Apr 01 2016 Agreed, although it looked like a good idea at first, void[T] is
- Meta (5/7) Apr 01 2016 We could do something similar as what's done with string and add
- Jacob Carlborg (6/8) Apr 02 2016 An alternative syntax for declaring a set could be:
Pretty much as per title. I has that in the back of my mind for a while. Would that work ?
Mar 31 2016
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
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:https://en.wikipedia.org/wiki/Set_%28abstract_data_type%29Pretty 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
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: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 CarlborgPretty 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"?
Mar 31 2016
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:[...] 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.On Thu, Mar 31, 2016 at 07:24:14PM +0000, deadalnix via Digitalmars-d wrote: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%29Pretty 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"?
Mar 31 2016
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
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: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...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
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
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
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: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.Ah, makes sense. But what would aa[x] return?A bool indicating membership.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.htmlAnd 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
On 3/31/16 4:11 PM, Adam D. Ruppe wrote:On Thursday, 31 March 2016 at 19:57:50 UTC, Walter Bright wrote:But how do you add a key to the set? Currently only allowed via: a[x] = ...; -SteveOn 3/31/2016 12:44 PM, H. S. Teoh via Digitalmars-d wrote: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.Ah, makes sense. But what would aa[x] return?A bool indicating membership.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.htmlAnd 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
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
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: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.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
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
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
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
On 3/31/2016 2:09 PM, Ali Çehreli wrote:Expanding on Walter's idea: a[x] = shared(void); // add a[x] = void; // removeFor shame!Ali "ducks and runs for cover" :)The internet is forever :-)
Mar 31 2016
On Thursday, March 31, 2016 14:45:18 Walter Bright via Digitalmars-d wrote:On 3/31/2016 2:09 PM, Ali ehreli 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! ;) - Jonathan M DavisExpanding on Walter's idea: a[x] = shared(void); // add a[x] = void; // removeFor shame!Ali "ducks and runs for cover" :)The internet is forever :-)
Mar 31 2016
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
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
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 errorOn 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 DavisThe 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
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
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 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:[...]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.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
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 beenThe 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
On 2016-03-31 21:57, Walter Bright wrote:On 3/31/2016 12:44 PM, H. S. Teoh via Digitalmars-d wrote: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 CarlborgAh, 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
Apr 02 2016
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
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
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
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
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: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."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
On Friday, April 01, 2016 19:26:46 Daniel Murphy via Digitalmars-d wrote:On 1/04/2016 6:24 AM, deadalnix wrote: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 DavisPretty 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
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: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.On 1/04/2016 6:24 AM, deadalnix wrote: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 DavisPretty 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
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: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 DavisAs 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.
Apr 01 2016
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: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)On Friday, 1 April 2016 at 12:45:23 UTC, Jonathan M Davis wrote: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 DavisAs 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.
Apr 01 2016
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
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: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). AndreiIndeed, 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.
Apr 02 2016
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
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). AndreiThanks for the updates (and for your work !), can't wait for DConf ! :)
Apr 06 2016
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
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:Yep ! The code is even there.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
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
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: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.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
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
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