Sdk: const Set constructor

[nex3]

It would be useful to have the Set constructor be const to allow for the creation of frozen empty sets, a la "const []" or "const {}".

[nex3]

_Added Area-Library, Triaged labels._

[lrhn]

You should be able to make immutable Sets, but for a const Set with an arbitrary number of elements, we'd likely need language support in order to make it "not suck".
You can't pass an arbitrary number of elements to a normal const constructor, so you need to use either a List or a Map literal to collect elements, and then pass that to a const constructor. Since the constructor can't do any computation, the Set would be wrapped around the List or Map. A List would be inefficient, and canonicalization would depend on the order, so the best approach with the current syntax is to use a Map and wrap it as a Set of the Map's keys, Then it would only work with Strings:
class Set<E> {
 const factory Set.fromMapKeys(Map<E,Dynamic> values) = MapKeySet<E>;
 ...
}
That means it would be:
  const Set<String>.fromMapKeys(const <String,Null>{"A": null, "B": null})
to create a const Set of "A" and "B".

For a 'const Set' to be really viable, it should have syntax support, so I'm changing this til Area-Langauge.

---

_Added this to the Later milestone._
_Removed Area-Library label._
_Added Area-Language label._

[nex3]

_Removed the owner._

[rakudrama]

Language support for const Set<T> would be very useful.

I can find plenty of work-arounds in the codebase, e.g.

  static final Set<String> _allowedElements = new Set.from([
    'A',
    'ABBR',
    ...
    'TT',
    'U',
    'UL',
    'VAR',
    'VIDEO',
    'WBR',
  ]);

[kasperl]

_Removed this from the Later milestone._
_Added Oldschool-Milestone-Later label._

[kasperl]

_Removed Oldschool-Milestone-Later label._

[gbracha]

_Set owner to @gbracha._
_Added Accepted label._

[gbracha]

See also issue #3792. Not exactly a duplicate, but close.

[DartBot]

_This comment was originally written by @Emasoft_

---

@andrew.m : The answers are of course the following:

­1

 const Set([1, 2, 1]);
should be automatically interpreted as:
 const Set([1, 2]);
because repeated elements are always ignored. Adding an element should always check if the element already is present in the set, and if this is the case nothing will be added, rising no errors.
A set does not have repeating elements. The set A is identical to the set B when one can show A⊆B and B⊆A and therefore A=B. For example: the set {1,1,1,2,2} is by definition equal to {1}∪{1}∪{1}∪{2}∪{2}, then {1,1,1,2,2}={1,2}.
The difference between a Set and an Array is that in the Set the value of an element is also the key used to identify it, while the Array is an indexed family multiset, providing access to individual elements by their key, like an index. A multiset may be formally defined as a 2-tuple (A, m) where A is some set and m is a function from A to the set N = {1, 2, 3, .. } of positive natural numbers, called indices. A Set doesn't have an index, and consequently doesn't have any order ( the set {3,1,2} is equivalent to the set {1,2,3} ), and cannot have any repeating element, because the value of an element is also the key used to identify it. The elements in an array follow a strict order at all times, and all inserted elements are given a position in this order. The elements in a Set have not a predefined order, and thanks to this they can be merged or modified with boolean operators (es. setA.union(setB) or setA.difference(setB) boolean operations always return another new Set object. If setA and setB contain the same elements, their difference is a new empty Set object). Sets can be mutable or immutable, depending on the language implementation and on the use of the const modifier. A mutable set provide a method to add a new element without creating a new set ( like: setA.AddElement(4) ). An immutable Set instead produce a new Set object each time a Set is modified, preserving the original Set object. In an immutable set the following line rises an error: setA.AddElement(4) - Error: setA is defined as const. To add an element you should use the boolean union operator (i.e. setA.union(4) ) because that method returns a new Set object.

­2

const Set([1, 2, 1]) == const Set([1, 2])
those expression should always be evaluated to true, because of the #­1.

[DartBot]

_This comment was originally written by @Emasoft_

---

@sra :

Language support for const Set<T> would be very useful.

True. Sets should be typed with the generic notation to ensure type safety.

Also a "mixed types" set would be great. The allowed types should be only those defined with the generic syntax. Something like:

Set<FordClass, ToyotaClass, OpelClass> supported_car_models = new Set([
 toyotaCorolla1998,
 toyotaCorolla1998Verso,
 fordKa2010,
 fordKa2011,
 fordSpace1994,
 fordSpace1994Cabrio,
 fordKa2003,
 opelQuadra2014,
 opelQuadra2014Diesel,
 toyotaCorolla1995,
 toyotaCorolla1996,
 toyotaCorolla2014Hybrid
  ]);
 
