Collections Scala Data Structures Immutable Lists Vectors Sets Maps Performance

August 31, 2025

Immutable Collections: Lists, Vectors, Sets, and Maps

Explore Scala's rich collection library, understanding the performance characteristics and use cases for Lists, Vectors, Sets, Maps, and other immutable data structures.

Lesson 25 🚀 Practice

Immutable Collections: Lists, Vectors, Sets, and Maps

Introduction

Scala's collections library is one of its greatest strengths, providing a rich set of immutable data structures that are both performant and easy to use. Understanding the characteristics and appropriate use cases for different collection types is crucial for writing efficient Scala code.

In this lesson, you'll learn about the core immutable collections: Lists, Vectors, Sets, and Maps. You'll understand their performance characteristics, when to use each one, and how to work with them effectively in functional programming.

Lists: The Fundamental Sequence

Understanding Lists

Lists are the most commonly used sequence collection in functional programming. They are implemented as linked lists, making them ideal for recursive processing and prepending elements.

// Creating Lists
val emptyList = List()
val numbers = List(1, 2, 3, 4, 5)
val strings = List("apple", "banana", "cherry")
val mixed: List[Any] = List(1, "hello", true, 3.14)

println(numbers)  // List(1, 2, 3, 4, 5)
println(strings)  // List(apple, banana, cherry)

// List construction with cons operator (::)
val list1 = 1 :: 2 :: 3 :: Nil
val list2 = 0 :: numbers  // Prepend 0
val list3 = numbers :+ 6  // Append 6 (inefficient for Lists)

println(list1)  // List(1, 2, 3)
println(list2)  // List(0, 1, 2, 3, 4, 5)
println(list3)  // List(1, 2, 3, 4, 5, 6)

// List concatenation
val combined = List(1, 2) ++ List(3, 4) ++ List(5, 6)
val concatenated = numbers ::: List(6, 7, 8)  // List-specific concat

println(combined)      // List(1, 2, 3, 4, 5, 6)
println(concatenated)  // List(1, 2, 3, 4, 5, 6, 7, 8)

// Basic List operations
println(numbers.head)      // 1 (first element)
println(numbers.tail)      // List(2, 3, 4, 5) (all except first)
println(numbers.last)      // 5 (last element)
println(numbers.init)      // List(1, 2, 3, 4) (all except last)
println(numbers.length)    // 5
println(numbers.size)      // 5 (same as length)
println(numbers.isEmpty)   // false
println(numbers.nonEmpty)  // true

// Safe access methods
println(numbers.headOption)  // Some(1)
println(numbers.lastOption)  // Some(5)
println(emptyList.headOption)  // None
println(emptyList.lastOption)  // None

// Element access (O(n) complexity)
println(numbers(0))     // 1 (first element)
println(numbers(2))     // 3 (third element)
println(numbers.apply(4))  // 5 (last element)

// Safe element access
println(numbers.lift(2))   // Some(3)
println(numbers.lift(10))  // None

// Check if element exists
println(numbers.contains(3))     // true
println(numbers.contains(10))    // false
println(numbers.exists(_ > 4))   // true
println(numbers.forall(_ > 0))   // true

// Finding elements
println(numbers.find(_ > 3))          // Some(4)
println(numbers.findLast(_ < 4))      // Some(3)
println(numbers.indexOf(3))           // 2
println(numbers.indexWhere(_ > 3))    // 3

// List patterns and deconstruction
def describeList(list: List[Int]): String = list match {
  case Nil => "Empty list"
  case x :: Nil => s"Single element: $x"
  case x :: y :: Nil => s"Two elements: $x, $y"
  case head :: tail => s"Head: $head, Tail length: ${tail.length}"
}

val testLists = List(
  List(),
  List(42),
  List(1, 2),
  List(1, 2, 3, 4, 5)
)

testLists.foreach(list => println(s"$list: ${describeList(list)}"))

List Performance and Use Cases

import scala.util.Random

// List performance characteristics
def timeOperation[T](name: String)(operation: => T): T = {
  val start = System.nanoTime()
  val result = operation
  val end = System.nanoTime()
  println(f"$name: ${(end - start) / 1e6}%.2f ms")
  result
}

// Prepending is O(1) - very efficient
val baseList = (1 to 1000).toList
timeOperation("Prepend 1000 elements") {
  (1 to 1000).foldLeft(baseList)((acc, elem) => elem :: acc)
}

// Appending is O(n) - less efficient for large lists
timeOperation("Append 100 elements") {
  (1 to 100).foldLeft(baseList)((acc, elem) => acc :+ elem)
}

// List is excellent for recursive processing
def sum(list: List[Int]): Int = list match {
  case Nil => 0
  case head :: tail => head + sum(tail)
}

def product(list: List[Int]): Int = list match {
  case Nil => 1
  case head :: tail => head * product(tail)
}

def reverse[A](list: List[A]): List[A] = {
  def loop(remaining: List[A], acc: List[A]): List[A] = remaining match {
    case Nil => acc
    case head :: tail => loop(tail, head :: acc)
  }
  loop(list, Nil)
}

val numbers = List(1, 2, 3, 4, 5)
println(s"Sum: ${sum(numbers)}")           // Sum: 15
println(s"Product: ${product(numbers)}")   // Product: 120
println(s"Reversed: ${reverse(numbers)}")  // Reversed: List(5, 4, 3, 2, 1)

// List processing with higher-order functions
val scores = List(85, 92, 78, 96, 88, 73, 90)

val highScores = scores.filter(_ >= 90)
val bonusScores = scores.map(_ + 5)
val totalScore = scores.reduce(_ + _)
val averageScore = totalScore.toDouble / scores.length

println(s"High scores (>=90): $highScores")     // List(92, 96, 90)
println(s"Bonus scores (+5): $bonusScores")     // List(90, 97, 83, 101, 93, 78, 95)
println(f"Average score: $averageScore%.1f")    // Average score: 86.0

// Grouping and partitioning
val students = List(
  ("Alice", 92), ("Bob", 78), ("Charlie", 95), 
  ("Diana", 83), ("Eve", 88), ("Frank", 76)
)

