List, Set and Map should have a method to compare if elements are equal

[DartBot]

This issue was originally filed by [email protected]

---

What steps will reproduce the problem?

main() {
  var s1 = new Set.from([2, 4, 5]);
  var s2 = new Set.from([4, 2, 5]);
  print(s1 == s2); // expect true, prints false
  print(s1 != s2); // expect false, prints true
}

What version of the product are you using? On what operating system?

DartPad, DartEditor build 5104 on OS X

[iposva-google]

Added Area-Library, Triaged labels.

[DartBot]

This comment was originally written by @ggirou

---

Also for lists and maps
  List<String> firstList = ['one', 'two', 'three'];
  List<String> secondList = ['one', 'two', 'three'];
  
  assert(firstList == secondList);

  Map<String, int> firstMap = {'one' : 1, 'two' : 2, 'three' : 3 };
  Map<String, int> secondMap = {'one' : 1, 'two' : 2, 'three' : 3 };
  
  assert(firstMap == secondMap);

[lrhn]

We already have Set.containsAll, so Set.operator== isn't that far from the style.

There isn't necessarily a simple way to compare two sets that is faster than
   s1.size == s2.size && s1.every(s2.contains)
and a slow operator== might be a surprising performance bottleneck.

I.e., no promises, but it seems reasonable.

---

Set owner to @lrhn.
Removed Type-Defect label.
Added Type-Enhancement, Accepted labels.

[DartBot]

This comment was originally written by @seaneagan

---

are List and Map covered by this issue, or should they be filed separately ? Here's some pseudocode:

// for List
bool operator == (List other) {
  if(length != other.length) return false;
  for(int i = 0; i < length; i++) if(this[i] != other[i]) return false;
  return true;
}

// for Map
bool operator == (Map other) {
  if(length != other.length) return false;
  return getKeys().every((key) => other.containsKey(key) && this[key] == other[key]);
}

[lrhn]

On further consideration, I'm not sure it's really a good idea to identify two mutable sets just because they currently have the same elements. One might be preserving iteration order, the other not, and if they iterate elements in different orders, are they really the same Set object. They represent the same mathematical set, but mathematical equalities aren't always the correct computational equality.
I think I'd rather have a .sameElements(Set) method for when you really need that, and keep identity equality as default.

I believe Object will get a hashCode function, making all objects hashable. That complicates changing operator== on complex classes, and I'm not sure it's reasonable to do it in general on, e.g., Set. That's a further complication. If sets are equal based only on elements, we need to compute a hash value for a Set that is independent of the order that elements are iterated in. That is likely to make for a lousy hash value. It also makes either the hash value slow to compute, or the class needs to cache and update the hash value based on single element changes. Caching and updating a hash value is an unnecessary overhead if you don't use it.

All in all, I'm tipping towards not making collections override operator== by default. It's possible to have special versions that do that, but then they also need to have a strategy for computing the hashValue.

[DartBot]

This comment was originally written by [email protected]

---

It's pretty surprising to me that [1, 2, 3] != [1, 2, 3] because the lists aren't identical. It's fairly easy to add an == method to list and map, and I think we should do this. If people want something fast, they can just use the identical() method.

[lrhn]

Lists are simple relative to Set and Map because the ordering is integral to the value.
It's less obvious whether {"x":42,"y":37} == {"y":37,"x":42}, and adding equality only on lists is also confusing.

To be really safe, the hashCode of a collection with equality should be calculated every time it's queried because, since it must depend on the hashCode of the values, and the values might change even if the collection doesn't (at least for List and Map values, but Set and Map keys aren't allowed to change). That makes hashCode an expensive operation.

I.e., if we add equality, we should discourage the use of collections in places where hashCode is used (sets and keys of maps).

[DartBot]

This comment was originally written by [email protected]

---

In general, I never assume that a hash is ordered, hence {"x":42,"y":37} should == {"y":37,"x":42}.

It has always seemed strange to me to use a mutable object for a hash key; hence Python has tuples and lists, and only tuples can be used as dictionary keys.

I don't have any magical solutions to the problem you propose. However, it seems to me that making [1] == [1] is more important than making it fast to use lists as map keys.

[lrhn]

You come from a language where associative maps are called 'hash', so it makes sense that you don't expect them to be ordered. Technically, so does javascript programmers, except that their Object 'maps' have generally been implemented as having some kind of order (insertion or similar).
The underlying point is that implementing an operator== requires fixating at a specific abstraction level. If you see all Sets as equal if they have the same elements, that's one equality. If you care to distinguish between different kinds of sets (e.g., an OrderedSet and a HashSet, or a modifiable Set and an UnmodifiableSet, or any two sets which would iterate the elements in different orders) then you need a different equality.
The 'sameElements' equality can be written as a method named that, without requiring a change of hashCode. Changing operator== does require a compatible hashCode. That's why I prefer the former. I'd rather not override operator== with a slow implementation of that and hashCode, and then let those who need it use a specialized CollectionSet/CollectionMap that does its own hashing.

Lists makes it look easy because they are simple, but I would prefer that it worked the same for both List and Set and any other collection in he future.

[DartBot]

This comment was originally written by [email protected]

---

You come from a language where associative maps are called 'hash'

Actually, I come from a language where they're called dicts.

If you see all Sets as equal if they have the same elements, that's one equality. If you care to distinguish between different kinds of sets (e.g., an OrderedSet and a HashSet, or a modifiable Set and an UnmodifiableSet, or any two sets which would iterate the elements in different orders) then you need a different equality.

I don't mind if each type of set implements its own version of equality. I don't expect different types of sets to ever be equal.

The 'sameElements' equality can be written as a method named that, without requiring a change of hashCode.

Given your arguments above, I would find such an approach acceptable, although I still think it's going to cause confusion for a lot of programmers. I'd rather have a smart version of ==, and not be able to use things like sets, maps, and lists for hash keys, but I understand that that approach probably won't happen.

I wish there were some way to leave == undefined for lists, maps, and sets so that people would know that they either have to choose to use sameElements or identical. However, I can't think of a way that could be enforced statically.

[floitschG]

The core implementations of List, Set and Map will not look at their content to compute equality. In addition to the concerns expressed by Lasse (for example, comment 5) it is also difficult to implement (especially with cyclic data-structures).
However we are still considering a comparison method on List, Set and Map (see comment 9).
I'm changing the title of this bug accordingly.

---

Changed the title to: "List, Set and Map should have a method to compare if elements are equal".

[floitschG]

Issue #3611 has been merged into this issue.

[pavelgj]

I just spent 30 minutes trying to compare two simple maps... this is not a good developer/user experience.

I agree with most of the arguments against implementing == on maps/lists/sets, but the bottom line -- there must be a way to do at least trivial comparisons of maps/lists/sets. Maybe moving unittest/matcher.dart into dart:collection.

[lrhn]

Issue #10391 has been merged into this issue.

[DartBot]

This comment was originally written by [email protected]

---

It bites me as well. I came from java background and I was really surprised that there is no equality check on List and Set. At least it should be documented.

[lrhn]

You can now use package:collection/equality.dart to create custom equalities for collections and maps.

For example, just comparing two lists for having (operator==) equal elements, you can do:

var listEq = const ListEquality();
bool equals = listEq.equals(list1, list2);

If you want to check them for identity, do:

const listId = const ListEquality(const IdentityEquality());
bool identicalElements = listId.equals(list1, list2);

To make a set of lists that are considered equal if they have identical elements, do:

var setListId = const SetEquality(listId);
Set set = new HashSet(equals: setListId.equals,
                        hashCode: setListId.hash,
                        isValidKey: setListId.isValidKey);

Please play around with this and see if you find any bugs :)

