Scala 3
3.7.0
LearnInstallPlaygroundFind A LibraryCommunityBlog
LearnInstallPlaygroundFind A LibraryCommunityBlog
DocsAPI
Generated with
Copyright (c) 2002-2025, LAMP/EPFL
Copyright (c) 2002-2025, LAMP/EPFL
Scala 3/scala/scala.collection/scala.collection.immutable

scala.collection.immutable

package scala.collection.immutable

Members list

Type members

Classlikes

final case class ::[+A](head: A, var next: List[A]) extends List[A]

Attributes

Source
List.scala
Supertypes
trait Product
class List[A]
trait Serializable
trait LinearSeq[A]
trait LinearSeqOps[A, List, List[A]]
trait LinearSeq[A]
trait LinearSeqOps[A, List, List[A]]
class AbstractSeq[A]
trait Seq[A]
trait SeqOps[A, List, List[A]]
trait Iterable[A]
class AbstractSeq[A]
trait Seq[A]
trait Equals
trait SeqOps[A, List, List[A]]
trait PartialFunction[Int, A]
trait Int => A
class AbstractIterable[A]
trait Iterable[A]
trait IterableOps[A, List, List[A]]
trait IterableOnceOps[A, List, List[A]]
trait IterableOnce[A]
class Object
trait Matchable
class Any
Show all
abstract class AbstractMap[K, +V] extends AbstractMap[K, V], Map[K, V]

Explicit instantiation of the Map trait to reduce class file size in subclasses.

Explicit instantiation of the Map trait to reduce class file size in subclasses.

Attributes

Source
Map.scala
Supertypes
trait Map[K, V]
trait MapOps[K, V, Map, Map[K, V]]
trait Iterable[(K, V)]
class AbstractMap[K, V]
trait Map[K, V]
trait Equals
trait MapOps[K, V, Map, Map[K, V]]
trait PartialFunction[K, V]
trait K => V
class AbstractIterable[(K, V)]
trait Iterable[(K, V)]
trait IterableOps[(K, V), Iterable, Map[K, V]]
trait IterableOnceOps[(K, V), Iterable, Map[K, V]]
trait IterableOnce[(K, V)]
class Object
trait Matchable
class Any
Show all
Known subtypes
class HashMap[K, V]
class IntMap[T]
class ListMap[K, V]
class LongMap[T]
class Map1[K, V]
class Map2[K, V]
class Map3[K, V]
class Map4[K, V]
class WithDefault[K, V]
class WithDefault[K, V]
class TreeMap[K, V]
class TreeSeqMap[K, V]
class VectorMap[K, V]
Show all
abstract class AbstractSeq[+A] extends AbstractSeq[A], Seq[A]

Explicit instantiation of the Seq trait to reduce class file size in subclasses.

Explicit instantiation of the Seq trait to reduce class file size in subclasses.

Attributes

Source
Seq.scala
Supertypes
trait Seq[A]
trait SeqOps[A, Seq, Seq[A]]
trait Iterable[A]
class AbstractSeq[A]
trait Seq[A]
trait Equals
trait SeqOps[A, Seq, Seq[A]]
trait PartialFunction[Int, A]
trait Int => A
class AbstractIterable[A]
trait Iterable[A]
trait IterableOps[A, Seq, Seq[A]]
trait IterableOnceOps[A, Seq, Seq[A]]
trait IterableOnce[A]
class Object
trait Matchable
class Any
Show all
Known subtypes
class ArraySeq[A]
class ofBoolean
class ofByte
class ofChar
class ofDouble
class ofFloat
class ofInt
class ofLong
class ofRef[T]
class ofShort
class ofUnit
class LazyList[A]
class List[A]
class ::[A]
object Nil
class NumericRange[T]
class Exclusive[T]
class Inclusive[T]
class Queue[A]
class Range
class Exclusive
class Inclusive
class Stream[A]
class Cons[A]
object Empty
class Vector[A]
Show all
abstract class AbstractSet[A] extends AbstractSet[A], Set[A]

Explicit instantiation of the Set trait to reduce class file size in subclasses.

Explicit instantiation of the Set trait to reduce class file size in subclasses.

Attributes

