Other Collections

Now that we've covered the List and some relevant Traversables in the Scala standard library, we should also visit some other useful collections Scala provides. Even though this section has less theoretical material, this means that we'll have more time on the final activities of the chapter.

Sets

Sets are Iterables that contain no duplicate elements. The Set class provides methods to check for the inclusion of an element in the collection, as well as combining different collections. Note that since Set inherits from Traversable, you can apply all the higher-order functions we've seen previously on it. Due to the nature of its apply method, a Set can be seen as a function of type A => Boolean, which returns true if the element is present in the set, and false otherwise.

Tuples

A tuple is a class capable of containing an arbitrary number of elements of different types. A tuple is created by enclosing its elements in parentheses. A tuple is typed according to the type of its elements.

Let's now create tuples in REPL and access their elements by following these steps:

  1. Create some tuples in the REPL and access their elements.
  2. Observe the type of the tuples created, and how it depends on the enclosing elements' types.
  3. Use pattern matching as a way to destructure tuples.

The full code looks as follows:

scala> val tup = (1, "str", 2.0)
tup: (Int, String, Double) = (1,str,2.0)

scala> val (a, b, c) = tup
a: Int = 1
b: String = str
c: Double = 2.0

scala> tup._1
res0: Int = 1

scala> tup._2
res1: String = str

scala> tup._3
res2: Double = 2.0

scala> val pair = 1 -> "str"
pair: (Int, String) = (1,str)

Maps

A Map is an Iterable of tuples of size two (pairs of key/values), which are also called mappings or associations. A Map can't have repeated keys. One interesting fact about maps in Scala is that Map[A, B] extends PartialFunction[A, B], so you can use a Map in places where you need a PartialFunction.

Note

For more information, refer to the Scaladoc of the Map trait here: https://www.scala-lang.org/api/current/scala/collection/Map.html.

Mutable and Immutable Collections

So far, we've been covering mostly immutable collections (with the exception of Iterators, which are inherently mutable since most operations over it change its state—do note that iterators obtained from the iterator method of Scala collections are not expected to mutate the underlying collection). It is important to note, however, that Scala also provides a set of mutable collections in the scala.collection.mutable package. Mutable collections provide operations to change the collection in place.

A useful convention for using both immutable and mutable collections in the same place is to import the scala.collection.mutable package and prefix collection declaration with the mutable keyword, which is Map vs mutable.Map.

The following code shows the difference between the immutable and mutable Maps of Scala, showing that the latter has an update method that changes the collection in place: 

scala> import scala.collection.mutable
import scala.collection.mutable

scala> val m = Map(1 -> 2, 3 -> 4)
m: scala.collection.immutable.Map[Int,Int] = Map(1 -> 2, 3 -> 4)

scala> val mm = mutable.Map(1 -> 2, 3 -> 4)
mm: scala.collection.mutable.Map[Int,Int] = Map(1 -> 2, 3 -> 4)

scala> mm.update(3, 5)

scala> mm
res1: scala.collection.mutable.Map[Int,Int] = Map(1 -> 2, 3 -> 5)

scala> m.update(3, 5)
<console>:14: error: value update is not a member of scala.collection.immutable.Map[Int,Int]
       m.update(3, 5)
         ^

scala> m.updated(3, 5)
res3: scala.collection.immutable.Map[Int,Int] = Map(1 -> 2, 3 -> 5)

scala> m
res4: scala.collection.immutable.Map[Int,Int] = Map(1 -> 2, 3 -> 4)

Activity: Implementing the Tower of Hanoi Problem

We want to create a solver for the Tower of Hanoi problem. If you are not familiar with the puzzle, visit the Wikipedia page at https://en.wikipedia.org/wiki/Tower_of_Hanoi This is a good entry point for it:

  1. Implement the pathsinner function of the following function:
    def path(from: Int, to: Int, graph: Map[Int, List[Int]]): List[Int] = {
  def paths(from: Int): Stream[List[Int]] = ???
  paths(from).dropWhile(_.head != to).head.reverse
}

    The path function should return the shortest path from the from node to the to node in the graph graph. The graph is defined as an adjacency list encoded as a Map[Int, List[Int]]. The path's inner function should return a Stream of paths in increasing length (in a breadth-first search manner).

  2. Implement the nextHanoi function:
    type HanoiState = (List[Int], List[Int], List[Int])
def nextHanoi(current: HanoiState): List[HanoiState]

    The nextHanoi function should return a list of valid states one can achieve from the current HanoiState. For example: nextHanoi((List(1, 2, 3), Nil, Nil)) should return List((List (2, 3),List(1),List()), (List(2, 3),List(),List(1))).

  3. Generalize the previously implemented path method to be parameterized on the type of state we're operating on:
    def genericPath[A](from: A, to: A, nextStates: A => List[A]): List[A] = {
 def paths(current: A): Stream[List[A]] = ???
  paths(from).dropWhile(_.head != to).head.reverse
}
  4. With this new implementation, you should be able to solve the Tower of Hanoi problem by calling, for example:
    val start = (List(1, 2, 3), Nil, Nil)
val end = (Nil, Nil, List(1, 2, 3))
genericPath(start, end, nextHanoi)
  5. A possible implementation of the proposed activity is the following:
    // Does not avoid already visited nodes
def path(from: Int, to: Int, graph: Map[Int, List[Int]]): List[Int] = {
  def paths(current: Int): Stream[List[Int]] = {
    def bfs(current: Stream[List[Int]]): Stream[List[Int]] = {
      if (current.isEmpty) current
      else current.head #:: bfs(current.tail #::: graph(current.head.head).map(_ :: current.head).toStream)
    }
 
    bfs(Stream(List(current)))
  }
 
  paths(from).dropWhile(_.head != to).head.reverse
}
 
type HanoiState = (List[Int], List[Int], List[Int])
 
def nextHanoi(current: HanoiState): List[HanoiState] = {
  def setPile(state: HanoiState, i: Int, newPile: List[Int]): HanoiState = i match {
…
…
 genericPath(start, end, nextHanoi).size
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset