Explicit instantiation of the Map
trait to reduce class file size in subclasses.
Explicit instantiation of the Seq
trait to reduce class file size in subclasses.
Explicit instantiation of the Set
trait to reduce class file size in subclasses.
An immutable array.
Supports efficient indexed access and has a small memory footprint.
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 memory footprint of a bitset is determined by the largest number stored in it.
"Scala's Collection Library overview" section on Immutable BitSets
for more information.
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.
the type of the keys contained in this hash set.
the type of the values associated with the keys in this hash map.
2.13
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.
the type of the elements contained in this hash set.
2.13
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 of the values associated with integer keys.
2.7
A trait for collections that are guaranteed immutable.
the element type of the collection
This class implements an immutable linked list that evaluates elements in order and only when needed. 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
Elements of a LazyList
are memoized; that is, the value of each element is computed only once. To illustrate, we will alter body of the fibs
value above and take some more values:
import scala.math.BigInt object Main extends App { val fibs: LazyList[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip( fibs.tail).map(n => { println("Adding %d and %d".format(n._1, 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
There are a number of subtle points to the above example.
fibs
is a val
not a method. The memoization of the LazyList
requires us to have somewhere to store the information and a val
allows us to do that.While the LazyList
is actually being modified during access, this does not change the notion of its immutability. Once the values are memoized they do not change and values that have yet to be memoized still "exist", they simply haven't been realized yet.One must be cautious of memoization; you can very quickly eat up large amounts of memory if you're not careful. The reason for this is that the memoization of the LazyList
creates a structure much like scala.collection.immutable.List. So long as something is holding on to the head, the head holds on to the tail, and so it continues recursively. If, on the other hand, there is nothing holding on to the head (e.g. 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. These necessarily hold onto the head, since they are methods on LazyList
, and a lazy list holds its own head. For computations of this sort where memoization is not desired, use Iterator
when possible.// For example, let's build the natural numbers and do some silly iteration // 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)
tail
works at all is of interest. In the definition of fibs
we have 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
which would cause an infinite recursion and stack overflow. If we define a definition where the tail is not initially computable then we're going to have an infinite recursion:// 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 type of the elements contained in this lazy list.
2.13
"Scala's Collection Library overview" section on LazyLists
for more information.
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
.
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
// 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.") }
1.0
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.
"Scala's Collection Library overview" section on Lists
for more information.
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
.
the type of the keys contained in this list map
the type of the values associated with the keys
1
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
.
the type of the elements contained in this list set
1
Specialised immutable map structure for long keys, based on Fast Mergeable Long 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 of the values associated with the long keys.
2.7
NumericRange
is a more generic version of the Range
class which works with arbitrary types. It must be supplied with an Integral
implementation of the range type.
Factories for likely types include Range.BigInt
, Range.Long
, and Range.BigDecimal
. Range.Int
exists for completeness, but the Int
-based scala.Range
should be more performant.
val r1 = Range(0, 100, 1) val veryBig = Int.MaxValue.toLong + 1 val r2 = Range.Long(veryBig, veryBig + 100, 1) assert(r1 sameElements r2.map(_ - veryBig))
Queue
objects implement data structures that allow to insert and retrieve elements in a first-in-first-out (FIFO) manner.
Queue
is implemented as a pair of List
s, one containing the in elements and the other the out elements. Elements are added to the in list and removed from the out list. When the out list runs dry, the queue is pivoted by replacing the out list by in.reverse, and in by Nil.
Adding items to the queue always has cost O(1)
. Removing items has cost O(1)
, except in the case where a pivot is required, in which case, a cost of O(n)
is incurred, where n
is the number of elements in the queue. When this happens, n
remove operations with O(1)
cost are guaranteed. Removing an item is on average O(1)
.
1
"Scala's Collection Library overview" section on Immutable Queues
for more information.
The Range
class represents integer values in range [start;end) with non-zero step value step
. It's a special case of an indexed sequence. For example:
val r1 = 0 until 10 val r2 = r1.start until r1.end by r1.step + 1 println(r2.length) // = 5
Ranges that contain more than Int.MaxValue
elements can be created, but these overfull ranges have only limited capabilities. Any method that could require a collection of over Int.MaxValue
length to be created, or could be asked to index beyond Int.MaxValue
elements will throw an exception. Overfull ranges can safely be reduced in size by changing the step size (e.g. by 3
) or taking/dropping elements. contains
, equals
, and access to the ends of the range (head
, last
, tail
, init
) are also permitted on overfull ranges.
A generic trait for ordered immutable maps. Concrete classes have to provide functionality for the abstract methods in SeqMap
.
Note that when checking for equality SeqMap does not take into account ordering.
the type of the keys contained in this linked map.
the type of the values associated with the keys in this linked map.
2.13
2.13
An immutable map whose key-value pairs are sorted according to an scala.math.Ordering on the keys.
Allows for range queries to be performed on its keys, and implementations must guarantee that traversal happens in sorted order, according to the map's scala.math.Ordering.
the type of the keys contained in this tree map.
the type of the values associated with the keys.
import scala.collection.immutable.SortedMap // Make a SortedMap via the companion object factory val weekdays = SortedMap( 2 -> "Monday", 3 -> "Tuesday", 4 -> "Wednesday", 5 -> "Thursday", 6 -> "Friday" ) // TreeMap(2 -> Monday, 3 -> Tuesday, 4 -> Wednesday, 5 -> Thursday, 6 -> Friday) val days = weekdays ++ List(1 -> "Sunday", 7 -> "Saturday") // TreeMap(1 -> Sunday, 2 -> Monday, 3 -> Tuesday, 4 -> Wednesday, 5 -> Thursday, 6 -> Friday, 7 -> Saturday) val day3 = days.get(3) // Some("Tuesday") val rangeOfDays = days.range(2, 5) // TreeMap(2 -> Monday, 3 -> Tuesday, 4 -> Wednesday) val daysUntil2 = days.rangeUntil(2) // TreeMap(1 -> Sunday) val daysTo2 = days.rangeTo(2) // TreeMap(1 -> Sunday, 2 -> Monday) val daysAfter5 = days.rangeFrom(5) // TreeMap(5 -> Thursday, 6 -> Friday, 7 -> Saturday)
An immutable SortedMap whose values are stored in a red-black tree.
This class is optimal when range queries will be performed, or when traversal in order of an ordering is desired. If you only need key lookups, and don't care in which order key-values are traversed in, consider using * scala.collection.immutable.HashMap, which will generally have better performance. If you need insertion order, consider a * scala.collection.immutable.SeqMap, which does not need to have an ordering supplied.
the type of the keys contained in this tree map.
the type of the values associated with the keys.
import scala.collection.immutable.TreeMap // Make a TreeMap via the companion object factory val weekdays = TreeMap( 2 -> "Monday", 3 -> "Tuesday", 4 -> "Wednesday", 5 -> "Thursday", 6 -> "Friday" ) // TreeMap(2 -> Monday, 3 -> Tuesday, 4 -> Wednesday, 5 -> Thursday, 6 -> Friday) val days = weekdays ++ List(1 -> "Sunday", 7 -> "Saturday") // TreeMap(1 -> Sunday, 2 -> Monday, 3 -> Tuesday, 4 -> Wednesday, 5 -> Thursday, 6 -> Friday, 7 -> Saturday) val day3 = days.get(3) // Some("Tuesday") val rangeOfDays = days.range(2, 5) // TreeMap(2 -> Monday, 3 -> Tuesday, 4 -> Wednesday) val daysUntil2 = days.rangeUntil(2) // TreeMap(1 -> Sunday) val daysTo2 = days.rangeTo(2) // TreeMap(1 -> Sunday, 2 -> Monday) val daysAfter5 = days.rangeFrom(5) // TreeMap(5 -> Thursday, 6 -> Friday, 7 -> Saturday)
1
"Scala's Collection Library overview" section on Red-Black Trees
for more information.
This class implements an immutable map that preserves order using a hash map for the key to value mapping to provide efficient lookup, and a tree for the ordering of the keys to provide efficient insertion/modification order traversal and destructuring.
By default insertion order (TreeSeqMap.OrderBy.Insertion
) is used, but modification order (TreeSeqMap.OrderBy.Modification
) can be used instead if so specified at creation.
The orderingBy(orderBy: TreeSeqMap.OrderBy): TreeSeqMap[K, V]
method can be used to switch to the specified ordering for the returned map.
A key can be manually refreshed (i.e. placed at the end) via the refresh(key: K): TreeSeqMap[K, V]
method (regardless of the ordering in use).
Internally, an ordinal counter is increased for each insertion/modification and then the current ordinal is used as key in the tree map. After 232 insertions/modifications the entire map is copied (thus resetting the ordinal counter).
the type of the keys contained in this map.
the type of the values associated with the keys in this map.
2.13
2.13
This class implements immutable sorted sets using a tree.
the type of the elements contained in this tree set
1
"Scala's Collection Library overview" section on Red-Black Trees
for more information.
Vector is a general-purpose, immutable data structure. It provides random access and updates in effectively constant time, as well as very fast append and prepend. Because vectors strike a good balance between fast random selections and fast random functional updates, they are currently the default implementation of immutable indexed sequences. It is backed by a little endian bit-mapped vector trie with a branching factor of 32. Locality is very good, but not contiguous, which is good for very large sequences.
the element type
"Scala's Collection Library overview" section on Vectors
for more information.
A class to build instances of Vector
. This builder is reusable.
This class implements immutable maps using a vector/map-based data structure, which preserves insertion order.
Unlike ListMap
, VectorMap
has amortized effectively constant lookup at the expense of using extra memory and generally lower performance for other operations
the type of the keys contained in this vector map.
the type of the values associated with the keys in this vector map.
2.13
2.13
This class serves as a wrapper augmenting String
s with all the operations found in indexed sequences.
The difference between this class and StringOps
is that calling transformer methods such as filter
and map
will yield an object of type WrappedString
rather than a String
.
2.8
This object provides a set of operations to create ArraySeq
values.
This object provides a set of operations to create immutable.BitSet
values.
This object provides a set of operations to create immutable.HashMap
values.
This object provides a set of operations to create immutable.HashSet
values.
This object provides a set of operations to create LazyList
values.
This object provides a set of operations to create List
values.
This object provides a set of operations to create ListMap 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.
1
"Scala's Collection Library overview" section on List Maps
for more information.
This object provides a set of operations to create ListSet values.
Note that each element insertion takes O(n) time, which means that creating a list set with n elements will take O(n2) time. This makes the builder suitable only for a small number of elements.
1
This object provides a set of operations to create immutable.Map
values.
This object provides a set of operations to create immutable.Queue
values.
This object provides a set of operations to create immutable.Seq
values.
This object provides a set of operations to create immutable.Set
values.
This object provides a set of operations to create immutable.SortedSet
values.
This object provides a set of operations to create immutable.TreeMap values.
This object provides a set of operations to create immutable.TreeSet
values.
This object provides a set of operations to create Vector
values.
A companion object for wrapped strings.
2.8
© 2002-2019 EPFL, with contributions from Lightbend.
Licensed under the Apache License, Version 2.0.
https://www.scala-lang.org/api/2.13.0/scala/collection/immutable/index.html