Uncategorized

# Lists

Lists are quite similar to arrays, but there are two important differences. First, lists are immutable. That is, elements of a list cannot be changed by assignment. Second, lists have a recursive structure (i.e., a linked list), whereas arrays are flat.
Example of Lists with explicit types added:
```val fruits: List[String] = List("Apple", "Orange")
val empty: List[Nothing] = List()```
Nothing is subtype of every other Scala type. So it’s possible to write this:
`val empty: List[String] = List()`
All operations on lists can be expressed in terms of the following three:
• head returns the first element of a list
• tail returns a list consisting of all elements except the first
• isEmpty returns true if the list is empty
Pattern matching on lists
```val List(apple, orange, banana) = fruits

//if you don’t know the length of the list:
val a :: b :: rest = fruits
List(...) is an instance of a library-defined extractor pattern.```
First-order methods on class List
A method is first-order if it does not take any functions as arguments.
Concatenating two lists
`List(1, 2) ::: List(3, 4, 5)`
Accessing the end of a list: init and last
• last returns last element of List
• init returns all elements, except the last one
Unlike head and tail, which both run in constant time, init and last need to traverse the whole list to compute their result. They therefore take time proportional to the length of the list.
Prefixes and suffixes: drop, take, and splitAt

```scala> abcde take 2
res8: List[Char] = List(a, b)

scala> abcde drop 2
res9: List[Char] = List(c, d, e)

scala> abcde splitAt 2
res10: (List[Char], List[Char]) = (List(a, b),List(c, d, e))```
Element selection: apply and indices
```scala> abcde apply 2 // rare in Scala, same as abcde(2)
res11: Char = c

scala> abcde.indices
res13: scala.collection.immutable.Range = Range(0, 1, 2, 3, 4)```
Element selection is less popular for lists than for arrays because xs(n) takes time proportional to the index n.
Flattening a list of lists: flatten
The flatten method takes a list of lists and flattens it out to a single list:
```scala> List(List(1, 2), List(3), List(), List(4, 5)).flatten
res14: List[Int] = List(1, 2, 3, 4, 5)```
It can only be applied to lists whose elements are all lists. Trying to flatten any other list will give a compilation error.
Zipping lists: zip and unzip
The zip operation takes two lists and forms a list of pairs:
```scala> abcde.indices zip abcde
res17: scala.collection.immutable.IndexedSeq[(Int, Char)] =
IndexedSeq((0,a), (1,b), (2,c), (3,d), (4,e))```
If the two lists are of different length, any unmatched elements are dropped.
Any list of tuples can also be changed back to a tuple of lists by using the unzip method:
```scala> zipped.unzip
res19: (List[Char], List[Int]) = (List(a, b, c),List(1, 2, 3))```
Displaying lists: toString and mkString
The toString operation returns the canonical string representation of a list.
If you want a different representation you can use themkStringmethod. The operationxs mkString (pre, sep, post)involves four operands: the listxsto be displayed, a prefix stringpreto be displayed in front of all elements, a separator stringsepto be displayed between successive elements, and a postfix stringpostto be displayed at the end. The result of the operation is the string
Converting lists: iterator, toArray, copyToArray
To convert data between the flat world of arrays and the recursive world of lists, you can use method toArray in class List and toList in class Array.

Higher-order methods on class List

