Scala Standard Library2.12.5 < Back
 

# Packages

-  package root

  This is the documentation for the Scala standard library.

  This is the documentation for the Scala standard library.

  #### Package structure

  The scala package contains core types like `Int`, `Float`, `Array` or `Option` which are accessible in all Scala compilation units without explicit qualification or imports.

  Notable packages include:

  - `scala.collection` and its sub-packages contain Scala's collections framework
    - `scala.collection.immutable` - Immutable, sequential data-structures such as `Vector`, `List`, `Range`, `HashMap` or `HashSet`
    - `scala.collection.mutable` - Mutable, sequential data-structures such as `ArrayBuffer`, `StringBuilder`, `HashMap` or `HashSet`
    - `scala.collection.concurrent` - Mutable, concurrent data-structures such as `TrieMap`
    - `scala.collection.parallel.immutable` - Immutable, parallel data-structures such as `ParVector`, `ParRange`, `ParHashMap` or `ParHashSet`
    - `scala.collection.parallel.mutable` - Mutable, parallel data-structures such as `ParArray`, `ParHashMap`, `ParTrieMap` or `ParHashSet`
  - `scala.concurrent` - Primitives for concurrent programming such as `Futures` and `Promises`
  - `scala.io` - Input and output operations
  - `scala.math` - Basic math functions and additional numeric types like `BigInt` and `BigDecimal`
  - `scala.sys` - Interaction with other processes and the operating system
  - `scala.util.matching` - Regular expressions

  Other packages exist. See the complete list on the right.

  Additional parts of the standard library are shipped as separate libraries. These include:

  - `scala.reflect` - Scala's reflection API (scala-reflect.jar)
  - `scala.xml` - XML parsing, manipulation, and serialization (scala-xml.jar)
  - `scala.swing` - A convenient wrapper around Java's GUI framework called Swing (scala-swing.jar)
  - `scala.util.parsing` - Parser combinators (scala-parser-combinators.jar)

  #### Automatic imports

  Identifiers in the scala package and the `scala.Predef` object are always in scope by default.

  Some of these identifiers are type aliases provided as shortcuts to commonly used classes. For example, `List` is an alias for `scala.collection.immutable.List`.

  Other aliases refer to classes provided by the underlying platform. For example, on the JVM, `String` is an alias for `java.lang.String`.

  Definition Classes
    root
-  package scala

  Core Scala types.

  Core Scala types. They are always available without an explicit import.

  Definition Classes
    root
-  package collection

  Contains the base traits and objects needed to use and extend Scala's collection library.

  Contains the base traits and objects needed to use and extend Scala's collection library.

  #### Guide

  A detailed guide for using the collections library is available at http://docs.scala-lang.org/overviews/collections/introduction.html. Developers looking to extend the collections library can find a description of its architecture at http://docs.scala-lang.org/overviews/core/architecture-of-scala-collections.html.

  #### Using Collections

  It is convenient to treat all collections as either a scala.collection.Traversable or scala.collection.Iterable, as these traits define the vast majority of operations on a collection.

  Collections can, of course, be treated as specifically as needed, and the library is designed to ensure that the methods that transform collections will return a collection of the same type:

      scala> val array = Array(1,2,3,4,5,6)
      array: Array[Int] = Array(1, 2, 3, 4, 5, 6)

      scala> array map { _.toString }
      res0: Array[String] = Array(1, 2, 3, 4, 5, 6)

      scala> val list = List(1,2,3,4,5,6)
      list: List[Int] = List(1, 2, 3, 4, 5, 6)

      scala> list map { _.toString }
      res1: List[String] = List(1, 2, 3, 4, 5, 6)

  #### Creating Collections

  The most common way to create a collection is to use its companion object as a factory. The three most commonly used collections are scala.collection.Seq, scala.collection.immutable.Set, and scala.collection.immutable.Map. They can be used directly as shown below since their companion objects are all available as type aliases in either the scala package or in `scala.Predef`. New collections are created like this:

      scala> val seq = Seq(1,2,3,4,1)
      seq: Seq[Int] = List(1, 2, 3, 4, 1)

      scala> val set = Set(1,2,3,4,1)
      set: scala.collection.immutable.Set[Int] = Set(1, 2, 3, 4)

      scala> val map = Map(1 -> "one", 2 -> "two", 3 -> "three", 2 -> "too")
      map: scala.collection.immutable.Map[Int,String] = Map(1 -> one, 2 -> too, 3 -> three)

  It is also typical to prefer the scala.collection.immutable collections over those in scala.collection.mutable; the types aliased in the `scala.Predef` object are the immutable versions.

  Also note that the collections library was carefully designed to include several implementations of each of the three basic collection types. These implementations have specific performance characteristics which are described in the guide.

  The concrete parallel collections also have specific performance characteristics which are described in the parallel collections guide

  ##### Converting to and from Java Collections

  The scala.collection.JavaConverters object provides a collection of decorators that allow converting between Scala and Java collections using `asScala` and `asJava` methods.

  Definition Classes
    scala
