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

[scabug]

Omer van Kloeten (omervk) said:
I'd love to see a proposal 2 implemented. I'd suggest:

• Create valueMap and keyFilter that are strict versions of the above.
• Deprecate mapValues and filterKeys, adding a deprecation note that users should use .view.mapValues and .view.filterKeys respectively.

This would keep the library standardized, supplying only strict implementations, allowing users to explicitly use non-strict versions if they see fit.

[scabug]

@Blaisorblade said:
[~omervk]: your variant would require .view to be refined to return a MapView, which somehow still doesn't exist (or it would require adding mapValues and filterKeys on IterableView[A], taking an implicit proof that A =:= (K, V) — assuming that's handled well by type inference — but that would look odd to me).

I considered suggesting such a variant of 2, but I sense current views are often considered unsatisfactory — so I'm not sure I'd propose extending them.

Finally, for such a proposal somebody should volunteer to write MapView by 2.12 — I don't want to stall this proposal.

[scabug]

@Ichoran said:
I like #2 best of all the "let's do something" options, but we don't have to deprecate anything in order to provide an eager alternative. So I'm not entirely sure when the deprecation should hit. I'd rather put something in place for 2.12 that provides an alternative, and not necessarily make it contingent upon whether we deprecate or not.

[scabug]

@rklaehn said:
I would be in favour of adding mapValuesNow, which already exists on s.c.i.AnyRefMap and s.c.i.LongMap. I like the name because it comes up next to mapValues in code completion. I guess we should then also add filterKeysNow. At the same time, deprecate mapValues and filterKeys.

Regarding the implementation: eager mapValues for s.c.i.HashMap can be implemented very efficiently, same for s.c.i.SortedMap. Eager filterKeys for HashMap is also possible to implement quickly.

[scabug]

@dragos said:
I strongly believe deprecation is essential to proposal #2. IMO the main issue that needs resolution is warning people about filterKeys being lazy. If they already know they need a strict version they're not going to be bitten by this bug (I still call it a bug, since filter and filterKeys should behave the same way, likewise for map/mapValues).

[scabug]

@Blaisorblade said:
I agree with @Ichoran that "adding strict alternative" is technically orthogonal to the deprecation. So IMHO* somebody could already start implementing that, following Rüdiger's plans. (Even if we wouldn't do #2, we'll need the same implementations).

But @dragos is right if the overall goal of the bug is not "offer both behaviors at all" but "fix latent bugs where clients use the lazy variant but shouldn't". Under that goal, deprecation is essential to the overall goal. I think that's a good goal, since Scala tries to reduce pitfalls. The only downside is that some users will have to change their code just to confirm they mean to use the lazy version.

[SethTisue]

in the new collections (which will ship in 2.13.0-M4), both mapValues and filterKeys return a scala.collection.MapView

[frozenspider]

I've just spent three frustrating hours debugging, trying to understand why the heck values are evaluated out of order, only to eventually find out this issue. Ugh.
I strongly suggest to consider making those two methods eager in 3.0

[Ichoran]

@SethTisue @julienrf @szeiger - I think we should deprecate mapValues and filterKeys so that the viewiness becomes obvious. This is a long-standing issue that burns a lot of people. Now is the ideal time to fix it. Just making it a MapView isn't enough, since the laziness is not immediately apparent; calling the methods mappedValueView and filteredKeyView would avoid error.

Alternatively, leave it alone but return a value class with a single method, view, that gives out the view. So you can create it unwittingly, but you can't use it unwittingly.

[lrytz]

Submitted #10919