Collections Architecture & Custom Collections

This content was generated with the assistance of AI and should be verified against the official documentation before being relied on in production.

The reference material consulted while preparing these pages is listed in the section bibliography.

This page is written against Scala 3.10 (3.10.0, released 2026-10-12) and every example was compiled and run with Scala 3.10.0 through Scala CLI on JDK 26 (checked on 2026-10-15). The collections library is the 2.13 library shared by all of Scala 3, so the 3.9 LTS line (3.9.0, 2026-09-03) and 3.3 LTS (3.3.8) behave the same for everything shown here (see Scala 3.9 LTS versus 3.10).

The Scala collections have hundreds of operations on dozens of classes, and a filter on a List returns a List, on a Map a Map, on a LazyList a lazy LazyList, on a TreeSet a TreeSet that is still sorted. That consistency is not magic and not duplication: it comes from a small set of template traits that implement each operation once. This page explains that design, then uses it to write a custom collection and custom operations, and finishes with the changes you meet when migrating from the 2.12 collections. It builds on the trailhead scenario, a toolkit that plans hikes on a network of mountain trails, and assumes the tour in Collections Overview and Collection Operations; the cost of each class is on Collection Performance & Equality.

The problem the design solves

If every collection class implemented every operation, the library would be an enormous amount of nearly identical code that could drift apart. The principal design objective is to define each operation in as few places as possible, and the template traits have to cope with these differences between collections:

  • some operations return the same concrete collection type (filter on a List[Int] is a List[Int]);

  • some return the same collection type with another element type (map on a List[Int] can produce a List[String]);

  • some collections have one element type (List[A]), others two (Map[K, V]);

  • some operations return a different collection depending on the element type: map on a Map returns a Map if the function returns a pair, and an Iterable otherwise;

  • some transformations need an extra implicit parameter (map on a SortedSet needs an Ordering);

  • some collections are strict (List) and others non-strict (View, LazyList), and a default implementation must preserve that.

Source: Scala 2.13 Collections: Architecture

The next program shows each of these in the static types of the results.

//> using scala 3.10.0
import scala.collection.immutable.{SortedSet, TreeMap, ListMap}

@main def run(): Unit =
  val lengths = List(12.5, 7.0, 3.2)
  val names = Map("Refugio" -> 12.5, "Pico" -> 7.0)

  // same concrete type
  val a: List[Double] = lengths.filter(_ > 5)
  // same type constructor, new element type
  val b: List[String] = lengths.map(_.toString)
  // Map.map: result depends on whether the function returns a pair
  val c: Map[String, Int] = names.map((k, v) => k -> v.toInt)
  val d: Iterable[String] = names.map((k, v) => s"$k $v")
  // SortedSet.map needs an Ordering for the new element type
  val e: SortedSet[Int] = SortedSet(3.2, 7.0).map(_.toInt)
  // TreeMap.map: sorted map stays sorted if keys have an Ordering
  val f: TreeMap[Int, String] = TreeMap("b" -> 1, "a" -> 2).map((k, v) => v -> k)
  println(List(a, b, c, d, e, f).mkString("\n"))
List(12.5, 7.0)
List(12.5, 7.0, 3.2)
Map(Refugio -> 12, Pico -> 7)
List(Refugio 12.5, Pico 7.0)
TreeSet(3, 7)
TreeMap(1 -> b, 2 -> a)

Source: Scala 2.13 Collections: Four branches of template traits

The declared types are checked by the compiler: filter keeps List[Double], map changes the element type but keeps List, names.map((k, v) => k -> v.toInt) keeps Map, and the same call returning a String falls back to a plain Iterable (a List at run time). SortedSet.map keeps the set sorted only because an Ordering[Int] exists. If it does not, the compiler rejects the call.

//> using scala 3.10.0
import scala.collection.immutable.SortedSet

class Waypoint(val name: String)

@main def run(): Unit =
  val s = SortedSet(1, 2, 3)
  val t = s.map(i => Waypoint(i.toString))
  println(t)
-- [E172] Type Error: ./b2.scala:8:42
8 |  val t = s.map(i => Waypoint(i.toString))
  |                                          ^
  |No implicit Ordering[Waypoint] found to build a SortedSet[Waypoint]. You may want to upcast to a Set[Int @uncheckedVariance] first by calling `unsorted`..
  |I found:
  |    scala.math.Ordering.comparatorToOrdering[Waypoint](
  |      /* missing */summon[java.util.Comparator[Waypoint]])

Source: Scala 2.13 Collections: Architecture

The message comes from the SortedSetOps overload and suggests the fix: go through unsorted to get a plain Set, which needs no ordering.

Template traits: IterableOps

Operations are not defined in the classes (List, Vector) but in template traits, whose names end in Ops. The one for Iterable abstracts over three things. A simplified view of its header and of two operations:

trait IterableOps[+A, +CC[_], +C]:
  def filter(p: A => Boolean): C = ...
  def map[B](f: A => B): CC[B] = ...

Source: Scala 2.13 Collections: Abstracting over collection types

  • A is the element type;

  • CC is the type constructor of the collection, used when the element type changes (map, flatMap, collect, zip…​);

  • C is the collection type, used when the element type is kept (filter, take, drop, tail, init…​).

A leaf collection instantiates the parameters with itself. For List they are A, List and List[A]:

trait List[+A] extends Iterable[A], IterableOps[A, List, List[A]]

Source: Scala 2.13 Collections: Abstracting over collection types

Abstracting over CC is a use of higher-kinded types (CC takes one type argument), and the covariance of A is the subject of Variance. The operations in these traits are the methods listed on Collection Operations.

Four branches of template traits

Map[K, V] has two type parameters, so its constructor cannot be passed as the one-argument CC of IterableOps. A second family of template traits exists for maps, and two more cover the sorted collections, which need an Ordering that IterableOps knows nothing about.

Kind Not sorted Sorted

CC takes one type parameter

IterableOps (with SeqOps, SetOps)