-  package concurrent
  Definition Classes
    collection
-  package convert
  Definition Classes
    collection
-  package generic
  Definition Classes
    collection
-  package immutable
  Definition Classes
    collection
- ::
- AbstractMap
- BitSet
- DefaultMap
- HashMap
- HashSet
- IndexedSeq
- IntMap
- Iterable
- LinearSeq
- List
- ListMap
- ListSet
- LongMap
- Map
- MapLike
- MapProxy
- Nil
- NumericRange
- PagedSeq
- Queue
- Range
- Seq
- Set
- SetProxy
- SortedMap
- SortedSet
- Stack
- Stream
- StreamIterator
- StreamView
- StreamViewLike
- StringLike
- StringOps
- Traversable
- TreeMap
- TreeSet
- Vector
- VectorBuilder
- VectorIterator
- WrappedString
-  package mutable
  Definition Classes
    collection
-  package parallel

  Package object for parallel collections.

  Package object for parallel collections.

  Definition Classes
    collection
-  package script
  Definition Classes
    collection

p

scala.collection

# immutable 

#### package immutable

 
Ordering

1. Alphabetic

Visibility

1. Public
2. All

### Type Members

1.  final case class ::[B](head: B, tl: List[B]) extends List[B] with Product with Serializable

   A non empty list characterized by a head and a tail.

   A non empty list characterized by a head and a tail.

   B

     the type of the list elements.

   head

     the first element of the list

   tl

     the list containing the remaining elements of this list after the first one.

   Annotations
     @SerialVersionUID()
   Version

     1.0, 15/07/2003

   Since

     2.8

2.  abstract class AbstractMap[K, +V] extends collection.AbstractMap[K, V] with Map[K, V]

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

3.  abstract class BitSet extends AbstractSet[Int] with SortedSet[Int] with collection.BitSet with BitSetLike[BitSet] with 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 memory footprint of a bitset is determined by the largest number stored in it.

   Annotations
     @SerialVersionUID()
   See also

     Collection Library overview" section on `Immutable BitSets` for more information.

4.  trait DefaultMap[A, +B] extends Map[A, B]

   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.

   A

     the type of the keys contained in this map.

   B

     the type of the values associated with the keys.

   Since

     2.8

5.  sealed class HashMap[A, +B] extends AbstractMap[A, B] with Map[A, B] with MapLike[A, B, HashMap[A, B]] with Serializable with CustomParallelizable[(A, B), ParHashMap[A, B]]

   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.

   A

     the type of the keys contained in this hash map.

   B

     the type of the values associated with the keys.

   Annotations
     @SerialVersionUID()
   Version

     2.8

   Since

     2.3

   See also

     "Scala's Collection Library overview" section on `Hash Tries` for more information.

6.  sealed class HashSet[A] extends AbstractSet[A] with Set[A] with GenericSetTemplate[A, HashSet] with SetLike[A, HashSet[A]] with CustomParallelizable[A, ParHashSet[A]] with Serializable

   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.

   A

     the type of the elements contained in this hash set.

   Annotations
     @SerialVersionUID()
   Version

     2.8

   Since

     2.3