Source
Set.scala
Supertypes
trait Set[A]
trait SetOps[A, Set, Set[A]]
trait Iterable[A]
class AbstractSet[A]
trait Set[A]
trait Equals
trait SetOps[A, Set, Set[A]]
trait A => Boolean
class AbstractIterable[A]
trait Iterable[A]
trait IterableOps[A, Set, Set[A]]
trait IterableOnceOps[A, Set, Set[A]]
trait IterableOnce[A]
class Object
trait Matchable
class Any
Show all
Known subtypes
class BitSet
class BitSet1
class BitSet2
class BitSetN
class HashSet[A]
class ListSet[A]
class Set1[A]
class Set2[A]
class Set3[A]
class Set4[A]
class TreeSet[A]
class ValueSet
Show all
sealed abstract class ArraySeq[+A] extends AbstractSeq[A], IndexedSeq[A], IndexedSeqOps[A, ArraySeq, ArraySeq[A]], StrictOptimizedSeqOps[A, ArraySeq, ArraySeq[A]], EvidenceIterableFactoryDefaults[A, ArraySeq, ClassTag], Serializable

An immutable array.

An immutable array.

Supports efficient indexed access and has a small memory footprint.

Attributes

Companion
object
Source
ArraySeq.scala
Supertypes
trait Serializable
trait IndexedSeq[A]
trait IndexedSeq[A]
class AbstractSeq[A]
trait Seq[A]
trait SeqOps[A, ArraySeq, ArraySeq[A]]
trait Iterable[A]
class AbstractSeq[A]
trait Seq[A]
trait Equals
trait SeqOps[A, ArraySeq, ArraySeq[A]]
trait PartialFunction[Int, A]
trait Int => A
class AbstractIterable[A]
trait Iterable[A]
trait IterableOps[A, ArraySeq, ArraySeq[A]]
trait IterableOnce[A]
class Object
trait Matchable
class Any
Show all
Known subtypes
class ofBoolean
class ofByte
class ofChar
class ofDouble
class ofFloat
class ofInt
class ofLong
class ofRef[T]
class ofShort
class ofUnit
Show all
object ArraySeq extends StrictOptimizedClassTagSeqFactory[ArraySeq]

This object provides a set of operations to create Iterable values.

This object provides a set of operations to create Iterable values.

Attributes

Companion
class
Source
ArraySeq.scala
Supertypes
trait Serializable
class Object
trait Matchable
class Any
Show all
Self type
ArraySeq.type
sealed abstract class BitSet extends AbstractSet[Int], SortedSet[Int], SortedSetOps[Int, SortedSet, BitSet], StrictOptimizedSortedSetOps[Int, SortedSet, BitSet], BitSet, BitSetOps[BitSet], Serializable

A class for immutable bitsets.

A class for immutable bitsets.

Bitsets are sets of non-negative integers which are represented as variable-size arrays of bits packed into 64-bit words. The lower bound of memory footprint of a bitset is determined by the largest number stored in it.

Attributes

See also

"Scala's Collection Library overview" section on Immutable BitSets for more information.

Companion
object
Source
BitSet.scala
Supertypes
trait Serializable
trait BitSet
trait BitSetOps[BitSet]
trait SortedSet[Int]
trait SortedSet[Int]
trait SortedOps[Int, BitSet]
class AbstractSet[Int]
trait Set[Int]
trait SetOps[Int, Set, BitSet]
trait Iterable[Int]
class AbstractSet[Int]
trait Set[Int]
trait Equals
trait SetOps[Int, Set, BitSet]
trait Int => Boolean
trait Iterable[Int]
trait IterableOnce[Int]
class Object
trait Matchable
class Any
Show all
Known subtypes
class BitSet1
class BitSet2
class BitSetN
object BitSet extends SpecificIterableFactory[Int, BitSet]

This object provides a set of operations to create Iterable values.

This object provides a set of operations to create Iterable values.

Attributes

Companion
class
Source
BitSet.scala
Supertypes
trait Serializable
trait Factory[Int, BitSet]
class Object
trait Matchable
class Any
Show all
Self type
BitSet.type
final class HashMap[K, +V] extends AbstractMap[K, V], StrictOptimizedMapOps[K, V, HashMap, HashMap[K, V]], MapFactoryDefaults[K, V, HashMap, Iterable], DefaultSerializable