val (passing, failing) = students.partition(_._2 >= 80)
val groupedByGrade = students.groupBy { case (_, score) =>
  score match {
    case s if s >= 90 => "A"
    case s if s >= 80 => "B"
    case s if s >= 70 => "C"
    case _ => "F"
  }
}

println("Passing students:")
passing.foreach { case (name, score) => println(s"  $name: $score") }

println("Grade distribution:")
groupedByGrade.foreach { case (grade, students) =>
  println(s"  Grade $grade: ${students.map(_._1).mkString(", ")}")
}

// List comprehensions and for-expressions
val matrix = List(
  List(1, 2, 3),
  List(4, 5, 6),
  List(7, 8, 9)
)

val flattened = matrix.flatten
val evenNumbers = for {
  row <- matrix
  num <- row
  if num % 2 == 0
} yield num

val coordinates = for {
  x <- 1 to 3
  y <- 1 to 3
} yield (x, y)

println(s"Flattened matrix: $flattened")        // List(1, 2, 3, 4, 5, 6, 7, 8, 9)
println(s"Even numbers: $evenNumbers")          // List(2, 4, 6, 8)
println(s"Coordinates: ${coordinates.toList}")  // List((1,1), (1,2), (1,3), (2,1), ...)

Vectors: Random Access Sequences

Understanding Vectors

Vectors provide efficient random access and are the default sequence type in Scala. They're implemented as tries with a branching factor of 32, providing nearly O(1) access time.

// Creating Vectors
val emptyVector = Vector()
val numbers = Vector(1, 2, 3, 4, 5)
val strings = Vector("apple", "banana", "cherry")

println(numbers)  // Vector(1, 2, 3, 4, 5)
println(strings)  // Vector(apple, banana, cherry)

// Vector construction
val vector1 = Vector(1, 2, 3)
val vector2 = 0 +: numbers      // Prepend 0
val vector3 = numbers :+ 6      // Append 6
val vector4 = numbers ++ Vector(6, 7, 8)  // Concatenate

println(vector2)  // Vector(0, 1, 2, 3, 4, 5)
println(vector3)  // Vector(1, 2, 3, 4, 5, 6)
println(vector4)  // Vector(1, 2, 3, 4, 5, 6, 7, 8)

// Random access is efficient O(log32 n) ≈ O(1)
println(numbers(0))     // 1
println(numbers(2))     // 3
println(numbers(4))     // 5

// Vector operations
println(numbers.head)      // 1
println(numbers.tail)      // Vector(2, 3, 4, 5)
println(numbers.last)      // 5
println(numbers.init)      // Vector(1, 2, 3, 4)
println(numbers.length)    // 5

// Updating elements (creates new Vector)
val updated = numbers.updated(2, 99)
println(numbers)  // Vector(1, 2, 3, 4, 5) - original unchanged
println(updated)  // Vector(1, 2, 99, 4, 5) - new vector

// Slicing
println(numbers.slice(1, 4))    // Vector(2, 3, 4)
println(numbers.take(3))        // Vector(1, 2, 3)
println(numbers.drop(2))        // Vector(3, 4, 5)
println(numbers.takeRight(2))   // Vector(4, 5)
println(numbers.dropRight(2))   // Vector(1, 2, 3)

// Vector performance comparison with List
val size = 100000
val largeList = (1 to size).toList
val largeVector = (1 to size).toVector

// Random access performance
val randomIndices = (1 to 1000).map(_ => Random.nextInt(size))

timeOperation("List random access") {
  randomIndices.map(largeList(_)).sum
}

timeOperation("Vector random access") {
  randomIndices.map(largeVector(_)).sum
}

// Append performance
timeOperation("List append") {
  (1 to 1000).foldLeft(List[Int]())((acc, elem) => acc :+ elem)
}

timeOperation("Vector append") {
  (1 to 1000).foldLeft(Vector[Int]())((acc, elem) => acc :+ elem)
}

// Prepend performance
timeOperation("List prepend") {
  (1 to 1000).foldLeft(List[Int]())((acc, elem) => elem :: acc)
}

timeOperation("Vector prepend") {
  (1 to 1000).foldLeft(Vector[Int]())((acc, elem) => elem +: acc)
}

Vector Use Cases

// Vector is ideal when you need both random access and functional operations
case class Point(x: Double, y: Double)

val points = Vector(
  Point(0, 0), Point(1, 1), Point(2, 4), 
  Point(3, 9), Point(4, 16), Point(5, 25)
)

// Efficient element access by index
def getPointAt(index: Int): Option[Point] = {
  if (index >= 0 && index < points.length) Some(points(index))
  else None
}

// Efficient updates
def updatePoint(index: Int, newPoint: Point): Vector[Point] = {
  if (index >= 0 && index < points.length) points.updated(index, newPoint)
  else points
}

// Efficient transformations
val translatedPoints = points.map(p => Point(p.x + 1, p.y + 1))
val scaledPoints = points.map(p => Point(p.x * 2, p.y * 2))

println("Original points:")
points.zipWithIndex.foreach { case (point, index) =>
  println(f"  Point $index: (${point.x}%.1f, ${point.y}%.1f)")
}

println("Translated points (+1, +1):")
translatedPoints.zipWithIndex.foreach { case (point, index) =>
  println(f"  Point $index: (${point.x}%.1f, ${point.y}%.1f)")
}

// Vector is excellent for windowing operations
def slidingWindow[A](seq: Vector[A], windowSize: Int): Vector[Vector[A]] = {
  (0 to seq.length - windowSize).map(i => seq.slice(i, i + windowSize)).toVector
}

val data = Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
val windows = slidingWindow(data, 3)

println("Sliding windows of size 3:")
windows.zipWithIndex.foreach { case (window, index) =>
  println(s"  Window $index: $window")
}

// Moving averages using Vector
def movingAverage(values: Vector[Double], windowSize: Int): Vector[Double] = {
  slidingWindow(values, windowSize).map(window => window.sum / window.length)
}

val temperatures = Vector(20.1, 22.3, 19.8, 25.2, 27.1, 23.9, 21.7, 18.9, 24.3, 26.5)
val averages = movingAverage(temperatures, 3)

println("Temperature moving averages (window size 3):")
averages.zipWithIndex.foreach { case (avg, index) =>
  println(f"  Day ${index + 2}: ${avg}%.1f°C")
}