SortedSetOps

CC takes two type parameters

MapOps

SortedMapOps

Source: Scala 2.13 Collections: Four branches of template traits

classDiagram direction TB class IterableOps { <<trait>> one type parameter CC } class SeqOps { <<trait>> } class SetOps { <<trait>> } class MapOps { <<trait>> two type parameters CC } class SortedSetOps { <<trait>> needs Ordering } class SortedMapOps { <<trait>> needs Ordering on keys } class StrictOptimizedIterableOps { <<trait>> builder based } IterableOps <|-- SeqOps IterableOps <|-- SetOps IterableOps <|-- MapOps IterableOps <|-- StrictOptimizedIterableOps SetOps <|-- SortedSetOps MapOps <|-- SortedMapOps SeqOps <|.. List SeqOps <|.. Vector SetOps <|.. HashSet MapOps <|.. HashMap SortedSetOps <|.. TreeSet SortedMapOps <|.. TreeMap

MapOps extends IterableOps[(K, V), Iterable, C], so a Map inherits two overloads of map: the one from MapOps, which returns CC[K2, V2] (a Map), and the one from IterableOps, which returns Iterable[B]. When the function returns a pair both apply and the more specific MapOps one wins, so you get a Map; otherwise only the IterableOps one applies. This is the "same-result-type" principle: wherever possible, a transformation yields the same kind of collection. SortedSetOps and SortedMapOps add overloads that take a using Ordering, so that mapping a SortedSet to a type with an ordering gives a SortedSet again.

Scala 2 syntax differs only on the surface (implicit instead of using, braces instead of indentation); the traits are the same.

Strict and non-strict collections

Some collections evaluate their elements eagerly (List, Set, Vector) and others delay (View, LazyList). The default implementation of a transformation therefore has to preserve the strictness of the class it is inherited by. The library does this by implementing the operations on top of a non-strict View. A simplified filter and map:

trait IterableOps[+A, +CC[_], +C]:
  def iterableFactory: IterableFactory[CC]
  protected def fromSpecific(coll: IterableOnce[A]): C
  def filter(p: A => Boolean): C = fromSpecific(View.Filter(this, p))
  def map[B](f: A => B): CC[B] = iterableFactory.from(View.Map(this, f))

Source: Scala 2.13 Collections: Operations implementation

View.Filter(this, p) describes the filter without running it. fromSpecific turns that description into a concrete C: a List decides to traverse it right away, a LazyList wraps it. iterableFactory.from does the same for a different element type. View itself is an Iterable with a single abstract method, iterator, so its elements are only evaluated when the iterator is traversed.

//> using scala 3.10.0
import scala.collection.View

@main def run(): Unit =
  var evaluated = 0
  val xs = List(1, 2, 3, 4)
  val lazyView = xs.view.map { x => evaluated += 1; x * 2 }
  println(s"after view.map: evaluated = $evaluated")
  val strict = xs.map { x => evaluated += 1; x * 2 }
  println(s"after List.map: evaluated = $evaluated")
  evaluated = 0
  val ll = LazyList.from(1).map { x => evaluated += 1; x * 2 }
  println(s"LazyList.map before use: evaluated = $evaluated")
  println(ll.take(3).toList)
  println(s"after taking 3: evaluated = $evaluated")

  // static types of the same operation on strict and non-strict collections
  val a: List[Int] = xs.filter(_ > 1)
  val b: View[Int] = xs.view.filter(_ > 1)
  val c: LazyList[Int] = LazyList(1, 2, 3).filter(_ > 1)
  println(s"$a / ${b.toList} / ${c.toList}")
  // partition on a View: each half is a view that traverses the source again when it is used
  var traversals = 0
  val src = View.fromIteratorProvider { () => traversals += 1; Iterator(1, 2, 3, 4) }
  val (evens, odds) = src.partition(_ % 2 == 0)
  println(s"${evens.toList} ${odds.toList} traversals = $traversals")
after view.map: evaluated = 0
after List.map: evaluated = 4
LazyList.map before use: evaluated = 0
List(2, 4, 6)
after taking 3: evaluated = 3
List(2, 3, 4) / List(2, 3, 4) / List(2, 3)
List(2, 4) List(1, 3) traversals = 2

Source: Scala 2.13 Collections: Architecture

Neither view.map nor LazyList.map runs the function until elements are demanded (and LazyList only evaluates the first three elements, not the infinite tail), while List.map runs it immediately. The last line shows the cost of the view-based default: a partition on a view traverses its source once per half, which is why strict collections override partition.

When strictness is preferable: Builder and StrictOptimized

Some operations are more efficient strict (partition would have to traverse a non-strict source twice) and some cannot be non-strict at all (groupBy has to evaluate the elements). For those, the library offers a second implementation style based on a Builder instead of a View:

package scala.collection.mutable
trait Builder[-A, +C]:
  def addOne(elem: A): this.type
  def result(): C

Source: Scala 2.13 Collections: When a strict evaluation is preferable (or unavoidable)

You add an element with b.addOne(x) (or b += x) and take the collection with b.result(). The template traits expose it through newSpecificBuilder (same element type, result type C) and iterableFactory.newBuilder (any element type, result CC[B]). Traits whose names start with StrictOptimized (StrictOptimizedIterableOps, StrictOptimizedSeqOps, StrictOptimizedMapOps, StrictOptimizedSetOps, StrictOptimizedSortedSetOps and StrictOptimizedSortedMapOps) override the transformation operations to use builders. The guideline: if a collection is strict, mix the matching StrictOptimized trait in; if an operation need not be strict, leave it non-strict, or view-like behaviour will surprise users of lazy collections.

Factories: IterableFactory, MapFactory, Factory and BuildFrom

Because there are four branches of operations, there are four branches of factories. IterableFactory[CC] builds CC[A] from any IterableOnce[A] (from) and offers empty, newBuilder and apply; MapFactory[CC] does the same for two type parameters; and SortedIterableFactory, SortedMapFactory and EvidenceIterableFactory add the evidence (an Ordering, a ClassTag). The companion objects of the standard collections are those factories, which is why List.from(xs), Vector.from(xs) and Map.from(pairs) all exist.