This class implements immutable maps using a Compressed Hash-Array Mapped Prefix-tree.

This class implements immutable maps using a Compressed Hash-Array Mapped Prefix-tree. See paper https://michael.steindorfer.name/publications/oopsla15.pdf for more details.

Type parameters

K

the type of the keys contained in this hash set.

V

the type of the values associated with the keys in this hash map.

Attributes

Companion
object
Source
HashMap.scala
Supertypes
trait Serializable
trait StrictOptimizedMapOps[K, V, HashMap, HashMap[K, V]]
trait StrictOptimizedMapOps[K, V, HashMap, HashMap[K, V]]
class AbstractMap[K, V]
trait Map[K, V]
trait MapOps[K, V, HashMap, HashMap[K, V]]
trait Iterable[(K, V)]
class AbstractMap[K, V]
trait Map[K, V]
trait Equals
trait MapOps[K, V, HashMap, HashMap[K, V]]
trait PartialFunction[K, V]
trait K => V
class AbstractIterable[(K, V)]
trait Iterable[(K, V)]
trait IterableOps[(K, V), Iterable, HashMap[K, V]]
trait IterableOnceOps[(K, V), Iterable, HashMap[K, V]]
trait IterableOnce[(K, V)]
class Object
trait Matchable
class Any
Show all
object HashMap extends MapFactory[HashMap]

This object provides a set of operations to create Iterable values.

This object provides a set of operations to create Iterable values.

Attributes

Companion
class
Source
HashMap.scala
Supertypes
trait Serializable
class Object
trait Matchable
class Any
Self type
HashMap.type
final class HashSet[A] extends AbstractSet[A], StrictOptimizedSetOps[A, HashSet, HashSet[A]], IterableFactoryDefaults[A, HashSet], DefaultSerializable

This class implements immutable sets using a Compressed Hash-Array Mapped Prefix-tree.

This class implements immutable sets using a Compressed Hash-Array Mapped Prefix-tree. See paper https://michael.steindorfer.name/publications/oopsla15.pdf for more details.

Type parameters

A

the type of the elements contained in this hash set.

Attributes

Companion
object
Source
HashSet.scala
Supertypes
trait Serializable
class AbstractSet[A]
trait Set[A]
trait SetOps[A, HashSet, HashSet[A]]
trait Iterable[A]
class AbstractSet[A]
trait Set[A]
trait Equals
trait SetOps[A, HashSet, HashSet[A]]
trait A => Boolean
class AbstractIterable[A]
trait Iterable[A]
trait IterableOps[A, HashSet, HashSet[A]]
trait IterableOnce[A]
class Object
trait Matchable
class Any
Show all
object HashSet extends IterableFactory[HashSet]

This object provides a set of operations to create Iterable values.

This object provides a set of operations to create Iterable values.

Attributes

Companion
class
Source
HashSet.scala
Supertypes
trait Serializable
class Object
trait Matchable
class Any
Self type
HashSet.type
trait IndexedSeq[+A] extends Seq[A], IndexedSeq[A], IndexedSeqOps[A, IndexedSeq, IndexedSeq[A]], IterableFactoryDefaults[A, IndexedSeq]

Base trait for immutable indexed sequences that have efficient apply and length

Base trait for immutable indexed sequences that have efficient apply and length

Attributes

Companion
object
Source
Seq.scala
Supertypes
trait IndexedSeq[A]
trait Seq[A]
trait SeqOps[A, IndexedSeq, IndexedSeq[A]]
trait Seq[A]
trait Equals
trait SeqOps[A, IndexedSeq, IndexedSeq[A]]
trait PartialFunction[Int, A]
trait Int => A
trait Iterable[A]
trait Iterable[A]
trait IterableOnce[A]
class Object
trait Matchable
class Any
Show all
Known subtypes
class ArraySeq[A]
class ofBoolean
class ofByte
class ofChar
class ofDouble
class ofFloat
class ofInt
class ofLong
class ofRef[T]
class ofShort
class ofUnit
class NumericRange[T]
class Exclusive[T]
class Inclusive[T]
class Range
class Exclusive
class Inclusive
class Vector[A]
Show all
object IndexedSeq extends Delegate[IndexedSeq]