// Vector for matrix operations
type Matrix = Vector[Vector[Double]]

def createMatrix(rows: Int, cols: Int)(f: (Int, Int) => Double): Matrix = {
  Vector.tabulate(rows, cols)(f)
}

def matrixTranspose(matrix: Matrix): Matrix = {
  val rows = matrix.length
  val cols = matrix.head.length
  Vector.tabulate(cols, rows)((j, i) => matrix(i)(j))
}

def matrixMultiply(a: Matrix, b: Matrix): Option[Matrix] = {
  if (a.head.length != b.length) None
  else {
    val result = for {
      i <- a.indices
      j <- b.head.indices
    } yield {
      (a(i) zip b.map(_(j))).map { case (x, y) => x * y }.sum
    }
    Some(result.grouped(b.head.length).toVector)
  }
}

val matrix1 = createMatrix(2, 3)((i, j) => i * 3 + j + 1)
val matrix2 = createMatrix(3, 2)((i, j) => (i + 1) * (j + 1))

println("Matrix 1:")
matrix1.foreach(row => println(s"  ${row.mkString("[", ", ", "]")}"))

println("Matrix 2:")
matrix2.foreach(row => println(s"  ${row.mkString("[", ", ", "]")}"))

matrixMultiply(matrix1, matrix2) match {
  case Some(result) =>
    println("Matrix multiplication result:")
    result.foreach(row => println(s"  ${row.mkString("[", ", ", "]")}"))
  case None =>
    println("Matrix multiplication not possible")
}

Sets: Unique Element Collections

Understanding Sets

Sets are collections of unique elements with no defined order. They provide very fast membership testing and are ideal when you need to ensure uniqueness or perform set operations.

// Creating Sets
val emptySet = Set()
val numbers = Set(1, 2, 3, 4, 5)
val duplicates = Set(1, 2, 2, 3, 3, 4, 5)  // Duplicates removed automatically
val strings = Set("apple", "banana", "cherry")

println(numbers)    // Set(5, 1, 2, 3, 4) - order not guaranteed
println(duplicates) // Set(5, 1, 2, 3, 4) - same as numbers
println(strings)    // Set(apple, banana, cherry)

// Set operations
println(numbers.contains(3))     // true
println(numbers.contains(10))    // false
println(numbers(3))              // true (same as contains)
println(numbers.size)            // 5
println(numbers.isEmpty)         // false
println(numbers.nonEmpty)        // true

// Adding and removing elements (creates new Set)
val withSix = numbers + 6
val withoutThree = numbers - 3
val withMultiple = numbers ++ Set(6, 7, 8)
val withoutMultiple = numbers -- Set(1, 2)

println(withSix)        // Set(5, 1, 6, 2, 3, 4)
println(withoutThree)   // Set(5, 1, 2, 4)
println(withMultiple)   // Set(5, 1, 6, 2, 7, 3, 8, 4)
println(withoutMultiple) // Set(5, 3, 4)

// Set algebra operations
val set1 = Set(1, 2, 3, 4, 5)
val set2 = Set(4, 5, 6, 7, 8)

val union = set1 ++ set2          // or set1 | set2
val intersection = set1 & set2    // or set1.intersect(set2)
val difference = set1 -- set2     // or set1.diff(set2)
val symmetric = (set1 ++ set2) -- (set1 & set2)  // or set1.diff(set2) ++ set2.diff(set1)

println(s"Set1: $set1")
println(s"Set2: $set2")
println(s"Union: $union")                    // Set(5, 1, 6, 2, 7, 3, 8, 4)
println(s"Intersection: $intersection")      // Set(5, 4)
println(s"Difference (set1 - set2): $difference")  // Set(1, 2, 3)
println(s"Symmetric difference: $symmetric") // Set(1, 6, 2, 7, 3, 8)

// Subset/superset operations
val smallSet = Set(2, 3)
val largeSet = Set(1, 2, 3, 4, 5)

println(s"$smallSet is subset of $largeSet: ${smallSet.subsetOf(largeSet)}")    // true
println(s"$largeSet is superset of $smallSet: ${largeSet.contains(smallSet)}")  // false - wrong method
println(s"$largeSet contains all of $smallSet: ${smallSet.forall(largeSet)}")   // true

// Different Set implementations
import scala.collection.immutable.{HashSet, TreeSet, ListSet}

val hashSet = HashSet(3, 1, 4, 1, 5, 9, 2, 6)   // Hash-based, fast operations
val treeSet = TreeSet(3, 1, 4, 1, 5, 9, 2, 6)   // Sorted order
val listSet = ListSet(3, 1, 4, 1, 5, 9, 2, 6)   // Insertion order

println(s"HashSet: $hashSet")  // Unordered
println(s"TreeSet: $treeSet")  // Sorted: TreeSet(1, 2, 3, 4, 5, 6, 9)
println(s"ListSet: $listSet")  // Insertion order: ListSet(3, 1, 4, 5, 9, 2, 6)

Set Use Cases and Applications

// Duplicate detection and removal
val words = List("apple", "banana", "apple", "cherry", "banana", "date", "apple")
val uniqueWords = words.toSet
val wordCounts = words.groupBy(identity).view.mapValues(_.length).toMap

println(s"Original words: $words")
println(s"Unique words: $uniqueWords")
println("Word counts:")
wordCounts.foreach { case (word, count) => 
  println(s"  $word: $count")
}

// Membership testing for validation
val validUserRoles = Set("admin", "moderator", "user", "guest")
val validFileExtensions = Set(".txt", ".pdf", ".doc", ".docx", ".jpg", ".png")

def validateUserRole(role: String): Boolean = validUserRoles(role)
def validateFileExtension(filename: String): Boolean = {
  validFileExtensions.exists(filename.toLowerCase.endsWith)
}

val testRoles = List("admin", "user", "hacker", "moderator", "superuser")
val testFiles = List("document.txt", "image.jpg", "script.exe", "report.pdf")

println("Role validation:")
testRoles.foreach { role =>
  val valid = validateUserRole(role)
  println(s"  $role: ${if (valid) "✓ Valid" else "✗ Invalid"}")
}

println("File validation:")
testFiles.foreach { file =>
  val valid = validateFileExtension(file)
  println(s"  $file: ${if (valid) "✓ Valid" else "✗ Invalid"}")
}