Only objects belonging to those classes betwen brackets can be added or removed from the Set.
Also boolean operations between Sets of different classes should produce a Set that allows the resulting union of the two set of classes. For example:

Set<FordClass, ToyotaClass> setA = new Set();
Set<ToyotaClass, FordClass> setB = new Set();
var setC = setA.union(setB); // setC would be defined as Set<FordClass, ToyotaClass, OpelClass> type.

In other words, the statement:

typeOf(setC) == Set<FordClass, ToyotaClass, OpelClass>

would evaluate to true.

[DartBot]

_This comment was originally written by @Emasoft_

---

const Set([const Set([Color.RED, 41]), const [const Set(1, "hello")], 2]);
That is equivalent to:
const List arr1 = new List(2)[Color.RED, 41];
const Set setA = new Set(arr1);
const Set setB = new Set(1, "hello");
const List arr2 = new List(1)[setB];
const List arr3 = new List(3)[setA, arr2, 2];
const Set setC = new Set(arr3);

The resulting sets are equivalent to:

// because arr1 is interpreted as setA.AddElementsFromList(arr1)
const Set setA = new Set(Color.RED, 41);

// because the constructor overload with multiple parameters is called when there are multiple elements
const Set setB = new Set(1, "hello");

// because like above the constructor overload with multiple parameters is called when there are multiple elements, so Lists are not interpreted as a "fromList" constructor, but like a single element of type List.
const Set setC = new Set(setA, arr2, 2);

The others examples obey to the same rules I believe.

The only error is in the "s1.first" property. There is no order in a Set, so a .first property cannot exist. The only way to access elements from a Set is with the foreach operator:

foreach(object e in s1) {
   print(e);
}

Internally the foreach operator if applied to Sets choose the sequence of elements using their hash as index. So because the hash value of the int 1 is the same in both Sets, and the hash of 1 is always smaller or greater (depending of the hash function used by Dart internally) than the hash of 2, the sequence of the numbers printed by the foreach loop will always be the same, both for s1 that for s2.

But this has nothing to do with the Set per se (because it has no ordering), but with the foreach implementation details. Another method to extract the values from the Set could use a completely different method to decide the order of extraction. For example I can write a getRandomElement() method that choose to extract every time a different sequence of elements. All you can be sure is that in a Set all the informations about what element was inserted first or last is lost forever. There is not such information. Of course there is a memory ordering behind the scenes, but even that is not constant. To optimize a Set, the .union() method could choose to add a new element in a different non contiguous area of memory, or to use a previous memory segment just freed in memory because of a recent operation on the Set, to optimize the array in a way to keep each element stored in memory in a compact and contiguous segment, faster to read. Dictionaries in C++ make such optimizations behind the scenes every time. So even the allocation order of the elements in memory is not something that the Set can use, because it is completely random and can change at any time.

[DartBot]

_This comment was originally written by @Emasoft_

---

@andrew.m : I'm just telling you what an ideal set should be according to its definition. Of course the current set implemented in Dart is less than ideal, this is why we are arguing about improving it. And the .first property is surely something that should not be in the dart implementation of a set, because it is an ill defined function (there is no first element in a set) and can be misleading because it can return different results at different times, or for identical set. Yet that problem is not the subject of the issue of this post, it deserves a separate issue.

[DartBot]

_This comment was originally written by @Emasoft_

---

A linkedHashSet is not a Set. It is something else entirely. This should be corrected asap.
If you need an ideal implementation of a Set to use as reference, this is the only one:

http://www.cplusplus.com/reference/unordered_set/unordered_set/

Please note that the above c++ class, instead of featuring a ".first" method, features a ".begin" method and an ".end" method for the beginning and the end of the extraction process, making no guarantees on which specific element is considered its first element. Internally it make use of the concept of "buckets", and it distributes the elements in the bukets according to their hash value. The only thing that differ from the ideal set is the choice of making the buckets public, instead of keeping those a private member. Allowing to modify the buckets directly creates a risk of inconsistent behaviour when algorithms expect a Set to behave like a Set.

[bergwerf]

Has this been addressed already? The most pretty format would probably be const {0, 1, 2} (after the mathematical set symbols and kinda compatible with the idea of maps having only unique keys).

[munificent]

Has this been addressed already?

Nope. No update yet.

[lrhn]

Rolling this into #3792, since it asks for general set literals, and those should be able to be const too.