The factories that the user of a library function sees are two small traits, used in using clauses:

  • Factory[-A, +C] says "a way to build a collection C of elements A`" without naming `C. It is the argument of to (xs.to(Vector) works because a collection companion is implicitly converted to a Factory) and of Iterator.to.

  • BuildFrom[-From, -A, +C] says "given an existing collection of type From, a way to build a C from elements A`". Because it looks at the source collection, it can preserve its dynamic characteristics (the `Ordering of a SortedSet, the element type of an Array, the kind of String). Future.sequence, Future.traverse and the operations written in Transforming any collection use it.

trait Factory[-A, +C]:
  def fromSpecific(it: IterableOnce[A]): C
  def newBuilder: Builder[A, C]

trait BuildFrom[-From, -A, +C]:
  def fromSpecific(from: From)(it: IterableOnce[A]): C
  def newBuilder(from: From): Builder[A, C]

Source: Scala API: Factory and Scala API: BuildFrom

Prefer fromSpecific over newBuilder when you can: a builder always evaluates, while fromSpecific can stay lazy for a lazy collection type.

Writing a custom collection

To make a new collection profit from every predefined operation with the right result types, you choose a base type, implement a few abstract members, and (if you want the operations to return your type) mix in the Ops template and supply a factory. This section builds three collections for the trailhead scenario: an Iterable (the last few waypoints a hiker has passed), a Seq (a sequence of waypoints with a domain method) and a Map (an index of trail names with a prefix query).

A capped collection: Iterable

The first collection keeps at most capacity waypoints and drops the oldest ones. The first task is the supertype. A Seq is tempting, but a Seq promises (xs ++ ys).size == xs.size + ys.size, which a capped collection cannot keep, so the right base is immutable.Iterable. A first version only implements iterator (required by Iterable) and the new operation appended:

//> using scala 3.10.0
package trailhead

import scala.collection.immutable

/** The last `capacity` waypoints a hiker has passed, oldest dropped first. */
final class Recent1[A] private (val capacity: Int, items: Vector[A]) extends immutable.Iterable[A]:
  def this(capacity: Int) = this(capacity, Vector.empty)
  def appended[B >: A](elem: B): Recent1[B] =
    val grown = items :+ elem
    Recent1[B](capacity, if grown.size > capacity then grown.drop(1) else grown)
  def :+[B >: A](elem: B): Recent1[B] = appended(elem)
  def iterator: Iterator[A] = items.iterator
  override def className = "Recent1"

@main def run(): Unit =
  val r = Recent1[String](3) :+ "Refugio" :+ "Collado" :+ "Pico" :+ "Cumbre"
  println(r)
  println(r.size)
  println(r.map(_.length))
  val shortest = r.take(2)
  println(shortest)
  val t: immutable.Iterable[String] = r.take(2)
  println(t.getClass.getName)
Recent1(Collado, Pico, Cumbre)
3
List(7, 4, 6)
List(Collado, Pico)
scala.collection.immutable.$colon$colon

Source: Scala 2.13 Collections: Custom Collections

The collection works, and map gives a List because immutable.Iterable implements map with the default List factory. The interesting line is take(2): it returns a plain List, not a Recent1, because Iterable returns an Iterable, whose default is a List. Overriding take alone would not be enough. There are over fifty methods that return a collection (drop, filter, init…​), and the templates exist so you do not override any of them.

The fix is the protocol described above. The final version below:

  1. extends IterableOps[A, Recent, Recent[A]], which fixes the result types (Recent[A] for take, filter…​, Recent[B] for map);

  2. overrides iterableFactory to return a factory that builds Recent (the factory also carries the capacity);

  3. mixes in IterableFactoryDefaults, which implements fromSpecific, newSpecificBuilder and empty by forwarding to iterableFactory, so you do not write them;

  4. mixes in StrictOptimizedIterableOps, because the collection is strict;

  5. overrides knownSize (the size is always known) for performance.

//> using scala 3.10.0
package trailhead

import scala.collection.{IterableFactory, IterableFactoryDefaults, IterableOnce, IterableOps, StrictOptimizedIterableOps, immutable, mutable}

/** The last `capacity` waypoints a hiker has passed, oldest dropped first. */
final class Recent[A] private (val capacity: Int, items: Vector[A])
    extends immutable.Iterable[A],
      IterableOps[A, Recent, Recent[A]],
      IterableFactoryDefaults[A, Recent],
      StrictOptimizedIterableOps[A, Recent, Recent[A]]:

  def this(capacity: Int) = this(capacity, Vector.empty)

  def appended[B >: A](elem: B): Recent[B] =
    val grown = items :+ elem
    new Recent[B](capacity, if grown.size > capacity then grown.drop(1) else grown)

  def :+[B >: A](elem: B): Recent[B] = appended(elem)
  def apply(i: Int): A = items(i)
  def iterator: Iterator[A] = items.iterator
  override def knownSize: Int = items.size
  override def className = "Recent"
  override val iterableFactory: IterableFactory[Recent] = RecentFactory(capacity)

class RecentFactory(capacity: Int) extends IterableFactory[Recent]:
  def empty[A]: Recent[A] = new Recent[A](capacity)
  def from[A](source: IterableOnce[A]): Recent[A] =
    source match
      case r: Recent[?] if r.capacity == capacity => r.asInstanceOf[Recent[A]]
      case _ => (newBuilder[A] ++= source).result()
  def newBuilder[A]: mutable.Builder[A, Recent[A]] =
    new mutable.ImmutableBuilder[A, Recent[A]](empty):
      def addOne(elem: A): this.type =
        elems = elems :+ elem
        this

object Recent extends RecentFactory(capacity = 3)