// Tag management system
case class Article(id: Int, title: String, tags: Set[String])

val articles = List(
  Article(1, "Scala Basics", Set("scala", "programming", "functional")),
  Article(2, "Java vs Scala", Set("scala", "java", "comparison", "programming")),
  Article(3, "Functional Programming", Set("functional", "programming", "concepts")),
  Article(4, "Data Structures", Set("data-structures", "algorithms", "programming"))
)

// Find articles by tag
def findArticlesByTag(tag: String): List[Article] = {
  articles.filter(_.tags(tag))
}

// Find articles with any of the given tags
def findArticlesByAnyTag(tags: Set[String]): List[Article] = {
  articles.filter(article => (article.tags & tags).nonEmpty)
}

// Find articles with all of the given tags
def findArticlesByAllTags(tags: Set[String]): List[Article] = {
  articles.filter(article => tags.subsetOf(article.tags))
}

// Get all unique tags
val allTags = articles.flatMap(_.tags).toSet

println(s"All unique tags: $allTags")

println("\nArticles tagged 'programming':")
findArticlesByTag("programming").foreach(a => println(s"  ${a.title}"))

println("\nArticles with 'scala' OR 'java':")
findArticlesByAnyTag(Set("scala", "java")).foreach(a => println(s"  ${a.title}"))

println("\nArticles with 'scala' AND 'programming':")
findArticlesByAllTags(Set("scala", "programming")).foreach(a => println(s"  ${a.title}"))

// Tag statistics
val tagFrequency = articles.flatMap(_.tags).groupBy(identity).view.mapValues(_.length).toMap
val sortedTags = tagFrequency.toList.sortBy(-_._2)

println("\nTag frequency:")
sortedTags.foreach { case (tag, count) =>
  println(s"  $tag: $count articles")
}

// Related articles based on shared tags
def findRelatedArticles(article: Article): List[(Article, Int)] = {
  articles
    .filter(_.id != article.id)
    .map(other => (other, (article.tags & other.tags).size))
    .filter(_._2 > 0)
    .sortBy(-_._2)
}

println(s"\nRelated articles for '${articles.head.title}':")
findRelatedArticles(articles.head).foreach { case (article, sharedTags) =>
  println(s"  ${article.title} ($sharedTags shared tags)")
}

// Access control using Sets
case class User(id: Int, name: String, roles: Set[String])
case class Resource(id: Int, name: String, requiredRoles: Set[String])

val users = List(
  User(1, "Alice", Set("admin", "user")),
  User(2, "Bob", Set("moderator", "user")),
  User(3, "Charlie", Set("user")),
  User(4, "Diana", Set("admin", "moderator", "user"))
)

val resources = List(
  Resource(1, "User Database", Set("admin")),
  Resource(2, "Moderation Panel", Set("admin", "moderator")),
  Resource(3, "User Profile", Set("user")),
  Resource(4, "Analytics", Set("admin"))
)

def canAccess(user: User, resource: Resource): Boolean = {
  (user.roles & resource.requiredRoles).nonEmpty
}

def getUserAccessibleResources(user: User): List[Resource] = {
  resources.filter(canAccess(user, _))
}

println("\nUser access control:")
users.foreach { user =>
  val accessible = getUserAccessibleResources(user)
  println(s"${user.name} (${user.roles.mkString(", ")}) can access:")
  accessible.foreach(r => println(s"  - ${r.name}"))
  println()
}

Maps: Key-Value Associations

Understanding Maps

Maps store key-value associations where each key is unique. They provide efficient lookup, insertion, and deletion operations.

// Creating Maps
val emptyMap = Map()
val ages = Map("Alice" -> 25, "Bob" -> 30, "Charlie" -> 35)
val scores = Map(1 -> "A", 2 -> "B", 3 -> "C", 4 -> "D", 5 -> "F")
val mixedMap: Map[String, Any] = Map("name" -> "Alice", "age" -> 25, "active" -> true)

println(ages)    // Map(Alice -> 25, Bob -> 30, Charlie -> 35)
println(scores)  // Map(1 -> A, 2 -> B, 3 -> C, 4 -> D, 5 -> F)

// Map operations
println(ages("Alice"))           // 25
println(ages.get("Alice"))       // Some(25)
println(ages.get("David"))       // None
println(ages.getOrElse("David", 0))  // 0

println(ages.contains("Bob"))    // true
println(ages.contains("Eve"))    // false
println(ages.size)               // 3
println(ages.isEmpty)            // false
println(ages.keys)               // Set(Alice, Bob, Charlie)
println(ages.values)             // Iterable(25, 30, 35)

// Adding and removing entries (creates new Map)
val withDavid = ages + ("David" -> 28)
val withoutBob = ages - "Bob"
val withMultiple = ages ++ Map("Eve" -> 32, "Frank" -> 29)
val withoutMultiple = ages -- List("Alice", "Charlie")

println(withDavid)      // Map(Alice -> 25, Bob -> 30, Charlie -> 35, David -> 28)
println(withoutBob)     // Map(Alice -> 25, Charlie -> 35)
println(withMultiple)   // Map(Alice -> 25, Bob -> 30, Charlie -> 35, Eve -> 32, Frank -> 29)
println(withoutMultiple) // Map(Bob -> 30)

// Updating values
val updatedAges = ages.updated("Alice", 26)
val incrementedAges = ages.view.mapValues(_ + 1).toMap

println(updatedAges)    // Map(Alice -> 26, Bob -> 30, Charlie -> 35)
println(incrementedAges) // Map(Alice -> 26, Bob -> 31, Charlie -> 36)

// Map transformations
val names = ages.keys.toList.sorted
val ageList = ages.values.toList.sorted
val tuples = ages.toList.sortBy(_._1)

println(s"Names: $names")      // List(Alice, Bob, Charlie)
println(s"Ages: $ageList")     // List(25, 30, 35)
println(s"Tuples: $tuples")    // List((Alice,25), (Bob,30), (Charlie,35))

// Filtering Maps
val youngPeople = ages.filter(_._2 < 30)
val oldPeople = ages.filterNot(_._2 < 30)