Attributes

Companion
trait
Source
Seq.scala
Supertypes
trait Serializable
class Object
trait Matchable
class Any
Show all
Self type
IndexedSeq.type
object IndexedSeqDefaults

Attributes

Source
Seq.scala
Supertypes
class Object
trait Matchable
class Any
Self type
trait IndexedSeqOps[+A, +CC[_], +C] extends SeqOps[A, CC, C], IndexedSeqOps[A, CC, C]

Base trait for immutable indexed Seq operations

Base trait for immutable indexed Seq operations

Attributes

Source
Seq.scala
Supertypes
trait IndexedSeqOps[A, CC, C]
trait SeqOps[A, CC, C]
trait SeqOps[A, CC, C]
trait IterableOps[A, CC, C]
trait IterableOnceOps[A, CC, C]
trait IterableOnce[A]
class Object
trait Matchable
class Any
Show all
Known subtypes
class ArraySeq[A]
class ofBoolean
class ofByte
class ofChar
class ofDouble
class ofFloat
class ofInt
class ofLong
class ofRef[T]
class ofShort
class ofUnit
trait IndexedSeq[A]
class NumericRange[T]
class Exclusive[T]
class Inclusive[T]
class Range
class Exclusive
class Inclusive
class Vector[A]
Show all
object IntMap

A companion object for integer maps.

A companion object for integer maps.

Attributes

Companion
class
Source
IntMap.scala
Supertypes
trait Serializable
class Object
trait Matchable
class Any
Self type
IntMap.type
sealed abstract class IntMap[+T] extends AbstractMap[Int, T], StrictOptimizedMapOps[Int, T, Map, IntMap[T]], Serializable

Specialised immutable map structure for integer keys, based on Fast Mergeable Integer Maps by Okasaki and Gill.

Specialised immutable map structure for integer keys, based on Fast Mergeable Integer Maps by Okasaki and Gill. Essentially a trie based on binary digits of the integers.

Note: This class is as of 2.8 largely superseded by HashMap.

Type parameters

T

type of the values associated with integer keys.

Attributes

Companion
object
Source
IntMap.scala
Supertypes
trait Serializable
class AbstractMap[Int, T]
trait Map[Int, T]
trait MapOps[Int, T, Map, IntMap[T]]
trait Iterable[(Int, T)]
class AbstractMap[Int, T]
trait Map[Int, T]
trait Equals
trait MapOps[Int, T, Map, IntMap[T]]
trait PartialFunction[Int, T]
trait Int => T
class AbstractIterable[(Int, T)]
trait Iterable[(Int, T)]
trait IterableOps[(Int, T), Iterable, IntMap[T]]
trait IterableOnceOps[(Int, T), Iterable, IntMap[T]]
trait IterableOnce[(Int, T)]
class Object
trait Matchable
class Any
Show all
trait Iterable[+A] extends Iterable[A], IterableOps[A, Iterable, Iterable[A]], IterableFactoryDefaults[A, Iterable]

A trait for collections that are guaranteed immutable.

A trait for collections that are guaranteed immutable.

Type parameters

A

the element type of the collection

Attributes

Companion
object
Source
Iterable.scala
Supertypes
trait Iterable[A]
trait IterableOps[A, Iterable, Iterable[A]]
trait IterableOnce[A]
class Object
trait Matchable
class Any
Show all
Known subtypes
trait Map[K, V]
class AbstractMap[K, V]
class HashMap[K, V]
class IntMap[T]
class ListMap[K, V]
class LongMap[T]
class Map1[K, V]
class Map2[K, V]
class Map3[K, V]
class Map4[K, V]
class WithDefault[K, V]
class WithDefault[K, V]
class TreeMap[K, V]
class TreeSeqMap[K, V]
class VectorMap[K, V]
trait SeqMap[K, V]
trait SortedMap[K, V]
trait Seq[A]
class AbstractSeq[A]
class ArraySeq[A]
class ofBoolean
class ofByte
class ofChar
class ofDouble
class ofFloat
class ofInt
class ofLong
class ofRef[T]
class ofShort
class ofUnit
class LazyList[A]
class List[A]
class ::[A]
object Nil
class NumericRange[T]
class Exclusive[T]
class Inclusive[T]
class Queue[A]
class Range
class Exclusive
class Inclusive
class Stream[A]
class Cons[A]
object Empty
class Vector[A]
trait IndexedSeq[A]
trait LinearSeq[A]
trait Set[A]
class AbstractSet[A]
class BitSet
class BitSet1
class BitSet2
class BitSetN
class HashSet[A]
class ListSet[A]
class Set1[A]
class Set2[A]
class Set3[A]
class Set4[A]
class TreeSet[A]
class ValueSet
trait SortedSet[A]
Show all
object Iterable extends Delegate[Iterable]