@main def run(): Unit =
  val r = Recent("Refugio", "Collado", "Pico", "Cumbre")
  println(r)
  val taken: Recent[String] = r.take(2)
  println(taken)
  val lengths: Recent[Int] = r.map(_.length)
  println(lengths)
  println(r.filter(_.length > 4))
  println(r.partition(_.startsWith("C")))
  println(List(1, 2, 3, 4, 5).to(Recent))
  println(r.zip(r.map(_.length)))
  println(r.groupBy(_.length).map((len, rs) => len -> rs))
  println(r.drop(1).headOption)
Recent(Collado, Pico, Cumbre)
Recent(Collado, Pico)
Recent(7, 4, 6)
Recent(Collado, Cumbre)
(Recent(Collado, Cumbre),Recent(Pico))
Recent(3, 4, 5)
Recent((Collado,7), (Pico,4), (Cumbre,6))
HashMap(6 -> Recent(Cumbre), 7 -> Recent(Collado), 4 -> Recent(Pico))
Some(Pico)

Source: Scala 2.13 Collections: Custom Collections

Every transformation now returns the right type: take, filter and partition return Recent, map returns Recent[Int], zip returns Recent of pairs, and to(Recent) converts another collection (List(1, 2, 3, 4, 5).to(Recent) keeps the last three). groupBy returns a Map of Recent, since a map is the only reasonable result there. Three details of the code deserve attention:

  • the code uses new Recent[B](...) because the companion object Recent extends the factory and so defines its own apply, which would capture Recent[B](...) as a call to the varargs factory and not the constructor (the compiler reports a type mismatch);

  • RecentFactory is a class with a capacity parameter, and object Recent extends RecentFactory(capacity = 3) is a ready-made default instance; it is the factory that decides the capacity of the results;

  • from returns the source unchanged when it is already a Recent of the same capacity, avoiding a copy.

A sequence: Seq and IndexedSeq

A sequence needs a different set of traits: SeqOps branch (here through IndexedSeqOps), SeqFactory. The following Waypoints class is a sequence backed by a Vector, with a domain method (returnTrip) and the same result-type behaviour as Vector.

//> using scala 3.10.0
package trailhead

import scala.collection.{SeqFactory, StrictOptimizedSeqFactory, StrictOptimizedSeqOps, IterableFactoryDefaults, IterableOnce, immutable, mutable}

/** An immutable sequence of waypoints backed by a Vector, with a domain method. */
final class Waypoints[+A] private (underlying: Vector[A])
    extends immutable.AbstractSeq[A],
      immutable.IndexedSeq[A],
      immutable.IndexedSeqOps[A, Waypoints, Waypoints[A]],
      StrictOptimizedSeqOps[A, Waypoints, Waypoints[A]],
      IterableFactoryDefaults[A, Waypoints]:

  override def iterableFactory: SeqFactory[Waypoints] = Waypoints
  def length: Int = underlying.length
  def apply(i: Int): A = underlying(i)
  override def className = "Waypoints"

  /** A domain method: the same path walked back. */
  def returnTrip: Waypoints[A] = new Waypoints(underlying.reverse)

object Waypoints extends StrictOptimizedSeqFactory[Waypoints]:
  def empty[A]: Waypoints[A] = new Waypoints(Vector.empty)
  def from[A](source: IterableOnce[A]): Waypoints[A] =
    source match
      case w: Waypoints[A] => w
      case other => new Waypoints(Vector.from(other))
  def newBuilder[A]: mutable.Builder[A, Waypoints[A]] =
    Vector.newBuilder[A].mapResult(v => new Waypoints(v))

@main def run(): Unit =
  val w = Waypoints("Refugio", "Collado", "Pico")
  println(w)
  val sorted: Waypoints[String] = w.sorted
  println(sorted)
  val mapped: Waypoints[Int] = w.map(_.length)
  println(mapped)
  println(w.reverse.returnTrip)
  println(w.tail.headOption)
  println(w ++ List("Cumbre"))
  println(w :+ "Cumbre")
  println(w == List("Refugio", "Collado", "Pico"))
  println(w.patch(1, List("Lago"), 1))
  println(w.zipWithIndex)
  println(w.groupBy(_.length))
  println(w.to(Waypoints) eq w)
Waypoints(Refugio, Collado, Pico)
Waypoints(Collado, Pico, Refugio)
Waypoints(7, 7, 4)
Waypoints(Refugio, Collado, Pico)
Some(Collado)
Waypoints(Refugio, Collado, Pico, Cumbre)
Waypoints(Refugio, Collado, Pico, Cumbre)
true
Waypoints(Refugio, Lago, Pico)
Waypoints((Refugio,0), (Collado,1), (Pico,2))
HashMap(7 -> Waypoints(Refugio, Collado), 4 -> Waypoints(Pico))
true

Source: Scala 2.13 Collections: Custom Collections

sorted, map, ++, :+, patch and zipWithIndex return Waypoints, == with a List is true, because equality is defined for the sequence category as a whole (see Collection Performance & Equality), and groupBy returns a Map of Waypoints. The class is covariant (+A), like the standard immutable collections. The pieces are:

  • the supertypes: immutable.AbstractSeq (the abstract class the standard sequences extend, which avoids interface dispatch), immutable.IndexedSeq and the template IndexedSeqOps[A, Waypoints, Waypoints[A]];

  • iterableFactory of type SeqFactory, implemented by the companion Waypoints, which extends StrictOptimizedSeqFactory, the sequence-branch version of IterableFactory;

  • the abstract members of a sequence, length and apply, and IterableFactoryDefaults and StrictOptimizedSeqOps as before.

A map: the third branch

A map needs MapOps. When the key type is fixed (here String) and the collection is not generic in two parameters, the usual trick is to instantiate CC with the standard immutable.Map, and C with your own type, so that operations that keep keys and values return your type and operations that change them fall back to a standard Map. The next class indexes trails by name and adds a prefix query.

//> using scala 3.10.0
package trailhead