7.  trait IndexedSeq[+A] extends Seq[A] with collection.IndexedSeq[A] with GenericTraversableTemplate[A, IndexedSeq] with IndexedSeqLike[A, IndexedSeq[A]]

   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.

8.  sealed abstract class IntMap[+T] extends AbstractMap[immutable.IntMapUtils.Int, T] with Map[immutable.IntMapUtils.Int, T] with MapLike[immutable.IntMapUtils.Int, T, IntMap[T]]

   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.

   T

     type of the values associated with integer keys.

   Since

     2.7

9.  trait Iterable[+A] extends Traversable[A] with collection.Iterable[A] with GenericTraversableTemplate[A, Iterable] with IterableLike[A, Iterable[A]] with Parallelizable[A, ParIterable[A]]

   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.

10.  trait LinearSeq[+A] extends Seq[A] with collection.LinearSeq[A] with GenericTraversableTemplate[A, LinearSeq] with LinearSeqLike[A, LinearSeq[A]]

    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]]`.

11.  sealed abstract class List[+A] extends AbstractSeq[A] with LinearSeq[A] with Product with GenericTraversableTemplate[A, List] with LinearSeqOptimized[A, List[A]] with Serializable

    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`.

    Note: Despite being an immutable collection, the implementation uses mutable state internally during construction. These state changes are invisible in single-threaded code but can lead to race conditions in some multi-threaded scenarios. The state of a new collection instance may not have been "published" (in the sense of the Java Memory Model specification), so that an unsynchronized non-volatile read from another thread may observe the object in an invalid state (see scala/bug#7838 for details). Note that such a read is not guaranteed to ever see the written object at all, and should therefore not be used, regardless of this issue. The easiest workaround is to exchange values between threads through a volatile var.

    #### 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

    Annotations
      @SerialVersionUID()
    Example:

    1.     // 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.")
           }

    Version

      2.8

    Since

      1.0

    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.

    See also

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

12.  sealed class ListMap[A, +B] extends AbstractMap[A, B] with Map[A, B] with MapLike[A, B, ListMap[A, B]] with Serializable

    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 whey 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`.

    A

      the type of the keys contained in this list map

    B

      the type of the values associated with the keys

    Annotations
      @SerialVersionUID()
    Version

      2.0, 01/01/2007

    Since

      1

13.  sealed class ListSet[A] extends AbstractSet[A] with Set[A] with GenericSetTemplate[A, ListSet] with SetLike[A, ListSet[A]] with Serializable

    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 whey 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`.

    A

      the type of the elements contained in this list set

    Annotations
      @SerialVersionUID()
    Version

      1.0, 09/07/2003

    Since

      1

14.  sealed abstract class LongMap[+T] extends AbstractMap[immutable.LongMapUtils.Long, T] with Map[immutable.LongMapUtils.Long, T] with MapLike[immutable.LongMapUtils.Long, T, LongMap[T]]

    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.

    T

      type of the values associated with the long keys.

    Since

      2.7

15.  trait Map[K, +V] extends Iterable[(K, V)] with collection.Map[K, V] with MapLike[K, V, Map[K, V]]

    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: K): Option[V]
        def iterator: Iterator[(K, V)]
        def + [V1 >: V](kv: (K, V1)): Map[K, V1]
        def -(key: K): Map[K, V]

    Since

      1

16.  trait MapLike[K, +V, +This <: MapLike[K, V, This] with Map[K, V]] extends collection.MapLike[K, V, This] with Parallelizable[(K, V), ParMap[K, V]]

    A generic template for immutable maps from keys of type `K` to values of type `V`.

    A generic template for immutable maps from keys of type `K` to values of type `V`. 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: K): Option[V]
        def iterator: Iterator[(K, V)]
        def + [V1 >: V](kv: (K, V)): Map[K, V1]
        def - (key: K): 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.

    K

      the type of the keys contained in this collection.

    V

      the type of the values associated with the keys.

    This

      The type of the actual map implementation.

    Version

      2.8

    Since

      2.8