Attributes

Companion
trait
Source
Iterable.scala
Supertypes
trait Serializable
class Object
trait Matchable
class Any
Show all
Self type
Iterable.type
final class LazyList[+A] extends AbstractSeq[A], LinearSeq[A], LinearSeqOps[A, LazyList, LazyList[A]], IterableFactoryDefaults[A, LazyList], Serializable

This class implements an immutable linked list.

This class implements an immutable linked list. We call it "lazy" because it computes its elements only when they are needed.

Elements are memoized; that is, the value of each element is computed at most once.

Elements are computed in-order and are never skipped. In other words, accessing the tail causes the head to be computed first.

How lazy is a LazyList? When you have a value of type LazyList, you don't know yet whether the list is empty or not. If you learn that it is non-empty, then you also know that the head has been computed. But the tail is itself a LazyList, whose emptiness-or-not might remain undetermined.

A LazyList may be infinite. For example, LazyList.from(0) contains all of the natural numbers 0, 1, 2, and so on. For infinite sequences, some methods (such as count, sum, max or min) will not terminate.

Here is an example:

import scala.math.BigInt
object Main extends App {
  val fibs: LazyList[BigInt] =
    BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map{ n => n._1 + n._2 }
  fibs.take(5).foreach(println)
}

// prints
//
// 0
// 1
// 1
// 2
// 3

To illustrate, let's add some output to the definition fibs, so we see what's going on.

import scala.math.BigInt
object Main extends App {
  val fibs: LazyList[BigInt] =
    BigInt(0) #:: BigInt(1) #::
      fibs.zip(fibs.tail).map{ n =>
        println(s"Adding ${n._1} and ${n._2}")
        n._1 + n._2
      }
  fibs.take(5).foreach(println)
  fibs.take(6).foreach(println)
}

// prints
//
// 0
// 1
// Adding 0 and 1
// 1
// Adding 1 and 1
// 2
// Adding 1 and 2
// 3

// And then prints
//
// 0
// 1
// 1
// 2
// 3
// Adding 2 and 3
// 5

Note that the definition of fibs uses val not def. The memoization of the LazyList requires us to have somewhere to store the information and a val allows us to do that.

Further remarks about the semantics of LazyList:

- Though the LazyList changes as it is accessed, this does not contradict its immutability. Once the values are memoized they do not change. Values that have yet to be memoized still "exist", they simply haven't been computed yet.

- One must be cautious of memoization; it can eat up memory if you're not careful. That's because memoization of the LazyList creates a structure much like scala.collection.immutable.List. As long as something is holding on to the head, the head holds on to the tail, and so on recursively. If, on the other hand, there is nothing holding on to the head (e.g. if we used def to define the LazyList) then once it is no longer being used directly, it disappears.

- Note that some operations, including drop, dropWhile, flatMap or collect may process a large number of intermediate elements before returning.

Here's another example. Let's start with the natural numbers and iterate over them.

// We'll start with a silly iteration
def loop(s: String, i: Int, iter: Iterator[Int]): Unit = {
  // Stop after 200,000
  if (i < 200001) {
    if (i % 50000 == 0) println(s + i)
    loop(s, iter.next(), iter)
  }
}

// Our first LazyList definition will be a val definition
val lazylist1: LazyList[Int] = {
  def loop(v: Int): LazyList[Int] = v #:: loop(v + 1)
  loop(0)
}

// Because lazylist1 is a val, everything that the iterator produces is held
// by virtue of the fact that the head of the LazyList is held in lazylist1
val it1 = lazylist1.iterator
loop("Iterator1: ", it1.next(), it1)