import scala.collection.{IterableOnce, immutable, mutable}
import scala.collection.immutable.{TreeMap, MapOps}

/** A trail-name index: an immutable map with String keys and a prefix query. */
final class TrailIndex[+V] private (underlying: TreeMap[String, V])
    extends immutable.AbstractMap[String, V],
      MapOps[String, V, immutable.Map, TrailIndex[V]],
      collection.StrictOptimizedIterableOps[(String, V), immutable.Iterable, TrailIndex[V]]:

  // Operations that keep the key and value types return a TrailIndex
  override protected def fromSpecific(coll: IterableOnce[(String, V @scala.annotation.unchecked.uncheckedVariance)]): TrailIndex[V] =
    TrailIndex.from(coll)
  override protected def newSpecificBuilder: mutable.Builder[(String, V @scala.annotation.unchecked.uncheckedVariance), TrailIndex[V]] =
    TrailIndex.newBuilder[V]
  override def empty: TrailIndex[V] = TrailIndex.empty[V]

  def get(key: String): Option[V] = underlying.get(key)
  def iterator: Iterator[(String, V)] = underlying.iterator
  def removed(key: String): TrailIndex[V] = new TrailIndex(underlying.removed(key))
  def updated[V1 >: V](key: String, value: V1): TrailIndex[V1] = new TrailIndex(underlying.updated(key, value))

  /** All entries whose key starts with the prefix. */
  def withPrefix(prefix: String): TrailIndex[V] =
    new TrailIndex(underlying.rangeFrom(prefix).takeWhile((k, _) => k.startsWith(prefix)))

  override def className = "TrailIndex"

object TrailIndex:
  def empty[V]: TrailIndex[V] = new TrailIndex(TreeMap.empty[String, V])
  def from[V](source: IterableOnce[(String, V)]): TrailIndex[V] =
    source match
      case ti: TrailIndex[V @unchecked] => ti
      case other => (newBuilder[V] ++= other).result()
  def apply[V](entries: (String, V)*): TrailIndex[V] = from(entries)
  def newBuilder[V]: mutable.Builder[(String, V), TrailIndex[V]] =
    TreeMap.newBuilder[String, V].mapResult(m => new TrailIndex(m))

@main def run(): Unit =
  val idx = TrailIndex("camino-norte" -> 12.5, "camino-sur" -> 8.0, "collado" -> 3.2, "pico" -> 7.0)
  println(idx.withPrefix("cam"))
  val long: TrailIndex[Double] = idx.filter((_, km) => km > 7.5)
  println(long)
  val rounded = idx.map((k, km) => k -> km.toInt)
  println(rounded)
  val lengths = idx.map((k, km) => km)
  println(lengths)
  println(idx.removed("pico").keys)
  println(idx.updated("lago", 1.1).get("lago"))
TrailIndex(camino-norte -> 12.5, camino-sur -> 8.0)
TrailIndex(camino-norte -> 12.5, camino-sur -> 8.0)
Map(camino-norte -> 12, camino-sur -> 8, collado -> 3, pico -> 7)
List(12.5, 8.0, 3.2, 7.0)
Set(camino-norte, camino-sur, collado)
Some(1.1)

Source: Scala 2.13 Collections: Custom Collections

filter and withPrefix return TrailIndex, removed and updated too, and map returns a plain Map when the function returns a pair (the key type may change) and an Iterable otherwise. The code needs uncheckedVariance on the element type of fromSpecific and newSpecificBuilder, because the protected members of a covariant class use V in an invariant position; see Variance for why that annotation is safe here. For a fully generic map, implement MapOps[K, V, CC, C] with a MapFactory[CC] in the same way as the sequence.

Writing operations on any collection

Custom operations are different from custom collections. You want to add sumBy or intersperse to every collection, without writing a new collection. The three cases are consuming, producing and transforming. They are all extension methods and using clauses; the contextual-abstraction background is not repeated here.

Consuming any collection

To consume a collection, take an IterableOnce[A] if you traverse once, or an Iterable[A] if more than once. The extension below sums a function applied to the elements, and works on collections, iterators and, in Scala 3, also on String and Array.

//> using scala 3.10.0
package trailhead

case class Trail(name: String, km: Double, ascent: Int)

extension [A](coll: IterableOnce[A])
  def sumBy[B: Numeric](f: A => B): B =
    val it = coll.iterator
    val num = summon[Numeric[B]]
    var result = num.zero
    while it.hasNext do result = num.plus(result, f(it.next()))
    result

@main def run(): Unit =
  val trails = Vector(Trail("Ridge", 12.5, 900), Trail("Lake", 6.0, 300))
  println(trails.sumBy(_.km))
  println(Set(1, 2, 3).sumBy(_ * 2))
  println(Iterator("ab", "c").sumBy(_.length))
  println("hello".sumBy(_.toInt))
  println(Array("ab", "c").sumBy(_.length))
  println(List(1, 2).view.sumBy(_ + 1))
18.5
12
3
532
3
5

Source: Scala 2.13 Collections: Custom Collection Operations

The official guide explains that such an extension does not work on String and Array, because they are not part of the hierarchy and Scala 2 can apply only one implicit conversion. On Scala 3 the example above runs on both, because the extension receiver is converted to an IterableOnce by the Predef conversions ("hello" to a WrappedString, an Array[String] to an ArraySeq). What conversion does not give you is the original type of the receiver, which a transformation needs to return, and the complete list of collection-like types. For that the library has IsIterable[Repr] (and IsSeq and IsMap), with instances for every type that can be viewed as an IterableOps, including String, Array and the views.

//> using scala 3.10.0
package trailhead

import scala.collection.generic.IsIterable

extension [Repr](repr: Repr)(using iter: IsIterable[Repr])
  def sumBy[B: Numeric](f: iter.A => B): B =
    val it = iter(repr).iterator
    val num = summon[Numeric[B]]
    var result = num.zero
    while it.hasNext do result = num.plus(result, f(it.next()))
    result