17.  abstract class NumericRange[T] extends AbstractSeq[T] with IndexedSeq[T] with Serializable

    `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))

    Version

      2.8

18.  sealed class Queue[+A] extends AbstractSeq[A] with LinearSeq[A] with GenericTraversableTemplate[A, Queue] with LinearSeqLike[A, Queue[A]] with Serializable

    `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 `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)`.

    Annotations
      @SerialVersionUID()
    Version

      1.0, 08/07/2003

    Since

      1

    See also

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

19.  sealed class Range extends AbstractSeq[Int] with IndexedSeq[Int] with CustomParallelizable[Int, ParRange] with Serializable

    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.

    Annotations
      @SerialVersionUID()
    Version

      2.8

    Since

      2.5

    See also

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

20.  trait Seq[+A] extends Iterable[A] with collection.Seq[A] with GenericTraversableTemplate[A, Seq] with SeqLike[A, Seq[A]] with Parallelizable[A, ParSeq[A]]

    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.

21.  trait Set[A] extends Iterable[A] with collection.Set[A] with GenericSetTemplate[A, Set] with SetLike[A, Set[A]] with Parallelizable[A, ParSet[A]]

    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.

    Since

      1.0

22.  trait SortedMap[A, +B] extends Map[A, B] with collection.SortedMap[A, B] with MapLike[A, B, SortedMap[A, B]] with SortedMapLike[A, B, SortedMap[A, B]]

    A map whose keys are sorted.

    A map whose keys are sorted.

    A

      the type of the keys contained in this sorted map.

    B

      the type of the values associated with the keys.

    Version

      2.8

    Since

      2.4

23.  trait SortedSet[A] extends Set[A] with collection.SortedSet[A] with SortedSetLike[A, SortedSet[A]]

    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.

    Version

      2.8

    Since

      2.4

