Sdk: Add union, intersection and difference on Map.

[polux]

Proposal:

Map<K, V> union(Map<K, V> other, [V combine(K key, V left, V right)])
Map<K, V> intersection(Map<K, V> other, [V combine(K key, V left, V right)])
Map<K, V> difference(Map<K, V> other)

Combine is called for keys present in both maps. It defaults to (k, v1, v2) => v1 (or v2).

Same for sets.

[polux]

_Removed Type-Defect label._
_Added Type-Enhancement label._

[floitschG]

Set-methods are tracked in issue #7400.

---

_Added Area-Library, Triaged labels._
_Changed the title to: "Add union, intersection and difference on Map."._

[DartBot]

_This comment was originally written by @seaneagan_

---

Also, maybe a mutative version of "union", possibly called "merge":

void merge(Map<K, V> other, [V combine(K key, V left, V right)])

At least for "merge", "combine" should definitely default to (k, v1, v2) => v2

so maybe "union" should too for consistency.

[DartBot]

_This comment was originally written by @seaneagan_

---

In an equality-based (as opposed to identity-based) Map, there could be different ( i.e. !identical(k1, k2) ) keys in each map, which compare equal. Which key would get passed to the "union" and "intersection" combine callback in that case ?

Maybe could get by without the combine callbacks, and then depending on which values you want to take precedence, turn the operation around. That is, the following should cover most uses:

map1.union(map2); // map2 values takes precedence
map2.union(map1); // map1 values takes precedence
map1.intersect(map2); // map2 values takes precedence
map2.intersect(map1); // map1 values takes precedence

Also, I would probably prefer if these methods returned a lazy wrapper Map (same for issue #7400) instead of a snapshot, is that the intent?

[lrhn]

I think merge with the default combine is just addAll. For a combine that picks v1, I'd just use: map2.forEach((k, v) => map1.putIfAbsent(k, ()=>v)).
I think we have the mutating versions covered with the current operations.

We don't have any current plans for putting union/intersection/difference on the Map class.

---

_Added NotPlanned label._

[escamoteur]

May I pull this issue up because I was pretty surprised that it isn't supported. Maybe in the meantime opinions have changed?

[lrhn]

Adding new features to the Map interface is not planned (or likely to happen).

Since this issue was closed, Dart has added static extension methods, so now it's possible for third-party code to add (what looks like) methods to an existing interface. You can use something like:

extension MapCombinations<K, V> on Map<K, V> {
  /// Creates a new map with the same entries as this map and [other].
  /// 
  /// If the same key occurs in both maps,
  ///  the resulting map uses the value from this map.
  Map<K, V> leftJoin(Map<K, V> other) => {...other, ...this};

  /// Creates a new map with the same entries as this map and [other].
  /// 
  /// If the same key occurs in both maps, 
  /// the resulting map uses the value from [other].
  Map<K, V> rightJoin(Map<K, V> other) => {...this, ...other};

  /// Creates a new map with the same entries as this map and [other].
  /// 
  /// If the same key occurs in both maps, the resulting map uses the value
  /// computed by [combine] on the values of that key in this map and in [other].
  Map<K, V> join(Map<K, V> other, V combine(V leftValue, V rightValue)) =>
      {...this, for (var key in other.keys) 
          if (this.containsKey(key)) key: combine(this[key], other[key]) 
              else k: other[key]};

  /// Creates a new map with the entries of this map the key of which satisfies [test].
  Map<K, V> whereKeys(bool test(K key)) =>
      {for (var key in this.keys) if (test(key)) k: this[key]};
}

(I haven't named them "union", "intersection" and "difference" because, well, they are not set operations. They are closer to the relational left/right/inner/outer-join operations, and to a filter on the keys).

As you can see, the left/right join operations are exceedingly simple with the map literal spread syntax, so I'm not sure they really deserve a helper function.

[escamoteur]

@lrhn Thanks a lot!

[escamoteur]

Although I have trouble completely understanding your code. especially as Map doesn't offer a List Interface, how can you do `{...this, ...other} and why does this behave like an addAll?

Intersection would then be:

  Map<K, V> intersect(Map<K, V> other, V combine(V leftValue, V rightValue)) =>
      {for (var key in other.keys) 
          if (this.containsKey(key)) key: combine(this[key], other[key]) 
      };

[lrhn]

The syntax {...this, ...other} creates a new map with the same entries (key/value pairs) as this and other. If the same key occurs more than once in such a map literal, the value of the last occurrence is used.

So {...this, ...other} contains all the entries for keys that are only in this or in other, and for those keys that are in both, it uses the value from other.

The intersection would indeed be what you wrote.

[escamoteur]

Wow, so {...this, ...other}is a special handling for Maps in the Dart Language? Amazing.
And why does the if (test(key)) key: this[key] work to create a new MapEntry?

[lrhn]

Dart introduced spread operators into collection (list, set and map) literals last year.

The if (test(key)) key: this[key] syntax is a conditional map entry. You could always write {key: this[key]} as a map literal. Along with spreads, we also introduced "collection-if" and "collection-for" syntax which allows you to compute conditional map entries or mutiple map entries in a single "entry expression".
So if (test(key)) key: this[key] is a "collection-if" whose body is a normal map entry.
When the surrounding map literal is evaluated, the test(key) is tested, and only if it is true will the key: this[key] entry be added to the resulting map.

The for/in loop is an example of "collection-for"