@main def run(): Unit =
  println(Vector(1, 2, 3).sumBy(_ * 10))
  println("hello".sumBy(_.toInt))
  println(Array("ab", "c").sumBy(_.length))
  println(Map("a" -> 1, "b" -> 2).sumBy((_, v) => v))
  println(List(1, 2).view.sumBy(_ + 1))
60
532
3
3
5

Source: Scala 2.13 Collections: Custom Collection Operations

The shape is extension [Repr](repr: Repr)(using iter: IsIterable[Repr]), with iter.A as the element type and iter(repr) as the conversion to IterableOps. Use IsSeq when the operation only makes sense on sequences (it also works for SeqView, which does not extend Seq), and IsMap for maps and MapView.

Producing any collection

When a library function must produce a collection and the user should pick which one, take a Factory in a using clause. The functions below never name a concrete collection; the result type chooses it.

//> using scala 3.10.0
package trailhead

import scala.collection.Factory
import scala.collection.immutable.TreeSet
import scala.util.Random

case class Trail(name: String, km: Double)

// The caller picks the result collection; the library never names a concrete type
def namesOf[C](trails: Seq[Trail])(using factory: Factory[String, C]): C =
  factory.fromSpecific(trails.iterator.map(_.name))

// A generator of values that can build any collection of them
def randomKms[CC[_]](n: Int, seed: Long)(using factory: Factory[Double, CC[Double]]): CC[Double] =
  val rng = Random(seed)
  factory.fromSpecific(Iterator.fill(n)(math.round(rng.nextDouble() * 200) / 10.0))

@main def run(): Unit =
  val trails = Seq(Trail("Pico", 7.0), Trail("Lago", 4.5), Trail("Pico", 9.1))
  val asList: List[String] = namesOf(trails)
  val asSet: Set[String] = namesOf(trails)
  val asSorted: TreeSet[String] = namesOf(trails)
  val asArray: Array[String] = namesOf(trails)
  println(s"$asList $asSet $asSorted ${asArray.mkString(",")}")
  val kmList: List[Double] = randomKms(4, 7L)
  val kmSet: Set[Double] = randomKms(4, 7L)
  val kmLazy: LazyList[Double] = randomKms(4, 7L)
  println(s"$kmList $kmSet ${kmLazy.toList}")
List(Pico, Lago, Pico) Set(Pico, Lago) TreeSet(Lago, Pico) Pico,Lago,Pico
List(14.6, 15.0, 7.0, 17.9) Set(14.6, 15.0, 7.0, 17.9) List(14.6, 15.0, 7.0, 17.9)

Source: Scala 2.13 Collections: Custom Collection Operations

The expected type picks List, Set, a sorted TreeSet and an Array for namesOf, and for randomKms the CC[_] parameter of the signature is inferred from the declared type. The function passes fromSpecific an Iterator, so a lazy target such as LazyList is built lazily and a strict one evaluates it; this is the recommended way to build the result, and it is the reason the guide advises fromSpecific over a builder. An Array needs a ClassTag for the factory to exist, which the compiler finds because the element type is known.

Transforming any collection

Transforming is consuming plus producing: use IsSeq to consume, and BuildFrom to build a result of the same kind as the input. The operation below puts a separator between the elements of any sequence and returns the same kind of collection, String and Array included.

//> using scala 3.10.0
package trailhead

import scala.collection.BuildFrom
import scala.collection.generic.IsSeq

extension [Repr](repr: Repr)(using seq: IsSeq[Repr])
  def intersperse[B >: seq.A, That](sep: B)(using bf: BuildFrom[Repr, B, That]): That =
    val elems = seq(repr).iterator
    val withSeparators = elems.zipWithIndex.flatMap((x, i) => if i == 0 then Iterator(x) else Iterator(sep, x))
    bf.fromSpecific(repr)(withSeparators.to(Iterable))

@main def run(): Unit =
  val a: Vector[Int] = Vector(1, 2, 3).intersperse(0)
  val b: List[String] = List("Refugio", "Pico").intersperse(">")
  val c: String = "abc".intersperse('-')
  val d: Array[Int] = Array(1, 2, 3).intersperse(0)
  val e: LazyList[Int] = LazyList(1, 2).intersperse(9)
  println(s"$a $b $c ${d.mkString("[", ",", "]")} ${e.toList}")
  println(Seq(1, 2, 3).view.intersperse(0).toList)
Vector(1, 0, 2, 0, 3) List(Refugio, >, Pico) a-b-c [1,0,2,0,3] List(1, 9, 2)
List(1, 0, 2, 0, 3)

Source: Scala 2.13 Collections: Custom Collection Operations

Vector gives Vector, List gives List, a String gives a String, an Array[Int] an Array[Int], a LazyList a LazyList, and the separator type B may be a supertype of the element type. BuildFrom[Repr, B, That] is what makes the That result type follow from Repr. In 2.12 the same job was done by CanBuildFrom, which every transformation took as an implicit parameter; see the next section.

Migrating from the 2.12 collections

The 2.13 library is a redesign, and Scala 3 uses it unchanged, so code written for 2.12 (or Scala 2.11 and earlier) meets these changes. The main ones:

2.12 2.13 and Scala 3

scala.Seq, scala.IndexedSeq, and varargs types were collection.Seq and collection.IndexedSeq

They are aliases of immutable.Seq and immutable.IndexedSeq; varargs parameters are immutable sequences.

Transformations take an implicit CanBuildFrom[Repr, B, That] and return That

No CanBuildFrom parameter: map[B](f): CC[B] as shown above. BuildFrom (and Factory) are used by libraries, not by every method.

Traversable, TraversableOnce

Only Iterable and IterableOnce; the old Traversable is a deprecated alias (see the warnings below).

xs.to[List]

xs.to(List)

collection.breakOut

Removed. Use .view (or .iterator) plus .to(Collection).

Stream

LazyList; its head is also lazy.

mapValues, filterKeys return a Map

