Map's filterKeys and mapValues

[scabug]

In revision 21018, filterKeys and mapValues started returning map views in everything but name. This cause a few problems, however -- the lack of a distinct type does not help identifying them as returning non-strict collections, and they lack a force method to retrieve a strict collection.

I'd suggest returning a MapView, but there isn't any such collection at the moment -- view returns an IterableView instead. Perhaps the ideal would be to create a MapView, and make filterKeys and mapValues only non-strict in them.

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-4776?orig=1
Reporter: @dcsobral
Affected Versions: 2.8.0, 2.8.1, 2.9.0, 2.9.1, 2.11.1
See #7005

[scabug]

Lanny Ripple (lanny ripple) said:
Bumped into this in 2.9.2 and thought, "I'll just throw .seq onto the result". It doesn't work. Basically .mapView and .filterKeys are still lazy with no way to force. It's true Map extends GenMap and so I have only myself to blame but it was a bit of a nasty surprise.

[scabug]

Aaron Novstrup (anovstrup) said:
You can force it with .view.force, but it would be nice if the return type made it clear that it was a view.

[scabug]

@dcsobral said:
The git hash for the commit that changed it is a73bbdfed16e145da45edef41e0c2542173ac5bf.

[scabug]

Nicholas Sterling (amigonico) said:
Shouldn't we have to ask for a view if we want one?

[scabug]

Alexey Ermakov (technocoreai) said:
I second Nicolas' opinion. Normal immutable collections ({{List}}, {{Vector}} etc.) have strict mapping/filtering functions, so it's natural to assume that {{Map}}'s methods behave in the same way and use output of these in actor messages or the like, which then leads to very hard to debug issues.

[scabug]

@rklaehn said (edited on Jan 23, 2014 2:29:36 PM UTC):
Realistically, I think nothing will ever be done about this because it would break too much existing code that relies on the lazy behavior. So maybe the best way forward would be to add eager methods with a similar name?

In the new scala.collection.mutable.LongMap/AnyRefMap, @Ichoran added a method mapValuesNow . Maybe we should just add mapValuesNow and filterKeysNow to the map interface and implement it in the other collections? For immutable.HashMap, mapValuesNow would be easy to implement and very efficient.

[scabug]

Ben Challenor (bchallenor) said:
I'd like to add another vote for this. If we can't fix mapValues and filterKeys, let's add mapValuesNow and filterKeysNow as Rüdiger suggests. For now I'll be adding these as pimps in my code.

[scabug]

@Blaisorblade said:
BTW, mapValues seems somehow slated for renaming: http://www.scala-lang.org/news/roadmap-next.

Realistically, I think nothing will ever be done about this because it would break too much existing code that relies on the lazy behavior.

One could still change the return type to be more specific, like MapView (which somebody should write) or sth. like FilterMonadic — that would add a force method, and this would help for instance for #7005.

So maybe the best way forward would be to add eager methods with a similar name?

That's something which is possible in addition, and much easier because it wouldn't require implementing MapView.

It takes more time to write tests than actually making this right:

Map[K, A] ... {
def mapValuesNow(f: A => B): Map[K, B] = map { case (a, b) => (a, f(b)) }
}

Or Rüdiger, are you thinking of something more efficient?
If so, I suspect it should apply also to immutable.Map, since it is rather close to immutable.HashMap (I never understood the point of the difference, since a Map with size > 4 is a HashMap anyway, and before they follow the same structure).

[scabug]

@rklaehn said:
Yes, I was thinking of the following:

For scala.collection.immutable.HashMap it would be possible (and pretty trivial) to write a mapValuesNow that is very high performance. You can basically keep the entire Trie data structure and just transform the values of the HashMap1 and HashMapCollision1 leaf nodes. So you would e.g. not have to call hashCode or equals at all, whereas the generic mapValuesNow method calls them a lot and rebuilds the entire Trie from scratch. filterKeysNow is a bit more complex, but you could probably reuse some of the filter code of HashSet.

For the high performance mutable HashMap from Rex (AnyRefMap and LongMap), mapValuesNow is already implemented.

Regarding the immutable Map1..Map4: I don't really like them either since they complicate writing high performance tree/tree operations. Writing mapValuesNow for Map1..Map4 would be trivial, but a lot of boilerplate.

[scabug]

@retronym said:
Here's an example of how this can lead to surprising runtime results: #9499

[scabug]

@dragos said:
This ticket is nr. 7 both in terms of Votes and Watchers. Right there with "implement higher-order unification for type-constructor inference" and for-comprehension performance. While those tickets are technically very challenging, this one is more about reaching a decision and acting on it.

In an ideal world filterKeys would behave like filter and mapValues would behave like map. Unfortunately, the documentation promises that no elements are copied, and that restricts the implementation to pretty much the current one.

We could:

• change to strict behavior and break some clients. This could be done in Scala 3.0
• deprecate filterKeys and mapValues and create two other methods with explicit strict/lazy behavior, filterKeysNow and withFilterKeys à la FilterMonadic.
• add a specific return type. However, as long as that type is a subtype of Map we won't gain much, as it's unlikely people would use an explicit type to store the result of filter. This will go unnoticed in most of the cases.

The second choice sounds the most reasonable to me. Thoughts?

[scabug]

@dwijnand said (edited on Dec 18, 2015 4:27:58 PM UTC):
+1 for option 2

[scabug]

@Blaisorblade said:
I guess proposal 2 is intended to also include mapValuesNow and withMapValues? +1 to (this variant of) proposal 2.

As an advantage, if somebody volunteers, I expect one could provide, in a separate library, the same new methods for 2.11 through extension methods (at the cost of one extra import I'm afraid). By offering the same package for 2.12 (though empty), people interested in Java 6/7 could use the new methods both on 2.11 and on 2.12.

Following the existing roadmap (http://www.scala-lang.org/news/roadmap-next/), in Scala Aida we could then remove the existing mapValues and filterKeys, following usual deprecation policies.

[scabug]

@dragos said:
@Blaisorblade yes, I meant the same for mapValues