Programming in Scala [Chapter 16] — Working with Lists

Photo by Glenn Carstens-Peters on Unsplash

Introduction

This is part of my personal reading summary of the book — Programming in Scala. Take into account, we use Scala 2 since it is in industry and has vastly more resources available than Scala 3.

In Scala programs, lists emerge as one of the most frequently employed data structures. This chapter provides an in-depth exploration of lists through the following sections:

1. List literals
2. The List type
3. Constructing lists
4. Basic operations on lists
5. List patterns
6. First-order methods on class List

7. High-order methods on class List

8. Methods of the List object

9. Understanding Scala’s type inference algorithm

1. List literals

Lists resemble arrays but differ in two key aspects. First, lists are immutable — element values cannot be altered through assignment. Second, lists have a recursive, linked structure, in contrast to the flat nature of arrays.

val fruit = List("apples", "oranges", "pears")
val nums = List(1, 2, 3, 4)
val diag3 = List(
  List(1, 0, 0),
  List(0, 1, 0),
  List(0, 0, 1)
)
val empty = List()

2. The List type

In Scala, lists are homogeneous, meaning elements share the same type. List[T] denotes a list with elements of type T (see the examples above). Furthermore, Scala’s list type is covariant, meaning if S is a subtype of T, then List[S] is a subtype of List[T]. For instance, List[String] is a subtype of List[Object]. The empty list has type List[Nothing], the bottom type in Scala’s hierarchy, making it a subtype of every other list type (List[T]). This allows assignments like:

val xs: List[String] = List()  // List() is also of type List[String]!

3. Constructing lists

Lists in Scala are constructed using Nil and the infix operator :: (“cons”). Nil represents an empty list, while x :: xs denotes a list with x as its first element and xs as the rest.

val fruit = "apples" :: ("oranges" :: ("pears" :: Nil))
val nums = 1 :: 2 :: 3 :: 4 :: Nil
val diag3 = (1 :: (0 :: (0 :: Nil))) ::
            (0 :: (1 :: (0 :: Nil))) ::
            (0 :: (0 :: (1 :: Nil))) :: Nil
val empty = Nil

In these examples, fruit and nums demonstrate the creation of lists using cons (::). The associativity of :: is right-to-left, allowing for concise expressions without parentheses. For instance, val nums = 1 :: 2 :: 3 :: 4 :: Nil is equivalent to the previous definition of nums.

4. Basic operations on lists

Fundamental list operations in Scala are head, tail, and isEmpty methods. The head method retrieves the first element, tail returns the list without the first element, and isEmpty indicates if the list is empty.

// Using list operations
empty.isEmpty       // returns true
fruit.isEmpty       // returns false
fruit.head           // returns "apples"
fruit.tail.head      // returns "oranges"

The insert function inserts an element into a sorted list at the correct position. The isort function recursively applies insert to sort the input list.

def insert(x: Int, xs: List[Int]): List[Int] =
  if (xs.isEmpty || x <= xs.head) x :: xs
  else xs.head :: insert(x, xs.tail)

def isort(xs: List[Int]): List[Int] =
  if (xs.isEmpty) Nil
  else insert(xs.head, isort(xs.tail))

5. List patterns

This section explores pattern matching on lists in Scala. Lists can be deconstructed using patterns like List(a, b, c) for fixed-length lists or a :: b :: rest for lists of 2 or more elements. An example illustrates list pattern matching:

val List(a, b, c) = fruit // Matches lists of length 3
val a :: b :: rest = fruit // Matches lists of length 2 or greater

Pattern matching on lists provides a concise alternative to methods like head, tail, and isEmpty. An example demonstrates insertion sort using pattern matching:

def insert(x: Int, xs: List[Int]): List[Int] = xs match {
  case List()  => List(x)
  case y :: ys => if (x <= y) x :: xs else y :: insert(x, ys)
}

def isort(xs: List[Int]): List[Int] = xs match {
  case List()   => List()
  case x :: xs1 => insert(x, isort(xs1))
}

6. First-order methods on class List

This section covers first-order methods in the List class. A method is first-order if it does not take any funcions as arguments. At first, it introduces list concatenation (:::) with examples. It then explores the “Divide and Conquer” principle through the implementation of concatenation and demonstrates the length, init, last, reverse, drop, take, splitAt, apply, indices, zip, zipWithIndex, toString, and mkString methods. Additionally, it discusses converting lists using elements, toArray, copyToArray, and provides an example of merge sort, showcasing currying for flexible sorting methods. All these examples are shown below:

// List concatenation (:::)
List(1, 2) ::: List(3, 4, 5) // Result: List(1, 2, 3, 4, 5)

// Divide and Conquer principle - Concatenation
def append[T](xs: List[T], ys: List[T]): List[T] =
  xs match {
    case List() => ys
    case x :: xs1 => x :: append(xs1, ys)
  }

// Length
List(1, 2, 3).length // Result: 3

// Accessing end of a list - Init and Last
val abcde = List('a', 'b', 'c', 'd', 'e')
abcde.last // Result: 'e'
abcde.init // Result: List('a', 'b', 'c', 'd')

// Reversing lists
abcde.reverse // Result: List('e', 'd', 'c', 'b', 'a')

// Prefixes and Suffixes - Drop, Take, SplitAt
abcde.take(2) // Result: List('a', 'b')
abcde.drop(2) // Result: List('c', 'd', 'e')
abcde.splitAt(2) // Result: (List('a', 'b'), List('c', 'd', 'e'))

// Element selection - Apply and Indices
abcde(2) // Result: 'c'
abcde.indices // Result: List(0, 1, 2, 3, 4)

// Zipping lists
abcde.indices zip abcde // Result: List((0,'a'), (1,'b'), (2,'c'), (3,'d'), (4,'e'))

// Displaying lists - ToString and MkString
abcde.toString // Result: "List(a, b, c, d, e)"
abcde.mkString("[", ",", "]") // Result: "[a,b,c,d,e]"

// Merge sort example
def msort[T](less: (T, T) => Boolean)(xs: List[T]): List[T] = {
  def merge(xs: List[T], ys: List[T]): List[T] =
    (xs, ys) match {
      case (Nil, _) => ys
      case (_, Nil) => xs
      case (x :: xs1, y :: ys1) =>
        if (less(x, y)) x :: merge(xs1, ys)
        else y :: merge(xs, ys1)
    }
  val n = xs.length / 2
  if (n == 0) xs
  else {
    val (ys, zs) = xs splitAt n
    merge(msort(less)(ys), msort(less)(zs))
  }
}

// Sorting with merge sort
msort((x: Int, y: Int) => x < y)(List(5, 7, 1, 3)) // Result: List(1, 3, 5, 7)

7. Higher-order methods on class List

This section explores higher-order operators in Scala for common list operations, offering concise alternatives to loops. Four main operations are discussed:

7.1 Mapping over Lists

// map: Transforms each element in a list using a given function.
List(1, 2, 3) map (_ + 1) // Result: List(2, 3, 4)

// flatMap: Applies a function returning a list to each element and concatenates the results
words flatMap (_.toList) // Result: List(t, h, e, q, u, i, c, k, b, r, o, w, n, f, o, x)

// foreach: Applies a procedure to each element without creating a new list.
var sum = 0
List(1, 2, 3, 4, 5) foreach (sum += _)

7.2 Filtering Lists

// filter: Selects elements satisfying a given predicate.
List(1, 2, 3, 4, 5) filter (_ % 2 == 0) // Result: List(2, 4)

// partition: Splits a list into two based on a predicate.
List(1, 2, 3, 4, 5) partition (_ % 2 == 0) // Result: (List(2, 4), List(1, 3, 5))

// find: Returns the first element satisfying a predicate.
List(1, 2, 3, 4, 5) find (_ % 2 == 0) // Result: Some(2)