println(s"Young people: $youngPeople")  // Map(Alice -> 25)
println(s"Older people: $oldPeople")    // Map(Bob -> 30, Charlie -> 35)

// Map with default values
val defaultMap = ages.withDefaultValue(0)
println(defaultMap("Alice"))   // 25
println(defaultMap("Unknown")) // 0

val defaultMapFunction = ages.withDefault(key => key.length)
println(defaultMapFunction("Alice"))     // 25
println(defaultMapFunction("Unknown"))   // 7 (length of "Unknown")

Map Use Cases and Applications

// Frequency counting
val text = "the quick brown fox jumps over the lazy dog"
val words = text.split(" ").toList
val letterCounts = text.filter(_.isLetter).groupBy(identity).view.mapValues(_.length).toMap
val wordCounts = words.groupBy(identity).view.mapValues(_.length).toMap

println("Letter frequency:")
letterCounts.toList.sortBy(-_._2).foreach { case (letter, count) =>
  println(s"  $letter: $count")
}

println("\nWord frequency:")
wordCounts.foreach { case (word, count) =>
  println(s"  '$word': $count")
}

// Configuration management
case class DatabaseConfig(host: String, port: Int, database: String, username: String)
case class ServerConfig(host: String, port: Int, ssl: Boolean)

val configs = Map(
  "database" -> DatabaseConfig("localhost", 5432, "myapp", "user"),
  "server" -> ServerConfig("0.0.0.0", 8080, false)
)

def getConfig[T](name: String)(implicit map: Map[String, Any]): Option[T] = {
  map.get(name).map(_.asInstanceOf[T])
}

// Caching system
class Cache[K, V] {
  private var data = Map[K, V]()
  private var accessCount = Map[K, Int]()

  def get(key: K): Option[V] = {
    accessCount = accessCount.updated(key, accessCount.getOrElse(key, 0) + 1)
    data.get(key)
  }

  def put(key: K, value: V): Unit = {
    data = data.updated(key, value)
  }

  def remove(key: K): Unit = {
    data = data - key
    accessCount = accessCount - key
  }

  def getStats: Map[K, Int] = accessCount
  def size: Int = data.size
  def keys: Set[K] = data.keySet
}

val cache = new Cache[String, String]()
cache.put("user:1", "Alice")
cache.put("user:2", "Bob")
cache.put("user:3", "Charlie")

// Simulate cache access
List("user:1", "user:1", "user:2", "user:1", "user:3", "user:2").foreach { key =>
  cache.get(key) match {
    case Some(value) => println(s"Cache hit: $key -> $value")
    case None => println(s"Cache miss: $key")
  }
}

println("Cache access statistics:")
cache.getStats.foreach { case (key, count) =>
  println(s"  $key: $count accesses")
}

// Graph representation with Maps
type Graph[T] = Map[T, Set[T]]

val socialNetwork: Graph[String] = Map(
  "Alice" -> Set("Bob", "Charlie", "Diana"),
  "Bob" -> Set("Alice", "Eve"),
  "Charlie" -> Set("Alice", "Frank"),
  "Diana" -> Set("Alice"),
  "Eve" -> Set("Bob", "Frank"),
  "Frank" -> Set("Charlie", "Eve")
)

def findFriends(person: String): Set[String] = {
  socialNetwork.getOrElse(person, Set.empty)
}

def findMutualFriends(person1: String, person2: String): Set[String] = {
  findFriends(person1) & findFriends(person2)
}

def findFriendsOfFriends(person: String): Set[String] = {
  val directFriends = findFriends(person)
  val friendsOfFriends = directFriends.flatMap(findFriends)
  friendsOfFriends -- directFriends - person
}

println("Social network analysis:")
println(s"Alice's friends: ${findFriends("Alice")}")
println(s"Bob's friends: ${findFriends("Bob")}")
println(s"Mutual friends of Alice and Bob: ${findMutualFriends("Alice", "Bob")}")
println(s"Alice's friends of friends: ${findFriendsOfFriends("Alice")}")

// Inventory management
case class Product(id: String, name: String, price: Double)
case class InventoryItem(product: Product, quantity: Int, location: String)

val inventory = Map(
  "P001" -> InventoryItem(Product("P001", "Laptop", 999.99), 15, "Warehouse A"),
  "P002" -> InventoryItem(Product("P002", "Mouse", 29.99), 50, "Warehouse B"),
  "P003" -> InventoryItem(Product("P003", "Keyboard", 79.99), 25, "Warehouse A"),
  "P004" -> InventoryItem(Product("P004", "Monitor", 299.99), 8, "Warehouse C")
)

def findProductsByLocation(location: String): Map[String, InventoryItem] = {
  inventory.filter(_._2.location == location)
}

def getTotalInventoryValue: Double = {
  inventory.values.map(item => item.product.price * item.quantity).sum
}

def findLowStockItems(threshold: Int): Map[String, InventoryItem] = {
  inventory.filter(_._2.quantity <= threshold)
}

println("Inventory by location:")
List("Warehouse A", "Warehouse B", "Warehouse C").foreach { location =>
  val items = findProductsByLocation(location)
  println(s"$location:")
  items.foreach { case (id, item) =>
    println(f"  ${item.product.name}: ${item.quantity} units @ $$${item.product.price}%.2f")
  }
}

println(f"\nTotal inventory value: $$${getTotalInventoryValue}%.2f")

println("\nLow stock items (≤ 10 units):")
findLowStockItems(10).foreach { case (id, item) =>
  println(s"  ${item.product.name}: ${item.quantity} units")
}

Summary

In this lesson, you've mastered Scala's core immutable collections:

✅ Lists: Efficient for recursive processing and prepending operations
✅ Vectors: Best for random access and balanced operations
✅ Sets: Perfect for uniqueness constraints and membership testing
✅ Maps: Ideal for key-value associations and lookups
✅ Performance: Understanding when to use each collection type
✅ Real-world Applications: Practical examples for each collection

These collections form the foundation of functional programming in Scala and enable you to write efficient, expressive code.

What's Next

In the next lesson, we'll explore for-comprehensions and monads, learning how to chain operations elegantly and work with nested contexts using Scala's powerful for-yield syntax.

🚀 Practice Exercise

Put your knowledge to practice with hands-on coding exercises

Advanced ⏱️ 1h 30min