We don't plan on putting a simple equality on collections at this point. There are too many different ways you might want to define the equality, and it may or may not correspond to the internal equality used by a HashSet or HashMap.

[sethladd]

collection_helpers is not in pub, nor is it documented on api.dartlang.org. I went to go add this advice to StackOverflow but I couldn't link to anything :)

[sethladd]

Correction, it's in pub. Search wasn't updated.

[DartBot]

This comment was originally written by [email protected]

---

Just my 0.02, I think its a shame that this is not a planned feature for Dart. The fact that things like {"a": 1} == {"a": 1} "just work" in languages like Python make them a joy to work with.

The fact that things like this are so difficult to do in JavaScript is one of the things that makes Dart so promising.

I get that there's subtleties involved, but I think Dart is missing out on an opportunity here if we have to hunt down third party libraries to just get simple things like this to work.

[ejain]

var setListId = const SetEquality(listId);
Set set = new HashSet(equals: setListId.equals,
                        hashCode: setListId.hashCode,
                        isValidKey: setListId.isValidKey);

Couldn't get the code above to work anymore, but this does:

Set<List<T>> set = EqualitySet<List<T>>(ListEquality<T>());

[lrhn]

The code has (well, had, I've fixed them now) two typos, sorry about that. Try:

const listId = const ListEquality(const IdentityEquality());  // Needs to be const.
var setListId = const SetEquality(listId);
Set set = new HashSet(
    equals: setListId.equals,
    hashCode: setListId.hash,   // not .hashCode.
    isValidKey: setListId.isValidKey);

[ejain]

The code has (well, had, I've fixed them now) two typos, sorry about that. Try:

Can this code be made to work with generic type parameters?

const listId = const ListEquality<int>(const IdentityEquality());
var setListId = const SetEquality<List<int>>(listId);
Set<int> set = new HashSet<int>(
    equals: setListId.equals, // assignment error
    hashCode: setListId.hash,   // assignment error
    isValidKey: setListId.isValidKey);      

[ThinkDigitalSoftware]

Came here because I was looking to find a List<E>.toSet(E Function(List<E>, E) comparator) function because the List I'm trying to work with has duplicates, but I can't override the == operator and hashcode because it's not my code, and because I can't check to see if an element is in a list using my own function, toSet would have worked, except there not an option to make your own comparisons.

[lrhn]

Try SplayTreeSet(comparator).addAll(list).

Most sets are not comparator-based, but instead equals/hashCode based. You can create a custom such using HashSet(equals: yourEquals, hashCode: yourHash)

[ThinkDigitalSoftware]

Hey, that's helpful, thanks!

[cedvdb]

It is a bit of a downer that there is nothing streamlined on equality accross the board.

For instance if you use collection setEqual, you'd have to have a special matcher in testing to have an acceptable output:

expect(1, equals(2)); // will print expected<1>, actual<2>
expect(setEquals({}, {1}), isTrue);  // will print expected<true>, actual<false>

Is support on a deeper language level, like equals & == in java, not deemed worth it ? If equals was on object, there would be a matcher and no problem for sets, lists maps by now. But maybe this is a design decision that has good reasons ?

I would personnally turn it around though, isSameRef and == instead of == (same ref) & equals.

[lrhn]

@cedvdb You are using an example using the test package. The equals matcher actually does recognize sets, maps and iterables:

For Iterables and Maps, this will recursively match the elements. To handle cyclic structures a recursion depth limit can be provided. The default limit is 100. Sets will be compared order-independently.