// takeWhile and dropWhile: Extracts a prefix or removes a prefix based on a predicate.
List(1, 2, 3, -4, 5) takeWhile (_ > 0) // Result: List(1, 2, 3)

// span: Combines takeWhile and dropWhile, returning a pair of lists.
List(1, 2, 3, -4, 5) span (_ > 0) // Result: (List(1, 2, 3), List(-4, 5))

7.3 Folding Lists

// '/:' (fold left) and ':\' (fold right): Combine list elements using a binary operator.
def sum(xs: List[Int]): Int = (0 /: xs) (_ + _)

// foldLeft and foldRight: Alternatives to '/:' and ':\' with reversed operand order.
def reverseLeft[T](xs: List[T]): List[T] = (List[T]() /: xs) {(ys, y) => y :: ys}

7.4 Sorting Lists

// sort: Sorts a list based on a comparison function.
List(1, -3, 4, 2, 6) sort (_ < _) // Result: List(-3, 1, 2, 4, 6)

8. Methods of the List object

This section covers methods in the globally accessible object scala.List, the companion object of class List in Scala.

// List.apply for Creating Lists from Elements
List.apply(1, 2, 3) // Result: List(1, 2, 3)

// List.range for Creating a Range of Numbers
List.range(1, 5) // Result: List(1, 2, 3, 4)

// List.make for Creating Uniform Lists
List.make(5, 'a') // Result: List(a, a, a, a, a)

// List.unzip for Unzipping Lists
val zipped = "abcde".toList zip List(1, 2, 3)
List.unzip(zipped) // Result: (List(a, b, c), List(1, 2, 3))

// List.flatten and List.concat for Concatenating Lists
val xss = List(List('a', 'b'), List('c'), List('d', 'e'))
List.flatten(xss) // Result: List(a, b, c, d, e)
List.concat(List('a', 'b'), List('c')) // Result: List(a, b, c)

// List.map2, List.forall2, List.exists2 for Mapping and Testing Pairs of Lists]
List.map2(List(10, 20), List(3, 4, 5)) (_ * _) // Result: List(30, 80)
List.forall2(List("abc", "de"), List(3, 2)) (_.length == _) // Result: true
List.exists2(List("abc", "de"), List(3, 2)) (_.length != _) // Result: false

9. Understanding Scala’s type inference algorithm

This section discusses the difference between the use of sort and a custom sorting function msort in Scala, focusing on the syntactic forms of the comparison function. The example below demonstrates that the concise form (_ > _) can be used with sort but not with msort, requiring an explicit type parameter or a modification to the method to make it work. The Scala's type inference algorithm emphasizes the flow-based nature and provides solutions to the issues encountered, such as passing an explicit type parameter or modifying the method's parameter order.

// Example using sort
abcde sort (_ > _)

// Example using msort with explicit type parameter
msort[Char](_ > _)(abcde)

// Example using msort with modified method
def msortSwapped[T](xs: List[T])(less: (T, T) => Boolean): List[T] = {
  // Implementation
}

msortSwapped(abcde)(_ > _)

Concluding Thoughts

In conclusion, this chapter comprehensively explores the intricacies of working with lists in Scala, covering fundamental concepts such as list literals, the List type, and constructing lists. It delves into basic operations, list patterns, and first-order methods, offering a thorough understanding of list manipulation. The chapter then extends to higher-order methods, demonstrating concise alternatives to traditional loops for mapping, filtering, and folding lists. Additionally, it explores sorting techniques and introduces methods available in the List object. The discussion on Scala’s type inference algorithm sheds light on the importance of understanding syntactic forms, particularly in scenarios like custom sorting functions, where explicit type parameters or method modifications become necessary.

With this, we conclude the sixteenth chapter of this series. I hope it adds value to people who are interested in learning Scala.

Please don’t hesitate to contact me on LinkedIn with any comments or feedback.

Other chapters in this series can be found in this reading list.

Resources:

Odersky, M., Spoon, L., & Venners, B. (2008). Programming in scala. Artima Inc.