What does this code mean?

Question
1

Following is from mutable.Map.scala from standard scala collection library.

trait MapOps[K, V, +CC[X, Y] <: MapOps[X, Y, CC, _], +C <: MapOps[K, V, CC, C]]

I am a bit lost here.
What exactly this line means?

2

MapOps is a supertrait for implementation of a Map. Its methods shouldn’t return MapOps type directly, instead they should return subtypes that the user would expect. Therefore collections designers need to cope with complicated type signatures.

CC is used when returning collection of the same type but different generic parameters, e.g.:

  def updated[V1 >: V](key: K, value: V1): CC[K, V1] =
    clone().asInstanceOf[CC[K, V1]].addOne((key, value))

C is used when returning collection of the same type, including generic parameters, e.g.:

  override def clone(): C = empty ++= toIterable

Without complicated types above reusability suffers. Look for example at LinearSeq from Vavr.io:
https://github.com/vavr-io/vavr/blob/master/vavr/src/main/java/io/vavr/collection/LinearSeq.java

    @Override
    LinearSeq<T> prependAll(Iterable<? extends T> elements);

    @Override
    LinearSeq<T> remove(T element);

    @Override
    LinearSeq<T> removeFirst(Predicate<T> predicate);

    @Override
    LinearSeq<T> removeLast(Predicate<T> predicate);

    @Override
    LinearSeq<T> removeAt(int index);

    @Override
    LinearSeq<T> removeAll(T element);

    @Override
    LinearSeq<T> removeAll(Iterable<? extends T> elements);

All those overrides do nothing except narrowing return type, so that calling e.g. remove on reference of type LinearSeq results in LinearSeq instead of Seq. Without the override the method remove inherited from Seq returns Seq so calling remove on LinearSeq would result in Seq. Also notice that if Seq actually implemented some of the methods then subclasses would need to cast the return type in overrides or reimplement the whole method - depending on which would be safe to do. Overall, maintaining type safety would be a pain.

Standard Java collections avoid both complicated generic parameters and overrides, because they don’t offer methods that return collections of the same type. remove method in Vavr’s or Scala’s immutable collections return new collection, while in Java remove modifies collection in place (or throws exception if we opt for unmodifiable collections). One of the few methods in Java collections (or maybe the only one) that return new independent collection of the same type is clone method, but it fails miserably at maintaining proper return type. clone in Java collection just returns Object and you have to cast it yourself to precise type.

2 Likes
3

this is covered at https://docs.scala-lang.org/overviews/core/architecture-of-scala-213-collections.html

1 Like
4

Based on the description of Scala Collection Architecture in Chapter 25 of Programming in Scala (Oderski et al) I get the idea that the implicit parameter “canBuildFrom” is the mechanism for narrowing return types for collection operators. Is this a different mechanism? (I confess I haven’t a clue how to interpret the type parameters and their variances in the question.) Thanks.

5

mghildy’s question is about Scala 2.13.

The Scala 2.8-2.9-2.10-2.11-2.12 collections design and the 2.13 collections design are different. (2.7 and earlier had a still different design.)

The 2.13 design is described at https://docs.scala-lang.org/overviews/core/architecture-of-scala-213-collections.html

The older design is described at https://docs.scala-lang.org/overviews/core/architecture-of-scala-collections.html

A lot didn’t change, but some things did, and the role of CanBuildFrom is the biggest change. 2.12 uses CanBuildFrom pervasively. 2.13 does have something similar called BuildFrom but it plays a much smaller role. See https://www.scala-lang.org/blog/2017/05/30/tribulations-canbuildfrom.html (but note that some details in the new design may have changed since that was written).