Think of your daily routine. You wake up, you go to work, you go back home, and you go back to sleep. Your activities are looping, with them changing somewhat based on what's happening in your life. It is frequently necessary to set up similar structures in programming. Perhaps you have a piece of code that performs an action when a person presses a key. Or maybe you need to have something check your mail every 15 minutes.

This concept of looping is frequently handled via two things in Scala, a for-expression, and data structures. In this unit, we'll be exploring these two concepts and how to use them

If you have any issues understanding the material in this unit, please ask questions in the discord channel I've set up for teaching Scala, or you can discuss on scala-users.

Please remember to run the provided examples via the Scala console unless told otherwise. If you've forgotten how to launch and/or shut down the Scala console, please refer here.

Data Structures

Imagine if you will that you have a collection of video games. You could keep your collection in a giant pile on the floor of your room, but usually you'd arrange them in a way that makes playing and enjoying them the way you want more feasible. Maybe you like to find your games by name, and like to play games rather randomly. In that case you may store your games in a library shelf in alphabetical order. What if you always play the game you most recently acquired first, and when you finish a game, you give it away to your brother or friend? Then you might store your games in a stack, with newly purchased games on top, and games being removed from the stack when you've finished them. Maybe you want to play the oldest games you haven't finished yet before playing newer games. You might then store your games in a left-to-right queue where the oldest unfinished games are on the left, and new games are added on the right.

These are examples of data structures; programming constructs designed to store data and allow it to be used very easily. Data structures are specifically created and designed to help certain uses of data while disfavoring others. For example, a stack is designed to let you use and remove the most recently added data very easily. A queue lets you handle data in a first in, first out pattern easily. A sorted set lets you find data based on an ordered property (like name) quickly, and lets you quickly determine if you have a piece of data or not.

Scala supports a wide swath of data structures by default. In this Unit, we'll only discuss Lists though.

List

One of the most common and most frequently used data structures in Scala is called List. It's an implementation of a singly-linked list, and is frequently used to store lists of data. A List can store multiple related pieces of data together, allowing you to associate these pieces of data together quite naturally. For example, imagine you wanted to record in your program a list of things you'd like to buy at the store. In Scala, you would do this via the following code:

scala> val shoppingList = List("mango", "oranges", "tomato")
val shoppingList: List[String] = List(mango, oranges, tomato)