Mapping over lists: map, flatMap and foreach
The operation xs map f takes as operands a list xs of type List[T] and a function f of type T => U. It returns the list resulting from applying the function f to each list element in xs. For instance:
```scala> List(1, 2, 3) map (_ + 1)
res32: List[Int] = List(2, 3, 4)

scala> val words = List("the", "quick", "brown", "fox")
words: List[java.lang.String] = List(the, quick, brown, fox)

scala> words map (_.length)
res33: List[Int] = List(3, 5, 5, 3)

scala> words map (_.toList.reverse.mkString)
res34: List[String] = List(eht, kciuq, nworb, xof)```
The flatMap operator is similar to map, but it takes a function returning a list of elements as its right operand. Wheremapreturns a list of lists,flatMapreturns a single list in which all element lists are concatenated.
Unlike map and flatMap, foreach takes a procedure (a function with result type Unit) as right operand. It simply applies the procedure to each list element. The result of the operation itself is again Unit; no list of results is assembled.
```scala> var sum = 0
sum: Int = 0

scala> List(1, 2, 3, 4, 5) foreach (sum += _)

scala> sum
res39: Int = 15```
Filtering lists: filter, partition, find, takeWhile, dropWhile, and span
The operation “xs filter p” takes as operands a list xs of type List[T] and a predicate function p of type T => Boolean. It yields the list of all elements x in xs for which p(x) is true. For instance:
`scala> List(1, 2, 3, 4, 5) filter (_ % 2 == 0) res40: List[Int] = List(2, 4)`
```scala> words filter (_.length == 3)
res41: List[java.lang.String] = List(the, fox)```
The partition method is like filter, but it returns a pair of lists. One list contains all elements for which the predicate is true, while the other list contains all elements for which the predicate is false.
The find method is also similar to filter but it returns the first element satisfying a given predicate, rather than all such elements. It returns an optional value (Some/None).
The takeWhile and dropWhile operators also take a predicate as their right operand. The operation xs takeWhile p takes the longest prefix of list xs such that every element in the prefix satisfies p. Analogously, the operation xs dropWhile p removes the longest prefix from list xs such that every element in the prefix satisfies p. Here are some examples:
```scala> List(1, 2, 3, -4, 5) takeWhile (_ > 0)
res45: List[Int] = List(1, 2, 3)

scala> words dropWhile (_ startsWith "t")
res46: List[java.lang.String] = List(quick, brown, fox)```
The span method combines takeWhile and dropWhile in one operation, just like splitAt combines take and drop. It returns a pair of two lists, defined by the equality.
```scala> List(1, 2, 3, -4, 5) span (_ > 0)
res47: (List[Int], List[Int]) = (List(1, 2, 3),List(-4, 5))```
Predicates over lists: forall and exists
The operation xs forall p takes as arguments a list xs and a predicate p. Its result is true if all elements in the list satisfy p. Conversely, the operation xs exists p returns true if there is an element in xs that satisfies the predicate p.
```val variedNumList: List[Int] = List(1, 2, 3, -4, -5)
variedNumList forall(_ > 3) //returns false
variedNumList exists(_ < 3) //returns true```
Folding lists: /: and Another common kind of operation combines the elements of a list with some operator.
```scala> def sum(xs: List[Int]): Int = (0 /: xs) (_ + _)
sum: (xs: List[Int])Int```
A fold left operation “(z /: xs) (op)” involves three objects: a start value z, a list xs, and a binary operation op. The result of the fold is op applied between successive elements of the list prefixed by z.
To concatenate all words in a list of strings with spaces between them and in front, you can write this:
```scala>  ("" /: words) (_ +" "+ _)
res49: java.lang.String =  the quick brown fox```
Sorting lists: sortWith
The operation xs sortWith before, where “xs” is a list and “before” is a function that can be used to compare two elements, sorts the elements of list xs. The expression x before y should return true if x should come before y in the intended ordering for the sort. For instance:
```scala> List(1, -3, 4, 2, 6) sortWith (_ < _)
res51: List[Int] = List(-3, 1, 2, 4, 6)

scala> words sortWith (_.length > _.length)
res52: List[java.lang.String] = List(quick, brown, the, fox)```
Methods of the List object
The following are methods available on the List companion object.
Creating a range of numbers: List.range
This creates a list that includes a range of numbers. It’s possible to supply a third parameter, as a “step”. For example:
```scala> List.range(1, 5)
res54: List[Int] = List(1, 2, 3, 4)

scala> List.range(1, 9, 2)
res55: List[Int] = List(1, 3, 5, 7)

scala> List.range(9, 1, -3)
res56: List[Int] = List(9, 6, 3)```
Creating uniform lists: List.fill
The fill method creates a list consisting of zero or more copies of the same element. It takes two parameters: the length of the list to be created, and the element to be repeated. Iffillis given more than two arguments, then it will make multi- dimensional lists.
```scala> List.fill(5)('a')
res57: List[Char] = List(a, a, a, a, a)

scala> List.fill(2, 3)('b')
res59: List[List[Char]] = List(List(b, b, b), List(b, b, b))```
Tabulating a function: List.tabulate

The tabulate method creates a list whose elements are computed according to a supplied function. Its arguments are just like those of List.fill:
```scala> val squares = List.tabulate(5)(n => n * n)
squares: List[Int] = List(0, 1, 4, 9, 16)```
Concatenating multiple lists: List.concat
The concat method concatenates a number of element lists. The lists to be  concatenated are supplied as direct arguments to concat:
```scala> List.concat(List('a', 'b'), List('c'))
res60: List[Char] = List(a, b, c)```
Processing multiple lists together
Thezippedmethod on tuples generalizes several common operations to work on multiple lists instead of just one. One such operation ismap. Themapmethod for two zipped lists maps pairs of elements rather than individ- ual elements.
```scala> (List(10, 20), List(3, 4, 5)).zipped.map(_ * _)
res63: List[Int] = List(30, 80)```
There are also zipped analogs toexistsandforall. They are just like the single-list versions of those methods except they operate on elements from multiple lists instead of just one:
```scala> (List("abc", "de"), List(3, 2)).zipped.forall(_.length == _)
res64: Boolean = true

scala> (List("abc", "de"), List(3, 2)).zipped.exists(_.length != _)
res65: Boolean = false```