They return a MapView; call .toMap if you need a Map.

Views extend their collection (SeqView is a Seq)

Views no longer extend their collection types, and work reliably. IsSeq exists because of that.

Immutable HashSet and HashMap as hash tries

Reimplemented with the CHAMP encoding.

MutableList, ArrayStack, immutable Stack, ResizableArray

Removed; use ArrayBuffer/ListBuffer, ArrayDeque, List and so on.

Parallel collections in the standard library

A separate module (scala-parallel-collections).

xs1.sameElements(xs2) on any Iterable

Only on sequences and iterators: xs1.iterator.sameElements(xs2).

Source: Scala 2.13 Collections: Migration Guide

On Scala 3 many of these produce real messages. The first program uses two removed forms (the Scala 2 to[Set] syntax and breakOut):

//> using scala 3.10.0
@main def run(): Unit =
  val xs = List(3, 1, 2)
  val a = xs.to[Set]
  val b: List[Int] = xs.map(_ + 1)(collection.breakOut)
-- [E056] Syntax Error: ./m1.scala:4:10
4 |  val a = xs.to[Set]
  |          ^
  |          Missing type parameter for Set
-- [E008] Not Found Error: ./m1.scala:5:46
5 |  val b: List[Int] = xs.map(_ + 1)(collection.breakOut)
  |                                   ^^^^^^^^^^^^^^^^^^^
  |                              value breakOut is not a member of collection
2 errors found

Source: Scala 2.13 Collections: Migration Guide

The following uses the deprecated spellings that still compile, with -deprecation to show each message:

//> using scala 3.10.0
//> using option -deprecation
@main def run(): Unit =
  val s = Stream(1, 2, 3)
  val t: Traversable[Int] = List(1, 2)
  val m = Map("a" -> 1).mapValues(_ + 1)
  val it = List(1, 2).toIterator
  val v = List(1, 2).toStream
  val l = List(1, 2).iterator.toTraversable
  val s2 = List(1).toIterable
-- Deprecation Warning: ./m4.scala:4:10
4 |  val s = Stream(1, 2, 3)
  |          ^^^^^^
  |value Stream in package scala is deprecated since 2.13.0: Use LazyList instead of Stream
-- Deprecation Warning: ./m4.scala:5:9
5 |  val t: Traversable[Int] = List(1, 2)
  |         ^^^^^^^^^^^
  |type Traversable in package scala is deprecated since 2.13.0: Use Iterable instead of Traversable
-- Deprecation Warning: ./m4.scala:6:24
6 |  val m = Map("a" -> 1).mapValues(_ + 1)
  |          ^^^^^^^^^^^^^^^^^^^^^^^
  |method mapValues in trait MapOps is deprecated since 2.13.0: Use .view.mapValues(f). A future version will include a strict version of this method (for now, .view.mapValues(f).toMap).
-- Deprecation Warning: ./m4.scala:7:22
7 |  val it = List(1, 2).toIterator
  |           ^^^^^^^^^^^^^^^^^^^^^
  |method toIterator in trait IterableOnceOps is deprecated since 2.13.0: Use .iterator instead of .toIterator
-- Deprecation Warning: ./m4.scala:8:21
8 |  val v = List(1, 2).toStream
  |          ^^^^^^^^^^^^^^^^^^^
  |method toStream in trait IterableOnceOps is deprecated since 2.13.0: Use .to(LazyList) instead of .toStream
-- Deprecation Warning: ./m4.scala:9:30
9 |  val l = List(1, 2).iterator.toTraversable
  |          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |method toTraversable in class IterableOnceExtensionMethods is deprecated since 2.13.0: Use .iterator.to(Iterable) instead
-- Deprecation Warning: ./m4.scala:10:19
10 |  val s2 = List(1).toIterable
   |           ^^^^^^^^^^^^^^^^^^
   |method toIterable in trait Iterable is deprecated since 2.13.7: toIterable is internal and will be made protected; its name is similar to `toList` or `toSeq`, but it doesn't copy non-immutable collections
7 warnings found

Source: Scala 2.13 Collections: Migration Guide

A class that was removed outright is a hard error:

//> using scala 3.10.0
@main def run(): Unit =
  val ms = scala.collection.mutable.MutableList(1)
-- [E008] Not Found Error: ./m5.scala:3:36
3 |  val ms = scala.collection.mutable.MutableList(1)
  |           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |           value MutableList is not a member of scala.collection.mutable
1 error found

Source: Scala 2.13 Collections: Migration Guide, things removed in 2.13

The Seq alias and varargs

The most invasive change is the meaning of Seq. Because scala.Seq is now immutable, a method that took Seq[Int] no longer accepts an ArrayBuffer, and the varargs parameter Int* demands an immutable sequence too.

//> using scala 3.10.0
import scala.collection.mutable.ArrayBuffer

def total(xs: Seq[Int]): Int = xs.sum
def count(xs: Int*): Int = xs.size

@main def run(): Unit =
  val buf = ArrayBuffer(1, 2, 3)
  println(total(buf))
  println(count(buf*))
-- [E007] Type Mismatch Error: ./m2.scala:9:16
9 |  println(total(buf))
  |                ^^^
  |               Found:    (buf : scala.collection.mutable.ArrayBuffer[Int])
  |               Required: Seq[Int]
  | longer explanation available when compiling with `-explain`
-- [E007] Type Mismatch Error: ./m2.scala:10:16
10 |  println(count(buf*))
   |                ^^^
   |             Found:    (buf : scala.collection.mutable.ArrayBuffer[Int])
   |             Required: Seq[Int] | Array[? <: Int]
   | longer explanation available when compiling with `-explain`
2 errors found

Source: Scala 2.13 Collections: Migration Guide

Three ways to migrate a library signature: take collection.Seq for parameters (accepts every sequence, mutable or not), take collection.Seq and return immutable.Seq (Postel’s law), or use immutable sequences on both sides. The program below shows the first form and the call-site fixes for varargs (buf.toSeq*, which copies only if the sequence is not already immutable, and arr*, which is accepted for an array), and the MapView behaviour:

//> using scala 3.10.0
import scala.collection.mutable.ArrayBuffer
import scala.collection

def total(xs: collection.Seq[Int]): Int = xs.sum
def count(xs: Int*): Int = xs.size

@main def run(): Unit =
  val buf = ArrayBuffer(1, 2, 3)
  println(total(buf))
  println(count(buf.toSeq*))
  val arr = Array(4, 5)
  println(count(arr.toSeq*))
  println(count(arr*))
  val scores = Map("a" -> 1, "b" -> 2)
  val view = scores.view.mapValues(_ * 10)
  println(view)
  println(scores.view.mapValues(_ * 10).toMap)
  println(scores.view.filterKeys(_ == "a").toMap)
  println(xs0.getClass)
  def xs0 = List(1).iterator
6
3
2
2
MapView(<not computed>)
Map(a -> 10, b -> 20)
Map(a -> 1)
class scala.collection.StrictOptimizedLinearSeqOps$$anon$1

Source: Scala 2.13 Collections: Migration Guide

Cross-building with scala-collection-compat

A library that must support 2.12 and later at the same time can use the scala-collection-compat module, which backports the 2.13 API (xs.to(List), view.mapValues, LazyList…​) to 2.11 and 2.12 and ships Scalafix rules (Collection213Upgrade and Collections213CrossCompat) that rewrite old code. The same source then compiles on both. The program below is for 2.12.21 and printed the same output on 2.13.18 (it is not needed on Scala 3, where the 2.13 API is built in):

//> using scala 2.12.21
//> using dep org.scala-lang.modules::scala-collection-compat:2.14.0
import scala.collection.compat._

object Main {
  def main(args: Array[String]): Unit = {
    val xs = List(3, 1, 2, 3)
    val asSet = xs.to(Set)
    val asVector = xs.to(Vector)
    val m = Map("a" -> 1, "b" -> 2).view.mapValues(_ * 10).toMap
    println(s"$asSet $asVector $m")
    println(scala.util.Properties.versionNumberString)
  }
}
Set(3, 1, 2) Vector(3, 1, 2, 3) Map(a -> 10, b -> 20)
2.12.21

Source: Scala 2.13 Collections: Migration Guide

The sbt form of the dependency is libraryDependencies += "org.scala-lang.modules" %% "scala-collection-compat" % "2.14.0"; in Scala CLI use //> using dep org.scala-lang.modules::scala-collection-compat:2.14.0, as in the example. The Scalafix rules themselves were not run here. For code that is only on Scala 3, no module is needed: scala-collection-compat is meant for cross-building with 2.12 and earlier.

Differences from Java and Kotlin

  • Java has no template traits. The Collection interfaces return fixed interface types (List<E> subList, Collection<E>), and the transformations of the streams API are separate from the collections: stream().map(...).collect(Collectors.toCollection(TreeSet::new)). A Collector plays the role of a Factory. User-defined collections extend AbstractList, AbstractSet or AbstractMap and get equals, hashCode and toString from them, but not typed operations. See The Collections Framework and Streams & Collectors.

  • Kotlin has extension functions over Iterable and Collection, so an operation is defined once for all of them, but its result type is fixed: filter and map on any Iterable return a List (on a Set too), and only Map.filter returns a Map. There is no per-collection result type like Scala’s SortedSet.map giving a SortedSet. Producing "any collection" is toCollection(destination). See Collections & Sequences.

  • Scala’s design pays for the typed results with a more complex hierarchy to extend; most code never writes a collection and only uses the operations. Defining a new operation for every collection type is the common extension, and an extension method with IsIterable or IsSeq does it in a few lines.

Pitfalls

  • Overriding one operation (take) in a custom collection instead of mixing in IterableOps: the other fifty still return the base type.

  • Forgetting iterableFactory, or leaving fromSpecific and newSpecificBuilder pointing at the parent’s defaults: operations compile and return the wrong type, as Recent1 showed.

  • A companion that extends the factory also defines apply, which shadows the constructor in Recent[B](...). Use new.

  • Not mixing in StrictOptimized...Ops in a strict collection: it works but is slower, because the default implementations go through views.

  • Extending Seq for a collection that does not satisfy the Seq laws (such as size of ++).

  • Writing a library API with Seq and being surprised that mutable sequences are rejected. Choose collection.Seq or immutable.Seq deliberately.

  • Using Iterable.from or a builder in a Factory-based function and losing laziness; prefer fromSpecific.

  • Using mapValues and expecting a strict map: the result is a lazy view that re-evaluates the function on each access.

Where the books are outdated

  • Scala 2.12 and earlier books (including the 2nd edition of Programming in Scala) describe CanBuildFrom, Traversable, GenTraversableLike and the *Like and *Builder families. They no longer exist; the *Ops templates, Factory and BuildFrom replace them.

  • The same books show breakOut, to[C], Stream, mapValues returning a Map, immutable Stack, ArrayStack and MutableList. See the migration table above.

  • Examples that define a custom collection by extending SeqLike or IterableLike with a newBuilder and canBuildFrom do not compile on 2.13 or Scala 3.

  • The official guide’s remark that an extension method does not work on String and Array is about Scala 2 implicits; on Scala 3 an extension on IterableOnce does (as shown), though transformations still need IsSeq and BuildFrom to keep the receiver’s type.

  • The official custom-collection pages show Scala 2 and Scala 3 side by side. Only the Scala 3 syntax is used on this page.

Scala 3.9 LTS versus 3.10

The collections library is the same on every Scala 3 release, and the template traits, factories and BuildFrom have not changed since 2.13. The programs of this page were compiled and run unchanged on 3.3.8, 3.9.0 and 3.10.0 and printed the same output (the only difference on 3.3.8 was a JDK warning about sun.misc.Unsafe); the migration examples gave the same compiler messages.

References