About

:octocat: GitHub: All of the example code: repo (link)

:page_facing_up: blog link: https://purrgramming.life/cs/programming/fp/ :star:

---

Intro

List

A Scala immutable List is a linked sequence. Operations return a list value rather than mutating the original. They can share existing nodes: x :: xs adds one head and reuses xs as its tail; xs.tail can return an already existing tail. Appending or other edits may copy a prefix. An immutable list does not make mutable objects stored inside it immutable.

Original schematic created for these notes.

List vs Array

Mutability

Lists are immutable — the elements of a list cannot be changed.
Arrays are mutable – the immutable analogue of Array is IndexedSeq

Lists are recursive, while arrays are flat.

Creating Lists

Initial List

This is how you create an initial List:

val ints = List(1, 2, 3)
val names = List("Joel", "Chris", "Ed")

You can also declare the List’s type, if you prefer, though it generally isn’t necessary:

val ints: List[Int] = List(1, 2, 3)
val names: List[String] = List("Joel", "Chris", "Ed")

Results

val ints: List[Int] = List(1, 2, 3)
val names: List[String] = List(Joel, Chris, Ed)

List Constructers

All lists are constructed from:

• the empty list Nil, and
• the construction operation :: (pronounced cons)

x :: xs gives a new list with the first element x, followed by the elements of xs.

val fruit2 = "apples" :: ("oranges" :: ("pears" :: Nil))  
val nums2 = 1 :: (2 :: (3 :: (4 :: Nil)))  
val empty2 = Nil

Right Associativity

Convention: Operators ending in : associate to the right.

A :: B :: C is interpreted as A :: (B :: C).

We can thus omit the parentheses in the definition above.

Example

val nums = 1 :: 2 :: 3 :: 4 :: Nil

Adding Elements to a List

Prepend, Append and Concat

Because List is immutable, you can’t add new elements.
Instead, you create a new list by prepending or appending elements to an existing List.

val a = List(1,2,3)

prepend elements:

val b = 0 +: a
// val b: List[Int] = List(0, 1, 2, 3)

concat lists:

val c = List(-1, 0) ++: a
// val c: List[Int] = List(-1, 0, 1, 2, 3)

append elements

val d = a  :+ 0 // SLOW!
// val d: List[Int] = List(1, 2, 3, 0)

Remember the Method Names

The : character represents the side that the sequence is on.

so +: – list needs to be on the right

0 +: a

:+ – list needs to be on the left:

a :+ 4

Improve Performance

Vector

Vector provides random access and updates in effectively constant time and 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.

Prepend and Append -> Use Vector

List is a singly-linked list, so appending elements is relatively slow, especially when working with large sequences.

Use’ Vector’ instead if you want to prepend and append elements to an immutable sequence.

Access by Index -> Use Vector

Because List is a linked-list class, you shouldn’t try to access the elements of large lists by their index value. For instance, if you have a List with one million elements in it, accessing an element like myList(999999) will take a long time. If you want to access elements like this, use a Vector or ArrayBuffer instead.

List Type

Like arrays, lists are homogeneous: all elements must conform to a common declared or inferred element type. The type of a list with elements of type T is written scala. List[T] or shorter just List[T]

val fruit: List[String] = List("apples", "oranges", "pears")  
val nums : List[Int] = List(1, 2, 3, 4)  
val diag3: List[List[Int]] = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))  
val empty: List[Nothing] = List()

Operations

All operations on lists can be expressed in terms of the following three:

head - the first element of the list 
tail - the list composed of all the elements except the first. 
isEmpty ‘true‘ if the list is empty, ‘false‘ otherwise.

fruit.head // "apples"   
fruit.tail.head // "oranges"  

diag3.head // List(1, 0, 0)  

empty.head   
// would throw NoSuchElementException("head of empty list")

Decompose List with Pattern Matching

Nil – The Nil constant
p :: ps – A pattern that matches a list with a head matching p and a tail matching ps.
List(p1, ..., pn) – same as p1 :: … :: pn :: Nil

Examples

1 :: 2 :: xs – Lists of that start with 1 and then 2
x :: Nil – Lists of length 1
List(x) – Same as x :: Nil
List() – The empty list, same as Nil
List(2 :: xs) – A list that contains as only element another list that starts with 2.

Example Code

def listToString(list: List[String]): String = list match {  
  case s :: rest => s + " " + listToString(rest)  
  case Nil => ""  
}  

val fruits = "Apples" :: "Bananas" :: "Oranges" :: Nil  
//fruits: List[java.lang.String] = List(Apples, Bananas, Oranges)  

  listToString(fruits)  
//res0: String = "Apples Bananas Oranges "

Exercise

Consider the pattern

x :: y :: List(xs, ys) :: zs

What condition describes the length L of the lists it matches most accurately?
Answer:

The length L is >= 3

x’s length is 1
y’s length is 1
List(xs, ys)’s length is 1
The tail zs may contain zero or arbitrarily many elements.

so L = 1 + 1 + 1 + (0 or 1)
Result: L >= 3

Homework: Sorting Lists

To sort a list of numbers in ascending order:

• One way to sort the list List(7, 3, 9, 2) is to sort the tail List(3, 9, 2) to obtain List(2, 3, 9).
• The next step is to insert the head 7 in the right place to obtain the result List(2, 3, 7, 9).

// worst case of insert: Big(O): N  
def insert(x: Int, xs: List[Int]): List[Int] = xs match  
 case List() => List(x)  
 case y :: ys => if x < y then x :: xs else y :: insert(x, ys)  

def sort(xs: List[Int]): List[Int] = xs match  
 case List() => List()  
  case y :: ys => insert(y, sort(ys))  

sort(List(7, 3, 9, 2)) // val res0: List[Int] = List(2, 3, 7, 9)

Summary

List:

1. The ‘head’ method on a ‘List ‘ would NOT always produces type ‘T’ element. If the list is empty, ‘head’ throws a ‘NoSuchElementException’
2. It is possible to decompose lists with pattern matching such as p :: ps, ‘Nil’, ‘List(a)’
3. All elements must conform to the list’s element type; their concrete runtime types may differ.
4. Lists are immutable

Takeaway

For immutable List, head/tail/prepend are constant-time operations, while indexing and appending traverse the list. Choose a collection by its operation costs, and prefer headOption or pattern matching when emptiness is possible.