Instructions

Immutable Collections

Build a comprehensive data processing and analysis framework that demonstrates advanced usage of immutable collections, including performance optimization, custom collections, and complex data transformations.

Your program should:
1. Implement a multi-level caching system using nested Maps
2. Build performance benchmarks comparing List, Vector, and custom structures
3. Create a data pipeline with collection transformations and lazy evaluation
4. Implement custom collection operations using folds and recursion
5. Design a memory-efficient streaming processor for large datasets
6. Build a functional database query engine using collections

Requirements:
- Implement custom collection operations from scratch
- Compare performance across different collection types with measurements
- Use advanced collection methods (scanLeft, unfold, view, lazy operations)
- Handle large datasets efficiently with streaming techniques
- Implement complex data structures (tries, trees) using immutable collections
- Create functional abstractions over collection operations

Example usage:
```scala
val processor = DataProcessor()
val result = processor.pipeline(dataset)
.filter(complexPredicate)
.groupByKey(extractKey)
.aggregate(customAggregator)
.optimize()
```

Interactive Playground

⚠️ Spoiler Alert! Try to solve the exercise yourself first. Learning happens through practice!

```scala
import scala.collection.immutable._
import scala.util.Random
import java.util.concurrent.TimeUnit

object AdvancedCollectionsFramework extends App {

// Timing utilities
case class Benchmark(name: String, time: Long, result: Any)

def benchmark[T](name: String)(operation: => T): Benchmark = {
System.gc() // Suggest garbage collection
val start = System.nanoTime()
val result = operation
val end = System.nanoTime()
val timeMs = TimeUnit.NANOSECONDS.toMillis(end - start)
Benchmark(name, timeMs, result)
}

// 1. Multi-level Caching System
println("=== 1. Advanced Caching System ===")

class MultiLevelCache[K, V] {
private var l1Cache: Map[K, V] = Map.empty
private var l2Cache: Map[K, Map[String, V]] = Map.empty
private var l3Cache: Map[String, Map[K, V]] = Map.empty

def put(key: K, value: V, namespace: String = "default"): MultiLevelCache[K, V] = {
val newCache = new MultiLevelCache[K, V]
newCache.l1Cache = l1Cache + (key -> value)
newCache.l2Cache = l2Cache.updated(key,
l2Cache.getOrElse(key, Map.empty) + (namespace -> value))
newCache.l3Cache = l3Cache.updated(namespace,
l3Cache.getOrElse(namespace, Map.empty) + (key -> value))
newCache
}

def get(key: K): Option[V] = l1Cache.get(key)

def getFromNamespace(key: K, namespace: String): Option[V] = {
l3Cache.get(namespace).flatMap(_.get(key))
}

def getVersions(key: K): Map[String, V] = {
l2Cache.getOrElse(key, Map.empty)
}

def getAllInNamespace(namespace: String): Map[K, V] = {
l3Cache.getOrElse(namespace, Map.empty)
}

def size: (Int, Int, Int) = (l1Cache.size, l2Cache.size, l3Cache.size)

def evictLRU(maxSize: Int): MultiLevelCache[K, V] = {
if (l1Cache.size <= maxSize) this
else {
val newCache = new MultiLevelCache[K, V]
newCache.l1Cache = l1Cache.take(maxSize)
newCache.l2Cache = l2Cache
newCache.l3Cache = l3Cache
newCache
}
}
}

// Demonstrate caching system
var cache = new MultiLevelCache[String, String]()
cache = cache.put("user1", "Alice", "users")
cache = cache.put("user2", "Bob", "users")
cache = cache.put("session1", "active", "sessions")
cache = cache.put("user1", "Alice Updated", "users-v2")

println(s"L1 Cache user1: ${cache.get("user1")}")
println(s"Namespace users: ${cache.getAllInNamespace("users")}")
println(s"User1 versions: ${cache.getVersions("user1")}")
println(s"Cache sizes: ${cache.size}")

// 2. Performance Benchmarking Framework
println("\n=== 2. Performance Benchmarking ===")

val sizes = List(1000, 10000, 100000)
val operations = List("prepend", "append", "randomAccess", "map", "filter")

def generateTestData(size: Int): (List[Int], Vector[Int]) = {
val data = (1 to size).toList
(data, data.toVector)
}

def benchmarkCollections(size: Int): Map[String, List[Benchmark]] = {
val (list, vector) = generateTestData(size)
val random = new Random(42)

Map(
"prepend" -> List(
benchmark(s"List prepend $size") {
(1 to 1000).foldLeft(list)((acc, i) => i :: acc)
},
benchmark(s"Vector prepend $size") {
(1 to 1000).foldLeft(vector)((acc, i) => i +: acc)
}
),
"append" -> List(
benchmark(s"List append $size") {
(1 to 1000).foldLeft(list)((acc, i) => acc :+ i)
},
benchmark(s"Vector append $size") {
(1 to 1000).foldLeft(vector)((acc, i) => acc :+ i)
}
),
"randomAccess" -> List(
benchmark(s"List random access $size") {
(1 to 1000).map(_ => list(random.nextInt(list.size))).sum
},
benchmark(s"Vector random access $size") {
(1 to 1000).map(_ => vector(random.nextInt(vector.size))).sum
}
)
)
}

// Run benchmarks
sizes.foreach { size =>
println(s"\nBenchmarking with $size elements:")
val results = benchmarkCollections(size)
results.foreach { case (operation, benchmarks) =>
println(s"  $operation:")
benchmarks.foreach(b => println(f"    ${b.name}: ${b.time}%,d ms"))
}
}

// 3. Advanced Data Pipeline
println("\n=== 3. Functional Data Pipeline ===")

case class DataPoint(id: Int, category: String, value: Double, timestamp: Long)
case class AggregatedData(category: String, count: Int, sum: Double, avg: Double, max: Double, min: Double)

class DataProcessor {
def pipeline(data: Seq[DataPoint]): Pipeline = new Pipeline(data)
}

class Pipeline(private val data: Seq[DataPoint]) {
def filter(predicate: DataPoint => Boolean): Pipeline =
new Pipeline(data.filter(predicate))

def map[U](transform: DataPoint => U): Seq[U] =
data.map(transform)

def groupByCategory: Map[String, Seq[DataPoint]] =
data.groupBy(_.category)

def aggregate: Seq[AggregatedData] = {
groupByCategory.map { case (category, points) =>
val values = points.map(_.value)
AggregatedData(
category = category,
count = points.size,
sum = values.sum,
avg = values.sum / values.size,
max = values.max,
min = values.min
)
}.toSeq.sortBy(_.category)
}

def window(size: Int): Seq[Seq[DataPoint]] =
data.sliding(size).toSeq

def sample(n: Int): Pipeline = {
val sampled = if (data.size <= n) data
else Random.shuffle(data).take(n)
new Pipeline(sampled)
}

def toStream: LazyList[DataPoint] = data.to(LazyList)
}

// Generate sample data
val sampleData = (1 to 10000).map { i =>
DataPoint(
id = i,
category = List("A", "B", "C", "D")(Random.nextInt(4)),
value = Random.nextDouble() * 100,
timestamp = System.currentTimeMillis() + i * 1000
)
}

val processor = new DataProcessor()
val results = processor.pipeline(sampleData)
.filter(_.value > 50)
.sample(1000)
.aggregate

println("Pipeline Results (sample):")
results.take(3).foreach { agg =>
println(f"  ${agg.category}: count=${agg.count}%,d, avg=${agg.avg}%.2f, range=${agg.min}%.2f-${agg.max}%.2f")
}

// 4. Custom Collection Operations
println("\n=== 4. Custom Collection Operations ===")

object CustomOperations {

// Custom unfold operation
def unfold[A, B](seed: A)(f: A => Option[(B, A)]): LazyList[B] = {
f(seed) match {
case None => LazyList.empty
case Some((b, a)) => b #:: unfold(a)(f)
}
}

// Fibonacci using unfold
def fibonacci: LazyList[BigInt] = {
unfold((BigInt(0), BigInt(1))) { case (a, b) =>
Some((a, (b, a + b)))
}
}

// Custom partition with multiple predicates
def partitionMulti[A](seq: Seq[A])(predicates: (A => Boolean)*): Seq[Seq[A]] = {
predicates.map(pred => seq.filter(pred))
}

// Chunked processing with overlap
def chunkedOverlap[A](seq: Seq[A], chunkSize: Int, overlap: Int): Seq[Seq[A]] = {
if (seq.length <= chunkSize) Seq(seq)
else {
val step = chunkSize - overlap
seq.take(chunkSize) +: chunkedOverlap(seq.drop(step), chunkSize, overlap)
}
}

// Custom scanl with index
def scanWithIndex[A, B](seq: Seq[A], initial: B)(f: (B, A, Int) => B): Seq[B] = {
seq.zipWithIndex.scanLeft(initial) { case (acc, (elem, idx)) =>
f(acc, elem, idx)
}
}

// Frequency analysis
def frequencies[A](seq: Seq[A]): Map[A, Int] = {
seq.foldLeft(Map.empty[A, Int]) { (acc, elem) =>
acc.updated(elem, acc.getOrElse(elem, 0) + 1)
}
}

// Moving average
def movingAverage(values: Seq[Double], windowSize: Int): Seq[Double] = {
if (values.length < windowSize) Seq(values.sum / values.length)
else {
values.sliding(windowSize).map(window => window.sum / window.length).toSeq
}
}
}

// Demonstrate custom operations
println("Fibonacci first 10: " + CustomOperations.fibonacci.take(10).toList)

val testSeq = (1 to 20).toSeq
val partitioned = CustomOperations.partitionMulti(testSeq)(
_ % 2 == 0,    // evens
_ % 3 == 0,    // divisible by 3
_ > 10         // greater than 10
)
println("Multi-partition results:")
List("evens", "div by 3", "> 10").zip(partitioned).foreach { case (name, partition) =>
println(s"  $name: ${partition.take(5)}...")
}

val overlapped = CustomOperations.chunkedOverlap((1 to 10), 4, 2)
println(s"Chunked with overlap: $overlapped")

val withIndex = CustomOperations.scanWithIndex(List(1, 2, 3, 4), 0)((acc, elem, idx) => acc + elem * idx)
println(s"Scan with index: $withIndex")

val freqs = CustomOperations.frequencies("hello world".toList)
println(s"Character frequencies: $freqs")

val prices = Seq(10.0, 12.0, 11.0, 13.0, 15.0, 14.0, 16.0, 18.0)
val movingAvg = CustomOperations.movingAverage(prices, 3)
println(f"Moving averages: ${movingAvg.map(x => f"$x%.2f").mkString(", ")}")

// 5. Functional Trie Implementation
println("\n=== 5. Functional Trie Data Structure ===")

class Trie[V] private (private val children: Map[Char, Trie[V]], private val value: Option[V]) {

def insert(key: String, v: V): Trie[V] = {
if (key.isEmpty) new Trie(children, Some(v))
else {
val head = key.head
val tail = key.tail
val childTrie = children.getOrElse(head, Trie.empty[V])
val updatedChild = childTrie.insert(tail, v)
new Trie(children.updated(head, updatedChild), value)
}
}

def get(key: String): Option[V] = {
if (key.isEmpty) value
else children.get(key.head).flatMap(_.get(key.tail))
}

def startsWith(prefix: String): Boolean = {
if (prefix.isEmpty) true
else children.get(prefix.head).exists(_.startsWith(prefix.tail))
}

def keysWithPrefix(prefix: String): Set[String] = {
def findNode(key: String): Option[Trie[V]] = {
if (key.isEmpty) Some(this)
else children.get(key.head).flatMap(_.findNode(key.tail))
}

def collectKeys(node: Trie[V], currentPrefix: String): Set[String] = {
val current = if (node.value.isDefined) Set(currentPrefix) else Set.empty[String]
val fromChildren = node.children.flatMap { case (char, child) =>
collectKeys(child, currentPrefix + char)
}.toSet
current ++ fromChildren
}

findNode(prefix).map(collectKeys(_, prefix)).getOrElse(Set.empty)
}

def size: Int = {
val currentSize = if (value.isDefined) 1 else 0
currentSize + children.values.map(_.size).sum
}

def isEmpty: Boolean = value.isEmpty && children.isEmpty
}

object Trie {
def empty[V]: Trie[V] = new Trie[V](Map.empty, None)

def apply[V](pairs: (String, V)*): Trie[V] = {
pairs.foldLeft(empty[V]) { case (trie, (key, value)) =>
trie.insert(key, value)
}
}
}

// Demonstrate Trie
val dictionary = Trie(
"cat" -> "feline animal",
"car" -> "vehicle",
"card" -> "playing card",
"care" -> "attention",
"careful" -> "cautious",
"dog" -> "canine animal"
)

println(s"Dictionary size: ${dictionary.size}")
println(s"'car' definition: ${dictionary.get("car")}")
println(s"'card' exists: ${dictionary.get("card").isDefined}")
println(s"Starts with 'car': ${dictionary.startsWith("car")}")
println(s"Keys with prefix 'car': ${dictionary.keysWithPrefix("car")}")

// 6. Streaming Data Processor
println("\n=== 6. Memory-Efficient Streaming ===")

class StreamProcessor[A] {
def process[B](stream: LazyList[A])(transform: A => B): LazyList[B] = {
stream.map(transform)
}

def batchProcess[B](stream: LazyList[A], batchSize: Int)(transform: Seq[A] => Seq[B]): LazyList[B] = {
def batches(s: LazyList[A]): LazyList[Seq[A]] = {
if (s.isEmpty) LazyList.empty
else {
val batch = s.take(batchSize)
batch #:: batches(s.drop(batchSize))
}
}
batches(stream).flatMap(transform)
}

def aggregate[B](stream: LazyList[A], initial: B)(combine: (B, A) => B): B = {
stream.foldLeft(initial)(combine)
}

def takeWhileSum(stream: LazyList[Int], maxSum: Int): LazyList[Int] = {
def loop(s: LazyList[Int], currentSum: Int): LazyList[Int] = {
s match {
case head #:: tail if currentSum + head <= maxSum =>
head #:: loop(tail, currentSum + head)
case _ => LazyList.empty
}
}
loop(stream, 0)
}
}

val processor = new StreamProcessor[Int]()
val infiniteStream = LazyList.from(1)

// Only compute what we need
val processedStream = processor.process(infiniteStream)(_ * 2)
println(s"First 5 from infinite processed stream: ${processedStream.take(5).toList}")

val batchProcessed = processor.batchProcess(infiniteStream.take(100), 10) { batch =>
List(batch.sum)
}
println(s"Batch sums: ${batchProcessed.take(5).toList}")

val sumWhileUnder1000 = processor.takeWhileSum(infiniteStream, 1000)
println(s"Numbers that sum to <= 1000: ${sumWhileUnder1000.toList}")
println(s"Their sum: ${sumWhileUnder1000.sum}")

// 7. Query Engine
println("\n=== 7. Functional Query Engine ===")

case class Person(id: Int, name: String, age: Int, department: String, salary: Double)

class QueryEngine[T] {
def select[U](data: Seq[T])(selector: T => U): Seq[U] = data.map(selector)
def where(data: Seq[T])(predicate: T => Boolean): Seq[T] = data.filter(predicate)
def orderBy[U: Ordering](data: Seq[T])(keyExtractor: T => U): Seq[T] = data.sortBy(keyExtractor)
def groupBy[K](data: Seq[T])(keyExtractor: T => K): Map[K, Seq[T]] = data.groupBy(keyExtractor)
def take(data: Seq[T])(n: Int): Seq[T] = data.take(n)
def distinct(data: Seq[T]): Seq[T] = data.distinct

def join[U, K](left: Seq[T], right: Seq[U])(leftKey: T => K, rightKey: U => K): Seq[(T, U)] = {
for {
l <- left
r <- right
if leftKey(l) == rightKey(r)
} yield (l, r)
}

def aggregate[K, V](data: Seq[T])(groupBy: T => K)(agg: Seq[T] => V): Map[K, V] = {
data.groupBy(groupBy).mapValues(agg)
}
}

val people = Seq(
Person(1, "Alice", 30, "Engineering", 75000),
Person(2, "Bob", 25, "Sales", 60000),
Person(3, "Charlie", 35, "Engineering", 85000),
Person(4, "Diana", 28, "Marketing", 65000),
Person(5, "Eve", 32, "Sales", 70000)
)

val query = new QueryEngine[Person]()

// Complex query: Find top earner by department
val topEarners = query.aggregate(people)(_.department) { people =>
people.maxBy(_.salary)
}

println("Top earners by department:")
topEarners.foreach { case (dept, person) =>
println(s"  $dept: ${person.name} - $${person.salary:,.0f}")
}

// Multi-step query
val engineersOver30 = query.where(
query.where(people)(_.department == "Engineering")
)(_.age > 30)

val engineerNames = query.select(engineersOver30)(_.name)
println(s"Engineers over 30: ${engineerNames.mkString(", ")}")

// Salary statistics by department
val salaryStats = query.aggregate(people)(_.department) { people =>
val salaries = people.map(_.salary)
(salaries.min, salaries.max, salaries.sum / salaries.size)
}

println("Salary statistics by department (min, max, avg):")
salaryStats.foreach { case (dept, (min, max, avg)) =>
println(f"  $dept: $$$min%,.0f - $$$max%,.0f (avg: $$$avg%,.0f)")
}

println("\n=== Advanced Collections Framework Complete! ===")
println("Demonstrated:")
println("- Multi-level caching with immutable Maps")
println("- Performance benchmarking framework")
println("- Functional data processing pipelines")
println("- Custom collection operations and algorithms")
println("- Immutable Trie data structure")
println("- Memory-efficient streaming processing")
println("- Functional query engine")
}
```

Comments

Be the first to comment on this lesson!

Immutable Collections: Lists, Vectors, Sets, and Maps

Introduction

Lists: The Fundamental Sequence

Understanding Lists

List Performance and Use Cases

Vectors: Random Access Sequences

Understanding Vectors

Vector Use Cases

Sets: Unique Element Collections

Understanding Sets

Set Use Cases and Applications

Maps: Key-Value Associations

Understanding Maps

Map Use Cases and Applications

Summary

What's Next

🚀 Practice Exercise

Instructions

Interactive Playground

Comments

Sign In

Sign Up

Reset Password

Sign Out

Reset Password