immutable
A non empty list characterized by a head and a tail.
Explicit instantiation of the Map trait to reduce class file size in subclasses.
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 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.
A default map which implements the + and -
methods of maps.
A default map which implements the + and -
methods of maps. It does so using the default builder for
maps defined in the Map object.
Instances that inherit from DefaultMap[A, B] still have to
define:
def get(key: A): Option[B] def iterator: Iterator[(A, B)]
It refers back to the original map.
It might also be advisable to override foreach or
size if efficient implementations can be found.
the type of the keys contained in this map.
the type of the values associated with the keys.
2.8
This class implements immutable maps using a hash trie.
This class implements immutable maps using a hash trie.
Note: The builder of this hash map may return specialized representations for small maps.
the type of the keys contained in this hash map.
the type of the values associated with the keys.
2.8
2.3
"Scala's Collection Library overview"
section on Hash Tries for more information.
This class implements immutable sets using a hash trie.
This class implements immutable sets using a hash trie.
Note: The builder of this hash set may return specialized representations for small sets.
the type of the elements contained in this hash set.
2.8
2.3
A subtrait of collection.IndexedSeq which represents indexed sequences
that are guaranteed immutable.
A subtrait of collection.IndexedSeq which represents indexed sequences
that are guaranteed immutable.
Indexed sequences support constant-time or near constant-time element
access and length computation. They are defined in terms of abstract methods
apply for indexing and length.
Indexed sequences do not add any new methods to Seq, but promise
efficient implementations of random access patterns.
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 of the values associated with integer keys.
2.7
A base trait for iterable collections that are guaranteed immutable.
A base trait for iterable collections that are guaranteed immutable.
This is a base trait for all immutable Scala collections that define an iterator
method to step through one-by-one the collection's elements.
Implementations of this trait need to provide a concrete method with
signature:
def iterator: Iterator[A] They also need to provide a method newBuilder
which creates a builder for collections of the same kind.
This trait implements Iterable's foreach
method by stepping through all elements using iterator.
Subclasses should re-implement foreach with something more efficient,
if possible.
This trait adds methods iterator, sameElements,
takeRight, dropRight to the methods inherited
from trait
`Traversable`.
Note: This trait replaces every method that uses break in
TraversableLike by an iterator version.
A subtrait of collection.LinearSeq which represents sequences that
are guaranteed immutable.
A subtrait of collection.LinearSeq which represents sequences that
are guaranteed immutable.
Linear sequences have reasonably efficient head, tail, and isEmpty methods.
If these methods provide the fastest way to traverse the collection, a
collection Coll that extends this trait should also extend
LinearSeqOptimized[A, Coll[A]].
A class for immutable linked lists representing ordered collections of elements of type.
A class for immutable linked lists representing ordered collections of elements of type.
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.
// 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" :: List() // Pattern match days match { case firstDay :: otherDays => println("The first day of the week is: " + firstDay) case List() => println("There don't seem to be any week days.") }
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
2.8
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.
This class implements immutable maps using a list-based data structure.
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 in this list map.
the type of the values associated with the keys.
2.0, 01/01/2007
1
This class implements immutable sets using a list-based data structure.
This class implements immutable sets using a list-based data
structure. 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.0, 09/07/2003
1
Specialised immutable map structure for long keys, based on Fast Mergeable Long Maps by Okasaki and Gill.
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
A generic trait for immutable maps.
A generic trait for immutable maps. Concrete classes have to provide
functionality for the abstract methods in Map:
def get(key: A): Option[B] def iterator: Iterator[(A, B)] def + [B1 >: B](kv: (A, B1)): Map[A, B1] def -(key: A): Map[A, B]
1
A generic template for immutable maps from keys of type A
to values of type B.
A generic template for immutable maps from keys of type A
to values of type B.
To implement a concrete map, you need to provide implementations of the
following methods (where This is the type of the actual map implementation):
def get(key: A): Option[B] def iterator: Iterator[(A, B)] def + [B1 >: B](kv: (A, B)): Map[A, B1] def - (key: A): This
If you wish that transformer methods like take, drop, filter return the
same kind of map, you should also override:
def empty: This It is also good idea to override methods foreach and
size for efficiency.
the type of the keys contained in this collection.
the type of the values associated with the keys.
The type of the actual map implementation.
2.8
2.8
NumericRange is a more generic version of the
Range class which works with arbitrary types.
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 = new Range(0, 100, 1) val veryBig = Int.MaxValue.toLong + 1 val r2 = Range.Long(veryBig, veryBig + 100, 1) assert(r1 sameElements r2.map(_ - veryBig))
TODO: Now the specialization exists there is no clear reason to have separate classes for Range/NumericRange. Investigate and consolidate.
2.8
An implementation of lazily computed sequences, where elements are stored in "pages", i.e.
An implementation of lazily computed sequences, where elements are stored in "pages", i.e. arrays of fixed size.
A paged sequence is constructed from a function that produces more elements when asked.
The producer function - more, is similar to the read method in java.io.Reader.
The more function takes three parameters: an array of elements, a start index, and an end index.
It should try to fill the array between start and end indices (excluding end index).
It returns the number of elements produced, or -1 if end of logical input stream was reached
before reading any element.
the type of the elements contained in this paged sequence, with an ClassTag context bound.
2.7
Queue objects implement data structures that allow to
insert and retrieve elements in a first-in-first-out (FIFO) manner.
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 Lists, 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.0, 08/07/2003
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.
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.
2.8
2.5
"Scala's Collection Library overview"
section on Ranges for more information.
A subtrait of collection.Seq which represents sequences
that are guaranteed immutable.
A subtrait of collection.Seq which represents sequences
that are guaranteed immutable.
Sequences are special cases of iterable collections of class Iterable.
Unlike iterables, sequences always have a defined order of elements.
Sequences provide a method apply for indexing. Indices range from 0 up to the length of
a sequence. Sequences support a number of methods to find occurrences of elements or subsequences, including
segmentLength, prefixLength, indexWhere, indexOf, lastIndexWhere, lastIndexOf,
startsWith, endsWith, indexOfSlice.
Another way to see a sequence is as a PartialFunction from Int values
to the element type of the sequence. The isDefinedAt method of a sequence
returns true for the interval from 0 until length.
Sequences can be accessed in reverse order of their elements, using methods
reverse and reverseIterator.
Sequences have two principal subtraits, IndexedSeq and LinearSeq, which give different guarantees for performance.
An IndexedSeq provides fast random-access of elements and a fast length operation.
A LinearSeq provides fast access only to the first element via head, but also
has a fast tail operation.
A generic trait for immutable sets.
A generic trait for immutable sets.
A set is a collection that contains no duplicate elements.
To implement a concrete set, you need to provide implementations of the following methods:
def contains(key: A): Boolean def iterator: Iterator[A] def +(elem: A): This def -(elem: A): This
If you wish that methods like take, drop,
filter return the same kind of set, you should also override:
def empty: This It is also good idea to override methods foreach and
size for efficiency.
1.0
A map whose keys are sorted.
A map whose keys are sorted.
the type of the keys contained in this sorted map.
the type of the values associated with the keys.
2.8
2.4
A subtrait of collection.SortedSet which represents sorted sets
which cannot be mutated.
A subtrait of collection.SortedSet which represents sorted sets
which cannot be mutated.
2.8
2.4
The class Stream implements lazy lists where elements
are only evaluated when they are needed.
The class Stream implements lazy lists where elements
are only evaluated when they are needed. Here is an example:
import scala.math.BigInt object Main extends App { val fibs: Stream[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
The Stream class also employs memoization such that previously computed
values are converted from Stream elements to concrete values of type A.
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: Stream[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
Stream requires us to have somewhere to store the information and a val
allows us to do that.Stream 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.Stream 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 Stream) then once it is no longer being used directly,
it disappears.Stream, and a stream 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 Stream definition will be a val definition val stream1: Stream[Int] = { def loop(v: Int): Stream[Int] = v #:: loop(v + 1) loop(0) } // Because stream1 is a val, everything that the iterator produces is held // by virtue of the fact that the head of the Stream is held in stream1 val it1 = stream1.iterator loop("Iterator1: ", it1.next, it1) // We can redefine this Stream such that all we have is the Iterator left // and allow the Stream to be garbage collected as required. Using a def // to provide the Stream ensures that no val is holding onto the head as // is the case with stream1 def stream2: Stream[Int] = { def loop(v: Int): Stream[Int] = v #:: loop(v + 1) loop(0) } val it2 = stream2.iterator loop("Iterator2: ", it2.next, it2) // And, of course, we don't actually need a Stream at all for such a simple // problem. There's no reason to use a Stream 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, Stream(...)) so tail is deterministic.
If we deinfed 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... val sov: Stream[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: Stream[Int] = { def loop(h: Int, n: Int): Stream[Int] = h #:: loop(n, h + n) loop(1, 1) }
Note that mkString forces evaluation of a Stream, but addString does
not. In both cases, a Stream that is or ends in a cycle
(e.g. lazy val s: Stream[Int] = 0 #:: s) will convert additional trips
through the cycle to .... Additionally, addString will display an
un-memoized tail as ?.
the type of the elements contained in this stream.
1.1 08/08/03
2.8
"Scala's Collection Library overview"
section on Streams for more information.
A specialized, extra-lazy implementation of a stream iterator, so it can iterate as lazily as it traverses the tail.
A trait describing stringlike collections.
A trait describing stringlike collections.
The type of the actual collection inheriting StringLike.
2.8
This class serves as a wrapper providing Strings with all the operations
found in indexed sequences.
This class serves as a wrapper providing Strings with all the operations
found in indexed sequences. Where needed, instances of String object
are implicitly converted into this class.
The difference between this class and WrappedString is that calling transformer
methods such as filter and map will yield a String object, whereas a
WrappedString will remain a WrappedString.
2.8
A trait for traversable collections that are guaranteed immutable.
A trait for traversable collections that are guaranteed immutable.
This is a base trait of all kinds of immutable Scala collections. It
implements the behavior common to all collections, in terms of a method
foreach with signature:
def foreach[U](f: Elem => U): Unit
Collection classes mixing in this trait provide a concrete
foreach method which traverses all the
elements contained in the collection, applying a given function to each.
They also need to provide a method newBuilder
which creates a builder for collections of the same kind.
A traversable class might or might not have two properties: strictness and orderedness. Neither is represented as a type.
The instances of a strict collection class have all their elements
computed before they can be used as values. By contrast, instances of
a non-strict collection class may defer computation of some of their
elements until after the instance is available as a value.
A typical example of a non-strict collection class is a
scala.collection.immutable.Stream.
A more general class of examples are TraversableViews.
If a collection is an instance of an ordered collection class, traversing
its elements with foreach will always visit elements in the
same order, even for different runs of the program. If the class is not
ordered, foreach can visit elements in different orders for
different runs (but it will keep the same order in the same run).'
A typical example of a collection class which is not ordered is a
HashMap of objects. The traversal order for hash maps will
depend on the hash codes of its elements, and these hash codes might
differ from one run to the next. By contrast, a LinkedHashMap
is ordered because its foreach method visits elements in the
order they were inserted into the HashMap.
This class implements immutable maps using a tree.
This class implements immutable maps using a tree.
the type of the keys contained in this tree map.
the type of the values associated with the keys.
1.1, 03/05/2004
1
"Scala's Collection Library overview"
section on Red-Black Trees for more information.
This class implements immutable sets using a tree.
This class implements immutable sets using a tree.
the type of the elements contained in this tree set
2.0, 02/01/2007
1
"Scala's Collection Library overview"
section on Red-Black Trees for more information.
Vector is a general-purpose, immutable data structure.
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.
This class serves as a wrapper augmenting Strings with all the operations
found in indexed sequences.
This class serves as a wrapper augmenting Strings 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 is a simple wrapper class for `scala.collection.immutable.Map`.
This is a simple wrapper class for `scala.collection.immutable.Map`.
It is most useful for assembling customized map abstractions dynamically using object composition and forwarding.
(Since version 2.11.0) Proxying is deprecated due to lack of use and compiler-level support.
2.0, 31/12/2006
2.8
This is a simple wrapper class for `scala.collection.immutable.Set`.
This is a simple wrapper class for `scala.collection.immutable.Set`.
It is most useful for assembling customized set abstractions dynamically using object composition and forwarding.
type of the elements contained in this set proxy.
(Since version 2.11.0) Proxying is deprecated due to lack of use and compiler-level support.
2.8
This class implements immutable stacks using a list-based data structure.
This class implements immutable stacks using a list-based data structure.
Note: This class exists only for historical reason and as an analogue of mutable stacks. Instead of an immutable stack you can just use a list.
the type of the elements contained in this stack.
(Since version 2.11.0) Stack is an inelegant and potentially poorly-performing wrapper around List. Use List instead: stack push x becomes x :: list; stack.pop is list.tail.
1.0, 10/07/2003
1
"Scala's Collection Library overview"
section on Immutable stacks for more information.
This object provides a set of operations to create immutable.BitSet
This object provides a set of operations needed to create immutable.HashMap
This object provides a set of operations needed to create immutable.HashSet
This object provides a set of operations to create IndexedSeq
This object provides a set of operations to create IndexedSeqIndexedSeq is a Vector.
A companion object for integer maps.
This object provides a set of operations to create immutable.Iterable
This object provides a set of operations to create immutable.Iterableimmutable.Iterable is a List.
This object provides a set of operations to create immutable.LinearSeq
This object provides a set of operations to create immutable.LinearSeqimmutable.LinearSeq is a List.
This object provides a set of operations to create List
This object provides a set of operations needed to create immutable.ListMap values.
This object provides a set of operations needed to create immutable.ListMap values.
1
"Scala's Collection Library overview"
section on List Maps for more information.
This object provides a set of operations needed to create immutable.ListSet values.
A companion object for long maps.
This object provides a set of operations needed to create immutable.Map
The empty list.
The empty list.
1.0, 15/07/2003
2.8
A companion object for numeric ranges.
The PagedSeq object defines a lazy implementations of
a random access sequence.
The PagedSeq object defines a lazy implementations of
a random access sequence.
Provides utility methods that return instances of PagedSeq[Char].
fromIterator and fromIterable provide generalised instances of PagedSeq
2.7
This object provides a set of operations to create immutable.Queue
A companion object for the Range class.
This object provides a set of operations to create immutable.Seq
This object provides a set of operations needed to create immutable.Set
This object provides a set of operations needed to create sorted maps of type immutable.SortedMap.
This object provides a set of operations needed to create sorted sets of type immutable.SortedSet
This object provides a set of operations to create immutable.Stack
The object Stream provides helper functions to manipulate streams.
The object Stream provides helper functions to manipulate streams.
1.1 08/08/03
2.8
A companion object for the StringLike containing some constants.
A companion object for the StringLike containing some constants.
2.8
This object provides a set of operations to create immutable.Traversable
This object provides a set of operations to create immutable.Traversableimmutable.Traversable is a List.
This object provides a set of operations needed to create sorted maps of type immutable.TreeMap.
This object provides a set of operations needed to create sorted sets of type immutable.TreeSet
Companion object to the Vector class
A companion object for wrapped strings.
A companion object for wrapped strings.
2.8
A non empty list characterized by a head and a tail.
the type of the list elements.
the first element of the list
the list containing the remaining elements of this list after the first one.
1.0, 15/07/2003
2.8