24.  sealed abstract class Stream[+A] extends AbstractSeq[A] with LinearSeq[A] with GenericTraversableTemplate[A, Stream] with LinearSeqOptimized[A, Stream[A]] with Serializable

    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 {

          lazy 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 {

          lazy 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.

    - The definition of `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.
    - While the `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.
    - 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 `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.
    - 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 `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)

    - The fact that `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 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: 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 `?`.

    A

      the type of the elements contained in this stream.

    Version

      1.1 08/08/03

    Since

      2.8

    See also

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

25.  final class StreamIterator[+A] extends AbstractIterator[A] with Iterator[A]

    A specialized, extra-lazy implementation of a stream iterator, so it can iterate as lazily as it traverses the tail.

26.  trait StreamView[+A, +Coll] extends StreamViewLike[A, Coll, StreamView[A, Coll]]
27.  trait StreamViewLike[+A, +Coll, +This <: StreamView[A, Coll] with StreamViewLike[A, Coll, This]] extends SeqView[A, Coll] with SeqViewLike[A, Coll, This]
28.  trait StringLike[+Repr] extends IndexedSeqOptimized[Char, Repr] with Ordered[String]

    A trait describing stringlike collections.

    A trait describing stringlike collections.

    Repr

      The type of the actual collection inheriting `StringLike`.

    Since

      2.8

29.  final class StringOps extends AnyVal with StringLike[String]

    This class serves as a wrapper providing scala.Predef.Strings with all the operations found in indexed sequences.

    This class serves as a wrapper providing scala.Predef.Strings with all the operations found in indexed sequences. Where needed, `String`s are implicitly converted into instances of 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`.

    Since

      2.8

30.  trait Traversable[+A] extends collection.Traversable[A] with GenericTraversableTemplate[A, Traversable] with TraversableLike[A, Traversable[A]] with Immutable

    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`.

31.  final class TreeMap[A, +B] extends SortedMap[A, B] with SortedMapLike[A, B, TreeMap[A, B]] with MapLike[A, B, TreeMap[A, B]] with Serializable

    This class implements immutable maps using a tree.

    This class implements immutable maps using a tree.

    A

      the type of the keys contained in this tree map.

    B

      the type of the values associated with the keys.

    Version

      1.1, 03/05/2004

    Since

      1

    See also

      "Scala's Collection Library overview" section on `Red-Black Trees` for more information.

32.  final class TreeSet[A] extends SortedSet[A] with SortedSetLike[A, TreeSet[A]] with Serializable

    This class implements immutable sets using a tree.

    This class implements immutable sets using a tree.

    A

      the type of the elements contained in this tree set

    Annotations
      @SerialVersionUID()
    Version

      2.0, 02/01/2007

    Since

      1

    See also

      "Scala's Collection Library overview" section on `Red-Black Trees` for more information.

33.  final class Vector[+A] extends AbstractSeq[A] with IndexedSeq[A] with GenericTraversableTemplate[A, Vector] with IndexedSeqLike[A, Vector[A]] with VectorPointer[A] with Serializable with CustomParallelizable[A, ParVector[A]]

    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.

    Note: Despite being an immutable collection, the implementation uses mutable state internally during construction. These state changes are invisible in single-threaded code but can lead to race conditions in some multi-threaded scenarios. The state of a new collection instance may not have been "published" (in the sense of the Java Memory Model specification), so that an unsynchronized non-volatile read from another thread may observe the object in an invalid state (see scala/bug#7838 for details). Note that such a read is not guaranteed to ever see the written object at all, and should therefore not be used, regardless of this issue. The easiest workaround is to exchange values between threads through a volatile var.

    A

      the element type

    Annotations
      @SerialVersionUID()
    See also

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

34.  final class VectorBuilder[A] extends ReusableBuilder[A, Vector[A]] with VectorPointer[A]

    A class to build instances of `Vector`.

    A class to build instances of `Vector`. This builder is reusable.

35.  class VectorIterator[+A] extends AbstractIterator[A] with Iterator[A] with VectorPointer[A]
36.  final class WrappedString extends AbstractSeq[Char] with IndexedSeq[Char] with StringLike[WrappedString]

    This class serves as a wrapper augmenting `String`s with all the operations found in indexed sequences.

    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`.

    Since

      2.8

37.  trait MapProxy[A, +B] extends Map[A, B] with MapProxyLike[A, B, Map[A, B]]

    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.

    Annotations
      @deprecated
    Deprecated

      (Since version 2.11.0) proxying is deprecated due to lack of use and compiler-level support

    Version

      2.0, 31/12/2006

    Since

      2.8

38.  class PagedSeq[T] extends AbstractSeq[T] with collection.IndexedSeq[T]

    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.

    T

      the type of the elements contained in this paged sequence, with an `ClassTag` context bound.

    Annotations
      @deprecated
    Deprecated

      (Since version 2.11.8) this class will be moved to the scala-parser-combinators module

    Since

      2.7

39.  trait SetProxy[A] extends Set[A] with SetProxyLike[A, Set[A]]

    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.

    A

      type of the elements contained in this set proxy.

    Annotations
      @deprecated
    Deprecated

      (Since version 2.11.0) proxying is deprecated due to lack of use and compiler-level support.

    Since

      2.8

40.  class Stack[+A] extends AbstractSeq[A] with LinearSeq[A] with GenericTraversableTemplate[A, Stack] with LinearSeqOptimized[A, Stack[A]] with Serializable

    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.

    A

      the type of the elements contained in this stack.

    Annotations
      @SerialVersionUID() @deprecated
    Deprecated

      (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.

    Version

      1.0, 10/07/2003

    Since

      1

    See also

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

### Value Members

1.  object BitSet extends BitSetFactory[BitSet] with Serializable

   This object provides a set of operations to create ``immutable.BitSet`` values.

2.  object HashMap extends ImmutableMapFactory[HashMap] with generic.BitOperations.Int with Serializable

   This object provides a set of operations needed to create ``immutable.HashMap`` values.

3.  object HashSet extends ImmutableSetFactory[HashSet] with Serializable

   This object provides a set of operations needed to create ``immutable.HashSet`` values.

4.  object IndexedSeq extends IndexedSeqFactory[IndexedSeq]

   This object provides a set of operations to create ``IndexedSeq`` values.

   This object provides a set of operations to create ``IndexedSeq`` values. The current default implementation of a `IndexedSeq` is a `Vector`.

5.  object IntMap

   A companion object for integer maps.

6.  object Iterable extends GenTraversableFactory[Iterable] with TraversableFactory[Iterable]

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

   This object provides a set of operations to create ``immutable.Iterable`` values. The current default implementation of a `immutable.Iterable` is a `List`.

7.  object LinearSeq extends SeqFactory[LinearSeq]

   This object provides a set of operations to create ``immutable.LinearSeq`` values.

   This object provides a set of operations to create ``immutable.LinearSeq`` values. The current default implementation of a `immutable.LinearSeq` is a `List`.

8.  object List extends SeqFactory[List] with Serializable

   This object provides a set of operations to create ``List`` values.

9.  object ListMap extends ImmutableMapFactory[ListMap] with Serializable

   This object provides a set of operations needed to create `ListMap` values.

   This object provides a set of operations needed 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.

   Since

     1

   See also

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

10.  object ListSet extends ImmutableSetFactory[ListSet] with Serializable

    This object provides a set of operations needed to create `ListSet` values.

    This object provides a set of operations needed 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.

    Since

      1

11.  object LongMap

    A companion object for long maps.

12.  object Map extends ImmutableMapFactory[Map]

    This object provides a set of operations needed to create ``immutable.Map`` values.

13.  object Nil extends List[Nothing] with Product with Serializable

    The empty list.

    The empty list.

    Annotations
      @SerialVersionUID()
    Version

      1.0, 15/07/2003

    Since

      2.8

14.  object NumericRange extends Serializable

    A companion object for numeric ranges.

15.  object Queue extends SeqFactory[Queue] with Serializable

    This object provides a set of operations to create ``immutable.Queue`` values.

16.  object Range extends Serializable

    A companion object for the `Range` class.

17.  object Seq extends SeqFactory[Seq]

    This object provides a set of operations to create ``immutable.Seq`` values.

18.  object Set extends ImmutableSetFactory[Set]

    This object provides a set of operations needed to create ``immutable.Set`` values.

19.  object SortedMap extends ImmutableSortedMapFactory[SortedMap]

    This object provides a set of operations needed to create sorted maps of type `immutable.SortedMap`.

20.  object SortedSet extends ImmutableSortedSetFactory[SortedSet]

    This object provides a set of operations needed to create sorted sets of type ``immutable.SortedSet``.

21.  object Stack extends SeqFactory[Stack] with Serializable

    This object provides a set of operations to create ``immutable.Stack`` values.

22.  object Stream extends SeqFactory[Stream] with Serializable

    The object `Stream` provides helper functions to manipulate streams.

    The object `Stream` provides helper functions to manipulate streams.

    Version

      1.1 08/08/03

    Since

      2.8

23.  object StringLike

    A companion object for the `StringLike` containing some constants.

    A companion object for the `StringLike` containing some constants.

    Since

      2.8

24.  object Traversable extends GenTraversableFactory[Traversable] with TraversableFactory[Traversable]

    This object provides a set of operations to create ``immutable.Traversable`` values.

    This object provides a set of operations to create ``immutable.Traversable`` values. The current default implementation of a `immutable.Traversable` is a `List`.

25.  object TreeMap extends ImmutableSortedMapFactory[TreeMap] with Serializable

    This object provides a set of operations needed to create sorted maps of type `immutable.TreeMap`.

26.  object TreeSet extends ImmutableSortedSetFactory[TreeSet] with Serializable

    This object provides a set of operations needed to create sorted sets of type ``immutable.TreeSet``.

27.  object Vector extends IndexedSeqFactory[Vector] with Serializable

    Companion object to the Vector class

28.  object WrappedString

    A companion object for wrapped strings.

    A companion object for wrapped strings.

    Since

      2.8

### Deprecated Value Members

1.  object PagedSeq

   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`

   Annotations
     @deprecated
   Deprecated

     (Since version 2.11.8) this object will be moved to the scala-parser-combinators module

   Since

     2.7

### Ungrouped