// We can redefine this LazyList such that all we have is the Iterator left
// and allow the LazyList to be garbage collected as required.  Using a def
// to provide the LazyList ensures that no val is holding onto the head as
// is the case with lazylist1
def lazylist2: LazyList[Int] = {
  def loop(v: Int): LazyList[Int] = v #:: loop(v + 1)
  loop(0)
}
val it2 = lazylist2.iterator
loop("Iterator2: ", it2.next(), it2)

// And, of course, we don't actually need a LazyList at all for such a simple
// problem.  There's no reason to use a LazyList if you don't actually need
// one.
val it3 = new Iterator[Int] {
  var i = -1
  def hasNext = true
  def next(): Int = { i += 1; i }
}
loop("Iterator3: ", it3.next(), it3)

In the fibs example earlier, the fact that tail works at all is of interest. fibs has an initial (0, 1, LazyList(...)), so tail is deterministic. If we defined fibs such that only 0 were concretely known, then the act of determining tail would require the evaluation of tail, so the computation would be unable to progress, as in this code:

// The first time we try to access the tail we're going to need more
// information which will require us to recurse, which will require us to
// recurse, which...
lazy val sov: LazyList[Vector[Int]] = Vector(0) #:: sov.zip(sov.tail).map { n => n._1 ++ n._2 }

The definition of fibs above creates a larger number of objects than necessary depending on how you might want to implement it. The following implementation provides a more "cost effective" implementation due to the fact that it has a more direct route to the numbers themselves:

lazy val fib: LazyList[Int] = {
  def loop(h: Int, n: Int): LazyList[Int] = h #:: loop(n, h + n)
  loop(1, 1)
}

The head, the tail and whether the list is empty or not can be initially unknown. Once any of those are evaluated, they are all known, though if the tail is built with #:: or #:::, it's content still isn't evaluated. Instead, evaluating the tails content is deferred until the tails empty status, head or tail is evaluated.

Delaying the evaluation of whether a LazyList is empty or not until it's needed allows LazyList to not eagerly evaluate any elements on a call to filter.

Only when it's further evaluated (which may be never!) any of the elements gets forced.

for example:

def tailWithSideEffect: LazyList[Nothing] = {
  println("getting empty LazyList")
  LazyList.empty
}

val emptyTail = tailWithSideEffect // prints "getting empty LazyList"

val suspended = 1 #:: tailWithSideEffect // doesn't print anything
val tail = suspended.tail // although the tail is evaluated, *still* nothing is yet printed
val filtered = tail.filter(_ => false) // still nothing is printed
filtered.isEmpty // prints "getting empty LazyList"

You may sometimes encounter an exception like the following:

java.lang.RuntimeException: "LazyList evaluation depends on its own result (self-reference); see docs for more info

This exception occurs when a LazyList is attempting to derive its next element from itself, and is attempting to read the element currently being evaluated. A trivial example of such might be

lazy val a: LazyList[Int] = 1 #:: 2 #:: a.filter(_ > 2)

When attempting to evaluate the third element of a, it will skip the first two elements and read the third, but that element is already being evaluated. This is often caused by a subtle logic error; in this case, using >= in the filter would fix the error.

Type parameters

A

the type of the elements contained in this lazy list.

Attributes

See also

"Scala's Collection Library overview" section on LazyLists for more information.

Companion
object
Source
LazyList.scala
Supertypes
trait Serializable
trait LinearSeq[A]
trait LinearSeq[A]
class AbstractSeq[A]
trait Seq[A]
trait SeqOps[A, LazyList, LazyList[A]]
trait Iterable[A]
class AbstractSeq[A]
trait Seq[A]
trait Equals
trait SeqOps[A, LazyList, LazyList[A]]
trait PartialFunction[Int, A]
trait Int => A
class AbstractIterable[A]
trait Iterable[A]
trait IterableOps[A, LazyList, LazyList[A]]
trait IterableOnce[A]
class Object
trait Matchable
class Any
Show all
object LazyList extends SeqFactory[LazyList]

This object provides a set of operations to create Iterable values.

This object provides a set of operations to create Iterable values.

Attributes