With a List you are able to associate these three Strings representing things you should purchase with the concept of shopping. They have an order (the first element of the list is "mango", and the data can be pulled out of the list in said order.

Polymorphic types

You may have noticed that the type of shoppingList is odd compared to what we've seen before. It's not List, but rather List[String]. This is because List is something we call a polymorphic type.

Lists are designed to hold any data you want to put in them, and in order to do that while still letting you know what kind of data they contain, they have a type parameter. List[String] is a List that has the type parameter String, indicating that the List contains Strings. If you created a List with Ints, you would see that your result type would be List[Int].

scala> List(1,2,3)
val res0: List[Int] = List(1,2,3)

So what happens if you put different types of data into a List?

scala> List("hello", 1)
val res0: List[Matchable] = List(hello, 1)

If you remember the chart from the if-expression, this result type might make sense to you. Just like how an if-expression will try to find the common parent type of multiple different types, a List will find the common parent type of its inputs, and that type will be the type parameter to the list. If you see this happening in your code, you have probably messed up somewhere. Try to keep only the same types of data in a List

Practice

1. Create a List of your favorite tv shows
2. The stock market crashed in 1926, 1974, 1987, 2000, and 2008. Make a list of this data

For-expressions

We now know how to define a shopping list in Scala using the List type, but we don't really know what to do with it or how to use it. The most common thing to do with Lists in Scala is to process each element of them in order with something called a for-expression. Let's say for example that you wanted to print each element of your shopping list in the console for your spouse to pick up later. Using a for-expression would make this relatively easily.

However, let's first look at the structure of a for-expression:

for <name> <- <expression> yield <expression to repeat>

A for-expression starts with the for keyword. Next you provide a name following the naming conventions introduced in past lessons. We'll call this name the "element name from now on. After the element name, you use a left arrow <-, followed by an expression that returns a List (such as our shopping list). Finally, after the yield keyword, you provide an expression that will be evaluated for every element in the List; we'll call it the "yield expression". The element name you provided at the beginning of the for-expression can be used inside the yield expression, and that name is assigned the value of the current element in the List. It behaves a lot like a value, however, its value changes to be each element of a List in the order it was put into the List.

That's a lot to understand in theory, so lets try applying it:

scala> for item <- List("mango", "oranges", "tomato") 
  yield println(s"Please buy some $item.")
Please buy some mango.
Please buy some oranges.
Please buy some tomato.
val res0: List[Unit] = List((), (), ())

As you can see, for every element in our shopping list, a prompt like Please buy some mango. was written. This shows that item, the element name we gave to the for-expression, was assigned the value of each item in the List as we progressed through the List, and that the yield expression println(s"Please buy some $item") was evaluated for each element of the List.

The result type of a for-expression

As you may have noticed, our for-expression is an expression. It gave data back, and that data was a List the same size as our input list, with the result of evaluating the yield expression for each element. In this case, our expression was println(s"Please buy some $item"), so the only results we got were () for each expression. However, we could use any expression we want, and get the data back for that expression in a second list:

scala> for number <- List(1, 2, 3) yield number + 1
val res0: List[Int] = List(2,3,4)

As stated in many previous units, you can use a code block as the expression after the yield or the expression that returns the List, as you wish.

scala> for number <-
  val a = 1
  val b = 2
  val c = 3
  List(a, b, c)
yield 
  println(number)
  number * number

1
2
3
val res0: List[Int] = List(1, 4, 9)

You can also use if-expressions:

scala> def absoluteList(list: List[Int]) =
  for element <- list
  yield 
    if element < 0 then 
      -element
    else
      element

def absoluteList(list: List[Int]): List[Int]
scala> absoluteList(List(-2,-1,0,1,2))
val res0: List[Int] = List(2,1,0,1,2)

Ignoring elements in a List

Let's say you're writing hiring software for a business, and management wants to give their system a list of potential applicants and get the list of people to hire back from the system. Now, management isn't very good at their jobs, and the hiring criteria they've given you is... questionable...

Please develop a program to select people to hire from a list of applicant first names. The program should only hire people whose first name is more than 5 letters long. Short first names are a sign of weak character and poor work ethic!!

An addition to the syntax of a for-expression allows you easily implement this hiring program:

for <name> <- <list expression> if <boolean expression> yield <expression>

We've now added an ifafter the list-expression in our for-expression. This if allows us to filter the elements of the List, and makes sure the expression after the yield only sees data that returns true in the boolean expression.

scala> def hiringProgram(employeeNames: List[String]) = 
  for name <- employeeNames if name.size > 5
  yield 
    println(s"Hire $name!")
    name

def hiringProgram(employeeNames: List[String]): List[String]
scala> hiringProgram(List("Fred", "Jake", "Samantha", "Edward"))
Hire Samantha!
Hire Edward!
val res0: List[String] = List(Samantha, Edward)

In the above example, we give the name name for each employee name in the list employeeNames, and we filter who we hire by checking if name.size is greater than 5. For those names which match the condition, the yield expression is run. Since only two names in our example call can pass this filter, our resulting List is only two elements long, half the size of the original list.

This filtering can be added whenever you're using a for-expression, and the boolean expression for the filter doesn't necessarily have to use the element name.

scala> for i <- List(1,2,3) if false yield i
val res0: List[Int] = List()

Multi-list for-expressions

Imagine we have a method that enters a four digit code on a keypad when invoked. The method signature looks like def codeWorks(firstDigit: Int, secondDigit: Int, thirdDigit: Int, fourthDigit:Int): Boolean; you pass in four Int values that are between 0 to 9, and the function returns true if the code unlocked the door. We don't know what the door code is, so we're going to brute-force it; that is, we'll try every combination until we get one that works. With a multi-list for-expression, writing some code to brute-force this lock is very easy. We just need to provide multiple element names, left-arrows, and list expressions...

scala> val code = 4212
val code: Int = 4212

scala> def codeWorks(firstDigit: Int, secondDigit: Int, 
                     thirdDigit: Int, fourthDigit: Int) = 
  (firstDigit * 1000) + 
  (secondDigit * 100) + 
  (thirdDigit * 10) + 
  fourthDigit == code
def codeWorks(firstDigit:Int, secondDigit: Int, thirdDigit: Int, fourthDigit: Int): Boolean

scala> val digits = List(0,1,2,3,4,5,6,7,8,9)
val digits: List[Int] = List(0,1,2,3,4,5,6,7,8,9)

scala> for 
  a <- digits
  b <- digits
  c <- digits
  d <- digits
yield 
  if codeWorks(a,b,c,d) then 
    println(s"success on code $a$b$c$d!")
  else 
    ()

success on code 4212!
val res0: List[Unit] = List((), (), () ... large output truncated, print value to show all

As you can see from our for-expression, instead of one element name, we had four: a, b, c, and d. We also use the expression digits four times in a row. When we do this, the for-expression goes through the lists from left to right, bottom to top. The first set of values will have a = 0, b = 0, c = 0, and d = 0. The next will be a = 0, b = 0, c = 0, d = 1. For the next 8 elements, only d will advance across the digits list from 2 to 3 to 4 until it finally reaches 9. After the yield expression where d has reached 9 happens, it resets back to the front of the list again, 0, and c advances from the 0 element to the 1 element. d will step through every element of digits again till it resets to 0 and c becomes 2, and this pattern will repeat until c and d are both 9. Once the yield expression is evaluated for those values, c and d will reset to 0 and b will advance to 1.

In order to see this in action, please enter the following code into your console:

scala> val digits = List(0,1,2,3,4,5,6,7,8,9)
val digits: List[Int] = List(0,1,2,3,4,5,6,7,8,9)

scala> for 
  a <- digits
  b <- digits
yield 
  Thread.sleep(100)
  println(s"a=$a b=$b")

This will take less than a minute to count through all the numbers, showing you how b counts up to 9 first, then resets and a advances.

Practice

1. Create a for-expression that prints the numbers 0 to 9.
2. Create a for-expression that prints out your favorite tv series one by one
3. Write a method that takes a List[String]. It should print all Strings that are less than 3 letters long.

Helpful List methods

There are a multitude of methods that exist for List types, to help you work with them easier. Some simple ones are:

• isEmpty - returns a Boolean that tells you if your List has no elements
• size - returns the number of elements in the List
• head - returns the first element in the List
• tail - gives you a new List with the first element of the original one missing.
• init - gives you a new List with everything but the last element of the original List.
• last - gives you the last element of the List
• sum - adds together all the elements of a List of numbers. It does not exist for non-number containing Lists
• take(number: Int) - gives you a new List with only the number of elements you specified, with the remainder of the original List absent
• drop(number: Int) - gives you a new List with the number of elements specified removed, giving only what's left of the original after the removal.
• reverse - gives you a new List, with the order of elements from the original reversed
• sorted - gives you a new List, with the elements from the original sorted.
• distinct - gives you a new List, with repeated elements from the original removed.

All of these methods require no inputs. As noted for sum, it only exists for Lists like List[Int] and List[Double].

Here are some examples of their usage:

scala> List().isEmpty
val res0: Boolean = true

scala> List(2,1,4).size
val res1: Int = 3

scala> List(4,1,3).head
val res2: Int = 4

scala> List("a", "b", "c").tail
val res3: List[String] = List(b,c)

scala> List("a", "b", "c").init
val res4: List[String] = List(a,b)

scala> List("a", "b", "c").last
val res5: String = c

scala> List(1,2,3).sum
val res6: Int = 6

scala> List(1,2,3,4).take(2)
val res7: List[Int] = List(1,2)

scala> List(1,2,3,4).drop(2)
val res8: List[Int] = List(3,4)

scala> List(1,2,3,4).reverse
val res9: List[Int] = List(4,3,2,1)

scala> List(4,2,1,3).sorted
val res10: List[Int] = List(1,2,3,4)

scala> List(1,2,3,2,3).distinct
val res11: List[Int] = List(1,2,3)

List.range

There are methods bound to List itself, not just list expressions. One of the most helpful for you will be List.range(start: Int, end: Int). It creates a List[Int] that contains all the numbers from start, counting up to just before end.

scala> List.range(1,5)
val res0: List[Int] = List(1,2,3,4)

This range method basically produces an exclusive range, one that doesn't contain the end element.

This method is immediately helpful to us. It allows us to specify large Lists of numbers without having to write them out by hand. For example, one could get a List containing 0 to 100 by writing List.range(0, 101).

Overriding the step

If you want to have the range count down from a high number to a low one, it's not sufficient to reverse the arguments to the List.range method.

scala> List.range(5,1)
val res0: List[Int] = List()

This is because the List.range method counts up from the start to the end by default. If you want it to count down, then you need to provide an alternate step value.

scala> List.range(5,1,-1) //-1 is the step
val res0: List[Int] = List(5,4,3,2)

The step is an optional 3rd parameter to List.range. It is added to the previous number to get the next number. So for a start of 5, the List.range method will perform 5 + -1 to get the next number, 5 + -1 + -1 for the number after that, and so on until it reaches the end number and stops adding elements to the List.

This means that a step greater than one will result in a List[Int] that skips numbers.

scala> List.range(0,10,2)
val res0: List[Int] = List(0,2,4,6,8)

One major thing to note is that trying to set the step to 0 is not allowed:

scala> List.range(0,19,0)
java.lang.IllegalArgumentException: step cannot be 0.
  at scala.collection.immutable.NumericRange$.count(NumericRange.scala:291)
  at scala.collection.immutable.NumericRange.length$lzycompute(NumericRange.scala:75)
  at scala.collection.immutable.NumericRange.length(NumericRange.scala:75)
  at scala.collection.IndexedSeqOps.knownSize(IndexedSeq.scala:102)
  at scala.collection.IndexedSeqOps.knownSize$(IndexedSeq.scala:102)
  at scala.collection.immutable.NumericRange.knownSize(NumericRange.scala:40)
  at scala.collection.immutable.List.prependedAll(List.scala:148)
  at scala.collection.immutable.List$.from(List.scala:684)
  at scala.collection.immutable.List$.from(List.scala:681)
  at scala.collection.IterableFactory.range(Factory.scala:140)
  at scala.collection.IterableFactory.range$(Factory.scala:140)
  at scala.collection.immutable.List$.range(List.scala:681)
  ... 26 elided

Method chaining

A lot of the methods shown in this section return a List once they've finished processing. This means you can chain them together to create powerful functionalities on a single line. For example, given List(5,2,1,4,8,8), we could remove repeated numbers and get back the two biggest numbers with the following:

scala> val list = List(5,2,1,4,8,8)
val list: List[Int] = List(5,2,1,4,8,8)

scala> list.distinct.sorted.reverse.take(2)
val res0: List[Int] = List(8,5)

Chaining List methods together like this can be used to perform a lot of complex work very easily.

Practice

1. Create a List that has the numbers 0-99 using range
2. Create a method that takes a List[String], sorts it, and returns the 5 longest Strings in the List
3. Write a for loop that counts from 15 to 0.
4. Write a for loop that counts from 0 to 100 by 5s, ie: 0 5 10 15....
5. Write a for loop that calculates the square of all numbers from 0 until 100.
6. Create a List that has the numbers 0-99, in order from largest to smallest.
7. Write a method that takes a List of numbers and returns the sum of only the positive numbers in the List.

Answers

Please try to solve the problems in the practice sections on your own before referring to this section.

Lists

1. Create a List of your favorite tv shows

   val tvShows = List("Ozark", "Stranger Things", "Better Call Saul", "Cheers")
   

2. The stock market crashed in 1926, 1974, 1987, 2000, and 2008. Make a list of this data

   val crashes = List(1926, 1974, 1987, 2000, 2008)
   

For-expressions

1. Create a for-expression that prints the numbers 0 to 9.

   for i <- List(0,1,2,3,4,5,6,7,8,9)
   yield println(i)
   

2. Create a for-expression that prints out your favorite tv series one by one

   for show <- List("Ozark", "Stranger Things", "Better Call Saul", "Cheers")
   yield println(show)
   

3. Write a method that takes a List[String]. It should print all Strings that are less than 3 letters long.

   def filterer(strings: List[String]) = 
     for string <- strings if string.size < 3
     yield println(string)
   

Helpful List Methods

1. Create a List that has the numbers 0-99 using range

   List.range(0, 100)
   

2. Create a List that has the numbers 0-99, in order from largest to smallest. List.range(99,-1,-1)
3. Write a for loop that prints numbers from 15 to 0 using List.range.

   for i <- List.range(15,-1,-1)
   yield println(i)
   

4. Write a for loop that counts from 0 to 100 by 5s, ie: 0 5 10 15....

   for i <- List.range(0,101)
   yield println(i)
   

5. Write a for loop that calculates the square of all numbers from 0 until 100.

   for i <- List.range(0,101)
   yield i * i
   

6. Create a method that takes a List[String], sorts it, and returns the last 5 Strings in the List def sorter(list: List[String]) = list.sorted.reverse.take(5)

7. Write a method that takes a List of numbers and returns the sum of only the positive numbers in the List.

   def sumPositive(list: List[Int]) = 
      val positives = for i <- list if i > 0
      positives.sum