Companion
class
Source
LazyList.scala
Supertypes
trait Serializable
class Object
trait Matchable
class Any
Show all
Self type
LazyList.type
trait LinearSeq[+A] extends Seq[A], LinearSeq[A], LinearSeqOps[A, LinearSeq, LinearSeq[A]], IterableFactoryDefaults[A, LinearSeq]

Base trait for immutable linear sequences that have efficient head and tail

Base trait for immutable linear sequences that have efficient head and tail

Attributes

Companion
object
Source
Seq.scala
Supertypes
trait LinearSeq[A]
trait Seq[A]
trait SeqOps[A, LinearSeq, LinearSeq[A]]
trait Seq[A]
trait Equals
trait SeqOps[A, LinearSeq, LinearSeq[A]]
trait PartialFunction[Int, A]
trait Int => A
trait Iterable[A]
trait Iterable[A]
trait IterableOnce[A]
class Object
trait Matchable
class Any
Show all
Known subtypes
class LazyList[A]
class List[A]
class ::[A]
object Nil
class Queue[A]
class Stream[A]
class Cons[A]
object Empty
Show all
object LinearSeq extends Delegate[LinearSeq]

Attributes

Companion
trait
Source
Seq.scala
Supertypes
trait Serializable
class Object
trait Matchable
class Any
Show all
Self type
LinearSeq.type
trait LinearSeqOps[+A, +CC <: (LinearSeq), +C <: LinearSeq[A] & LinearSeqOps[A, CC, C]] extends SeqOps[A, CC, C], LinearSeqOps[A, CC, C]

Attributes

Source
Seq.scala
Supertypes
trait LinearSeqOps[A, CC, C]
trait SeqOps[A, CC, C]
trait SeqOps[A, CC, C]
trait IterableOps[A, CC, C]
trait IterableOnceOps[A, CC, C]
trait IterableOnce[A]
class Any
Show all
Known subtypes
class LazyList[A]
trait LinearSeq[A]
class List[A]
class ::[A]
object Nil
class Queue[A]
class Stream[A]
class Cons[A]
object Empty
Show all
sealed abstract class List[+A] extends AbstractSeq[A], LinearSeq[A], LinearSeqOps[A, List, List[A]], StrictOptimizedLinearSeqOps[A, List, List[A]], StrictOptimizedSeqOps[A, List, List[A]], IterableFactoryDefaults[A, List], DefaultSerializable

A class for immutable linked lists representing ordered collections of elements of type A.

A class for immutable linked lists representing ordered collections of elements of type A.

This class comes with two implementing case classes scala.Nil and scala.:: that implement the abstract members isEmpty, head and tail.

This class is optimal for last-in-first-out (LIFO), stack-like access patterns. If you need another access pattern, for example, random access or FIFO, consider using a collection more suited to this than List.

Performance

Time: List has O(1) prepend and head/tail access. Most other operations are O(n) on the number of elements in the list. This includes the index-based lookup of elements, length, append and reverse.

Space: List implements structural sharing of the tail list. This means that many operations are either zero- or constant-memory cost.

val mainList = List(3, 2, 1)
val with4 =    4 :: mainList  // re-uses mainList, costs one :: instance
val with42 =   42 :: mainList // also re-uses mainList, cost one :: instance
val shorter =  mainList.tail  // costs nothing as it uses the same 2::1::Nil instances as mainList

Attributes

See also

"Scala's Collection Library overview" section on Lists for more information.

Note

The functional list is characterized by persistence and structural sharing, thus offering considerable performance and space consumption benefits in some scenarios if used correctly. However, note that objects having multiple references into the same functional list (that is, objects that rely on structural sharing), will be serialized and deserialized with multiple lists, one for each reference to it. I.e. structural sharing is lost after serialization/deserialization.

Example 

// Make a list via the companion object factory
val days = List("Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday")
// Make a list element-by-element
val when = "AM" :: "PM" :: Nil
// Pattern match
days match {
  case firstDay :: otherDays =>
    println("The first day of the week is: " + firstDay)
  case Nil =>
    println("There don't seem to be any week days.")
}
Companion
object
Source
List.scala
Supertypes
trait Serializable
trait LinearSeq[A]
trait LinearSeqOps[A, List, List[A]]
trait LinearSeq[A]
trait LinearSeqOps[A, List, List[A]]
class AbstractSeq[A]
trait Seq[A]
trait SeqOps[A, List, List[A]]
trait Iterable[A]
class AbstractSeq[A]
trait Seq[A]
trait Equals
trait SeqOps[A, List, List[A]]
trait PartialFunction[Int, A]
trait Int => A
class AbstractIterable[A]
trait Iterable[A]
trait IterableOps[A, List, List[A]]
trait IterableOnceOps[A, List, List[A]]
trait IterableOnce[A]
class Object
trait Matchable
class Any
Show all
Known subtypes
class ::[A]
object Nil
object List extends StrictOptimizedSeqFactory[List]

This object provides a set of operations to create Iterable values.

This object provides a set of operations to create Iterable values.

Attributes

Companion
class
Source
List.scala
Supertypes
trait SeqFactory[List]
trait Serializable
class Object
trait Matchable
class Any
Show all
Self type
List.type
sealed class ListMap[K, +V] extends AbstractMap[K, V], SeqMap[K, V], StrictOptimizedMapOps[K, V, ListMap, ListMap[K, V]], MapFactoryDefaults[K, V, ListMap, Iterable], DefaultSerializable

This class implements immutable maps using a list-based data structure.

This class implements immutable maps using a list-based data structure. List map iterators and traversal methods visit key-value pairs in the order they were first inserted.

Entries are stored internally in reversed insertion order, which means the newest key is at the head of the list. As such, methods such as head and tail are O(n), while last and init are O(1). Other operations, such as inserting or removing entries, are also O(n), which makes this collection suitable only for a small number of elements.

Instances of ListMap represent empty maps; they can be either created by calling the constructor directly, or by applying the function ListMap.empty.

Type parameters

K

the type of the keys contained in this list map

V

the type of the values associated with the keys

Attributes

Companion
object
Source
ListMap.scala
Supertypes
trait Serializable
trait StrictOptimizedMapOps[K, V, ListMap, ListMap[K, V]]
trait StrictOptimizedMapOps[K, V, ListMap, ListMap[K, V]]
trait SeqMap[K, V]
trait SeqMap[K, V]
class AbstractMap[K, V]
trait Map[K, V]
trait MapOps[K, V, ListMap, ListMap[K, V]]
trait Iterable[(K, V)]
class AbstractMap[K, V]
trait Map[K, V]
trait Equals
trait MapOps[K, V, ListMap, ListMap[K, V]]
trait PartialFunction[K, V]
trait K => V
class AbstractIterable[(K, V)]
trait Iterable[(K, V)]
trait IterableOps[(K, V), Iterable, ListMap[K, V]]
trait IterableOnceOps[(K, V), Iterable, ListMap[K, V]]
trait IterableOnce[(K, V)]
class Object
trait Matchable
class Any
Show all
object ListMap extends MapFactory[ListMap]

This object provides a set of operations to create Iterable values.

This object provides a set of operations to create Iterable values.

Note that each element insertion takes O(n) time, which means that creating a list map with n elements will take O(n2) time. This makes the builder suitable only for a small number of elements.

Attributes

See also

"Scala's Collection Library overview" section on List Maps for more information.

Companion
class
Source
ListMap.scala
Supertypes
trait Serializable
class Object
trait Matchable
class Any
Self type
ListMap.type
sealed class ListSet[A] extends AbstractSet[A], StrictOptimizedSetOps[A, ListSet, ListSet[A]], IterableFactoryDefaults[A, ListSet], DefaultSerializable

This class implements immutable sets using a list-based data structure.

This class implements immutable sets using a list-based data structure. List set iterators and traversal methods visit elements in the order they were first inserted.

Elements are stored internally in reversed insertion order, which means the newest element is at the head of the list. As such, methods such as head and tail are O(n), while last and init are O(1). Other operations, such as inserting or removing entries, are also O(n), which makes this collection suitable only for a small number of elements.

Instances of ListSet represent empty sets; they can be either created by calling the constructor directly, or by applying the function ListSet.empty.

Type parameters

A

the type of the elements contained in this list set

Attributes

Companion
object
Source
ListSet.scala
Supertypes
trait Serializable
class