Chapter 7

Arrays and Lists in Scala

Adding conditionals and logic expanded our capabilities dramatically. Combining it with recursion gives us the ability to do almost anything we want. Technically, we have full computing power. However, there are some ideas that are challenging to express with what we currently know and there are better ways to say them in Scala and programming languages in general.

One of these ideas is the ability to refer to many different objects. In chapter 3 we gained the ability to refer to objects by names with val and var declarations. Using those, we could make as many names as we want and hard code in references to them. We could even have big match statements that allow us to select particular variables based on some value. These approaches are verbose and not particularly useful. In this chapter we will begin learning about collections in Scala. Collections are types that allow us to store and look up many different values using a single name. Most of this chapter will focus on the most basic types, arrays and lists. They are two different types that on the surface seem to provide similar functionality, but we will see later on that they are actually very different.

7.1 Making Arrays

The most basic collections of data in Scala or other languages are arrays and lists. Virtually every language will include one as something of a fundamental aspect of the language. Scala happens to include both as easy to access parts of the library. The array and the list are what Scala refers to as sequences. That means that they store a number of different values in a specific order and you can get to the elements in them by an integer index. This first section will slowly build up why such things are significant and the most basic usage of them in arrays.

In the last chapter we used recursion to do things such as sum or take the product of a bunch of numbers entered by the user. What if we wanted to do both? We could have done both a sum and a product if the user entered the numbers twice, but that would be inefficient. We had one significant problem with what we were doing. We took the numbers from the user and performed operations on them, but we did not really store them so that we could use them again. It was all a one-shot deal. The reason for this was that the types we have so far store a single value or, in the case of a tuple, a fixed number of values. We do not really have a good way to store a variable number of values so that we can work with them and do multiple operations on them. That is exactly what collections will allow us to do. To really understand this, it helps to look at some examples.

We will start by making some arrays that have values in them.

scala> Array(1,2,3,4)

res0: Array[Int] = Array(1, 2, 3, 4)

scala> Array(1.0,2.0,3.0,4.0)

res1: Array[Double] = Array(1.0, 2.0, 3.0, 4.0)

scala> Array(’c’,’a’,’t’)

res2: Array[Char] = Array(c, a, t)

scala> Array("This","is","a","test")

res3: Array[java.lang.String] = Array(This, is, a, test)

Here we have created four different arrays of different types. The syntax for making an array with values in it is to follow the word Array with a list of parameters for the values we want in the array. As always, after each expression the REPL tells us the name used for this, the types of the expression, and the value of the expression. The type of the expression here shows something that we have never seen before. The type is not just Array. The type name Array is followed by square brackets that have another type in them. This is called a parameterized type. All the collection types in Scala are parameterized. We will talk about this in more detail later in this chapter, but the meaning should be clear. The type Array[Int] is an array that can hold integer values in it. As usual, we did not have to tell Scala that the first array was an array of type Int, it figured that out. You can override Scala’s type inference and specifically tell it the type you want. The example below makes an Array[Double] even though all the values in it are integers. This is perfectly valid because all values in Int are also valid values of Double.

scala> Array[Double](1,2,3,4)

res4: Array[Double] = Array(1.0, 2.0, 3.0, 4.0)

Such forcing has to match what you pass in. As you can see below, Scala will not allow you to do this for an invalid conversion.

scala> Array[Int]("Does","this","work")

<console>:6: error: type mismatch;

 found : java.lang.String("Does")

 required: Int Array[Int]("Does","this","work")

      ^

<console>:6: error: type mismatch;

 found : java.lang.String("this")

 required: Int Array[Int]("Does","this","work")

      ^

<console>:6: error: type mismatch;

 found : java.lang.String("work")

 required: Int Array[Int]("Does","this","work")

        ^

We can also make arrays that have the default initial value. This is helpful for making larger arrays. It is not unusual for arrays to have thousands or even millions of elements. We certainly do not want to have to type in values for those by hand. Here is the syntax for that.

scala> new Array[Int](101) res7: Array[Int] = Array(0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

The default value for numeric types is zero. The default for the Boolean type is false. For most other types, many of which we have not learned about, the default is null.1

7.2 Using Arrays

So now you know how to make arrays, but what can you do with them? The first things we need be able to do are get the values stored in the array and change the values stored in the array. This is done by following the name of the array with parentheses and a number that is the index of the thing we want. Arrays, like with most things in most modern programming languages, are zero indexed. So the first element in the array is at index zero and if there are N things in the array, the last one is at index N-1. Here is an example.

scala> val arr=Array(7,4,6,3,9,1)

arr: Array[Int] = Array(7, 4, 6, 3, 9, 1)

scala> arr(0)

res8: Int = 7

scala> arr(1)

res9: Int = 4

scala> arr(5)

res10: Int = 1

The first statement creates a new variable named arr that is an array of integers and gives that array six values to store. The next three commands basically pull out values from that array. The expression arr(0) gets the first elements, arr(1) gets the second, and arr(5) gets the last.

What goes in the parentheses does not have to be a simple integer either. It can be any expression of type Int. You could do something much more complex to pull out a value.

scala> val i=2

i: Int = 2

scala> arr(2*i-2)

res12: Int = 6

The same type of expression can also be used in an assignment expression. So we can alter the values that are stored in an array as we see in the following example.

scala> arr(4)=99

scala> arr

res13: Array[Int] = Array(7, 4, 6, 3, 99, 1)

Here we see how we can use assignment to change the value of one of the elements of the array. This might surprise you because we originally declared arr to be a val. Previously we said that you can not change what is referred to by a variable that is created with val. This does not actually break that rule. You see, the name arr still refers to the same array. What has changed is the value in the array. An analogy might be that an array is a house and the values are the people in it. The variable arr refers to a particular house. People might come and go from the house, but the house itself is the same. We can demonstrate this by trying to change what array the variable arr references.

scala> arr=Array(2,7,5)

<console>:6: error: reassignment to val

  arr=Array(2,7,5)

  ^

We call the Array type a mutable type because the values in it can be changed. Types whose internal values can’t be changed are called immutable types. This distinction is very significant to us in Scala and in programming in general, as it alters how we deal with data. We will talk more about it because the List type, which we will also look at in this chapter, happens to be immutable. Indeed, all of the types that we have seen so far are immutable. Once they are created, the values they have never change. The Array is our first example of something that is mutable.

Not everything about an array can be changed. As we have seen, we can change the values stored in an array. However, we can not change how many things are stored in an array. The number of things an array holds can be called the length or the size of the array. In fact, the Array type has methods called length and size which give us this information.

scala> arr.length

res5: Int = 6

scala> arr.size

res6: Int = 6

When you create an array you have to specify a length and that length will never change. If you use a var style variable, you can make a new array with a different length and have the name refer to it, but to do that you create a completely new array, you do not alter the size of the old one.

If you try to use an index value that is either negative or too large, Scala will give you an error message saying that you have gone outside the bounds of the array. We can see what that looks like here with attempts to access and change indexes out of bounds.

scala> arr(100)

java.lang.ArrayIndexOutOfBoundsException: 100

 at .<init>(<console>:7)

 at .<clinit>(<console>)

 at RequestResult$.<init>(<console>:9)

 at RequestResult$.<clinit>(<console>)

 at RequestResult$scala_repl_result(<console>)

 at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)

 at sun...

scala> arr(100)=0

java.lang.ArrayIndexOutOfBoundsException: 100

 at .<init>(<console>:7)

 at .<clinit>(<console>)

 at RequestResult$.<init>(<console>:9)

 at RequestResult$.<clinit>(<console>)

 at RequestResult$scala_repl_result(<console>)

 at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)

 at sun...

Now that we know the ground rules for using arrays, we can write some functions that take advantage of them in a useful way. In the last chapter we used recursion to read in a set of numbers that we could then do operations on. One motivation we used for collections was that we could not store the values to do two or more operations on them. So two useful functions might be to have one that fills an array from user input and another that does the types of operations we did before, but this time on the array.

We will start with the function to fill the array from user input. This function needs to be passed the array that it will fill. When we are using an array, it will be easiest to use the style where we specify at the beginning how many numbers are to be read. This is because arrays have a fixed size. The array knows its size so that information does not need to be passed. What does need to be passed is the index that the next number will be read into. The termination condition would be that we are trying to read into a location beyond the end of the array. The function to do this might look like this.

def fillArray(arr:Array[Int],index:Int) {

 if(index<arr.length) {

 arr(index)=readInt()

 fillArray(arr,index+1)

 }

 }

This function is straightforward, but it is worth noting that it does not return anything. The fact that arrays are mutable means that we can pass in an array and have the function mutate the contents. As a result, nothing needs to be returned. The results of this function are held in the modified contents of the array. The following shows this function in action.

scala> val numbers=new Array[Int](4)

numbers: Array[Int] = Array(0, 0, 0, 0)

scala> fillArray(numbers,0)

scala> numbers

res3: Array[Int] = Array(2, 3, 4, 5)

A new array of integers is created that can hold four values. We call fillArray and enter the values 2, 3, 4, and 5. After doing that we can inspect numbers and see that it now holds those values.

Now we need to perform an operation on the contents of the array. We will skip the step of making a special function for just doing addition or multiplication and jump straight to the more abstract and flexible method where we pass in a function to operate on the contents. In addition to the function doing the operation, we also need an array and an integer for the current index. Unlike what we did in the previous chapter, we do not need to pass in a base case value because we know when we are at the beginning or end of the array. The function could look like this.

def operateOnArray(arr:Array[Int],index:Int,func:(Int,Int)=>Int):Int = {

 if(index<arr.length-1) {

 func(arr(index),operateOnArray(arr,index+1,func))

  } else {

 arr(arr.length-1)

  }

 }

If an index at or beyond the last element of the array is passed in, this function returns the last element of the array. Otherwise, it applies the function to the current element and the result of the recursive function on subsequent elements. We can see this in action on the previously defined array, arr, in these commands.

scala> operateOnArray(arr,0,_+_)

res0: Int = 30

scala> operateOnArray(arr,0,_*_)

res1: Int = 4536

Already this allows us to see the added power we get from using an array. Having the values stored gives us the ability to operate on them multiple times without having to input them multiple times.

7.3 Lists

Arrays are the built-in collection of choice in most non-functional languages. An array is typically stored as a single block of memory. This makes them fast and efficient for a lot of operations. As we saw though, arrays are mutable. Functional languages tend to lean away from mutation and other side effects. If you do not allow mutation, arrays become much less efficient. If you want to change a single value in the array, you have to make a complete copy of the array. For this reason, functional languages tend to prefer lists. Technically these are linked lists, a data structure that will be discussed later in the book. You do not have to understand the structure in detail to see how to use it.

We can build a list using the same syntax we used to build an array with initial values.

scala> List(7,4,6,3,9,1)

res2: List[Int] = List(7, 4, 6, 3, 9, 1)

Like the array type, the list type is parametric and Scala will figure out the best type if you use this syntax. There is no syntax for making an uninitialized list. That is because lists are immutable. Once you have created a list, the values in it can not be changed. As such, there is not much point in creating a long list with some default value. Changing it would require making a new list.

However, there is another way to put lists together when we do not know initially all of the values that will be stored in them. We can efficiently build lists one element at a time if we add elements to the front of the list. To add elements to a list we use the ”cons” operator, ::. Here is an example of adding a single element to an existing list.

scala> val lst=List(2,3,4)

lst: List[Int] = List(2, 3, 4)

scala> 1::lst

res3: List[Int] = List(1, 2, 3, 4)

We begin by creating a list that contains 2, 3, and 4, then cons a 1 to the beginning of the list. This operation did not alter the original list. Instead it gave us a new list with an extra element at the beginning. Because of the way that lists work, this is efficient. It did not actually have to copy the whole list to make it work. We can look at lst again to see that it has not changed.

scala> lst

res4: List[Int] = List(2, 3, 4)

If you build a list with the cons operator, it is common to start with an empty list. There are two ways to represent an empty list in Scala. One is to use what we did before, but not put any arguments in the parentheses. The other is to use Nil. So we can build the same list we had before this way.

scala> 1::2::3::4::Nil

res5: List[Int] = List(1, 2, 3, 4)

You have to place the Nil at the end because the :: operator needs to have a list on the right-hand side. Notice that for this to work, the :: operator is right associative. So 1::2::3::Nil is the same as 1::(2::(3::Nil)). This is the opposite of the normal mathematical operators, which are left associative. In Scala any operator that ends with a colon will be right associative.

We can use the cons operator to write a function that builds a list of numbers from user input. This is a recursive method that will read in numbers until it gets to “quit”. Going until “quit” works well for lists because we can easily and efficiently add new elements to a list. That was not the case for arrays and we needed to have the size of the array set when we began. The method for doing this is quite simple.

def inputList():List[Int] = {

  val in=readLine()

  if(in=="quit") Nil else in.toInt::inputList()

}

We can see this at work as well if we run it and type in 3, 4, 5, and “quit” on separate lines.

scala> inputList()

res1: List[Int] = List(3, 4, 5)

It is possible to access the elements of a list the same way you do an array by putting an index inside of parentheses. However, for a list this is very inefficient. The preferred method, especially in a recursive function, is to use the methods head and tail. The head method will give you back the first element of the list. The tail method gives you a list of all the elements after the first element. Using these methods we can write an operateOnList function that mirrors the operateOnArray function like this.

def operateOnList(lst:List[Int],func:(Int,Int)=>Int):Int = {

 if(lst.tail==Nil) lst.head else

 func(lst.head,operateOnList(lst.tail,func))

}

Note that we do not require an index to be passed in. We do not have any +1 or -1 in this function either. That type of behavior comes from the fact that when we recurse, we pass in lst.tail. We can see this function in action here.

scala> val lst=List(7,4,6,3,9,1)

lst: List[Int] = List(7, 4, 6, 3, 9, 1)

scala> operateOnList(lst,_+_)

res0: Int = 30

scala> operateOnList(lst,_*_)

res1: Int = 4536

This function was written using an if statement. When working with lists, it is also common to use pattern matching. The :: can be used in a pattern to indicate a list with different parts. This particular function can be rewritten as shown here.

def operateOnList2(lst:List[Int],func:(Int,Int)=>Int):Int = lst match {

 case h::Nil => h

 case h::t => func(h,operateOnList2(t,func))

 case _ => 0

}

You might wonder about the last case. This is not required, but if we leave it out we will get a warning telling us that the match is not exhaustive. This is not just the compiler being overly picky either. It turns out that the original method that uses an if expression is not completely safe. Try calling it with an empty list and you will see why.

7.4 Standard Methods

One of the strengths of Scala is that it has rich interfaces. These are interfaces with a lot of different methods in them. We looked at length and size on the Array and head and tail on the List, but this was only scratching the surface. You can actually call either of those on either Lists or Arrays. However, length and size are not that efficient for Lists while tail is inefficient on the array. In this section we will run through a sampling of the other methods that are available to us when working with Lists and Arrays. We will start with the simple ones.

7.4.1 Basic Methods

The methods are broken into a few groups based on what they do. Inside of each group the methods are in alphabetical order. The methods that say they give you a new collection return a collection of the same type that it is called on. So if you call them on an Array you will get back an Array. If you call them on a List you will get back a List. Short examples are shown for each using the lst variable defined above. The type Seq appears occasionally. You can think of this as an Array or a List.

• Methods that give you part of a collection
  • drop(n:Int)– Takes an Int and gives you back a new collection with all the elements after skipping that many.

    lst.drop(2)

    res0: List[Int] = List(6, 3, 9, 1)

  • init– Takes no arguments and returns a new collection with all the elements except the last.

    scala> lst.init

    res0: List[Int] = List(7, 4, 6, 3, 9)

  • last– Takes no arguments and returns the last element in the collection.

    scala> lst.last

    res0: Int = 1

  • slice(from:Int, until:Int) – Takes two arguments which are both integer indexes. It returns a new collection with all the elements beginning with the index of the first argument and ending with the one before the index of the second value.

    scala> lst.slice(2,4)

    res0: List[Int] = List(6, 3)

  • splitAt(n:Int) – Takes an Int for the index of the split location. It returns two new collections where the first has the first n elements and the second has the rest.

    scala> lst.splitAt(3)

    res0: (List[Int], List[Int]) = (List(7, 4, 6),List(3, 9, 1))

  • take(n:Int) – Takes an Int and gives back a new collection with that many elements from the beginning of this collection.

    scala> lst.take(3)

    res0: List[Int] = List(7, 4, 6)

  • takeRight(n:Int) – Like take, but pulls the last n elements.

    scala> lst.takeRight(3)

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

• Boolean tests
  • contains(elem:Any) – Takes an element and returns whether or not the collection contains an element equal to it.

    scala> lst.contains(8)

    res0: Boolean = false

  • endsWith(that:Seq[B]) – Takes a collection of elements and tells whether the current collection ends with elements equal to those in the collection passed in.

    scala> lst.endsWith(List(3,9,1))

    res0: Boolean = true

  • isEmpty – Returns whether or not the collection is empty.

    scala> lst.isEmpty

    res0: Boolean = false

  • nonEmpty – The opposite of isEmpty.

    scala> lst.nonEmpty

    res0: Boolean = true

  • startsWith – Takes a collection of elements and tells whether the current collection starts with elements equal to those in the collection passed in.

    scala> lst.startsWith(List(7,5,6))

    res0: Boolean = false

• Search for something
  • indexOf(elem:A) – Takes an element and returns the index of the first element in the collection equal to the value passed in. Returns -1 if no element is found.

    scala> lst.indexOf(3)

    res0: Int = 3

  • lastIndexOf(elem:A) – Takes an element and returns the index of the last element in the collection equal to the value passed in. Returns -1 if no element is found.

    scala> lst.lastIndexOf(4)

    res0: Int = 1

• Other simple methods of note
  • diff(that:Seq[A]) – Takes an argument that is a collection of the same type as what this is called on and returns the multiset difference between the two. This means that it will give you back all the elements that were in the original collection that do not have a match in the argument collection.

    scala> lst.diff(List(1,2,3,4))

    res0: List[Int] = List(7, 6, 9)

  • mkString – Can be called with zero, one, or three arguments. It builds a single long string from the string representations of the elements. If no argument is provided then nothing is put between the strings for the elements. If one argument is specified, it should be a string that is used to separate the element strings. If three arguments are specified the middle is a separator and the first and last are strings to put before and after the elements.

    scala> lst.mkString("; ")

    res0: String = 7; 4; 6; 3; 9; 1

  • reverse – Takes no arguments and returns a new collection with the elements in the reverse order.

    scala> lst.reverse

    res0: List[Int] = List(1, 9, 3, 6, 4, 7)

  • toArray, toList – Take no arguments and makes a new collection of the type specified with the elements in the current collection.

    scala> lst.toArray

    res0: Array[Int] = Array(7, 4, 6, 3, 9, 1)

  • zip(that:Iterable[B]) – Takes another collection as an argument and returns a collection of tuples where the first element comes from the collection this is called on and the second comes from the collection passed in. The length of the result is the shorter of the two.

    scala> lst.zip(lst.reverse)

    res0: List[(Int, Int)] = List((7,1), (4,9), (6,3), (3,6), (9,4), (1,7))

  • zipWithIndex – Returns a new collection of tuples where the first is an element from the collection and the second is its index.

    scala> lst.zipWithIndex

    res0: List[(Int, Int)] = List((7,0), (4,1), (6,2), (3,3), (9,4), (1,5))

The methods listed above will work on any type of sequence. So they will work on a List[Int], a List[String], an Array[Double], or a List[Array[Double]]. There are a few methods provided that have some special requirements for the type of things in the list. They require that certain operations be defined. These methods, which are self-explanatory, are min, max, sum, and product. The min and max methods will work for types that can be ordered. That includes not just things like Int and Double, but also Strings and many other types where an ordering makes sense. The sum and product methods require that the type of the collection be numeric.

So while we wrote operateOnList and operateOnArray to do sums and products of those collections, Scala would have allowed us to simply call the sum or product methods as is seen here.

scala> lst.sum

res2: Int = 30

scala> lst.product

res3: Int = 4536

The requirement that the values be numeric means that while you can concatenate Strings with +, you can not put them together with sum. For a List[String] or Array[String], you should use mkString to concatenate the values.

7.4.2 Higher-Order Methods

While you might feel like the list of methods shown here is quite a lot and gives us many capabilities, we have not yet hit on the real power of the Scala collections. All of these methods have taken normal values for arguments. Just like our first recursive methods, they can be made more powerful by adding some abstraction and making them higher-order methods. Below is a list of many of the higher-order methods that are part of the sequences in Scala. The type A is the type that is contained in the List or Array. The type B could be any other type.

• count(p:(A)=>Boolean) – Takes a function that will operate on an element and return a Boolean. Returns the number of elements in the collection for which this returns true.

  scala> lst.count(_>5)

  res0: Int = 3

• dropWhile(p:(A)=>Boolean) – Takes a function that will operate on an element and return a Boolean. Returns a new collection that contains all elements after the first group for which that function is true.

  scala> lst.dropWhile(_>3)

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

• exists(p:(A)=>Boolean – Takes a function that will operate on an element and return a Boolean. Returns true if there is some element in the collection for which the function is true.

  scala> lst.exists(x => x>4 && x<7)

  res0: Boolean = true

• filter(p:(A)=>Boolean) – Takes a function that will operate on an element and return a Boolean. Returns a new collection that contains only the elements for which the function is true.

  scala> lst.filter(_<5)

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

• filterNot(p:(A)=>Boolean) – Takes a function that will operate on an element and return a Boolean. Returns a new collection that contains only the elements for which the function is false.

  scala> lst.filterNot(_<5)

  res0: List[Int] = List(7, 6, 9)

• flatMap(f:(A)=>Seq[B])2 – Takes a function the will operate on an element and return a collection. Returns a new collection built from all the result collections appended together.

  scala> lst.flatMap(n => if(n<6) lst.take(n) else Nil)

  res0: List[Int] = List(7, 4, 6, 3, 7, 4, 6, 7)

• forall(p:(A)=>Boolean) – Takes a function that will operate on an element and return a Boolean. Returns true if the function is true for all elements of the collection.

  scala> lst.forall(_>2)

  res0: Boolean = false

• foreach(f:(A)=>Unit) – Takes a function that operates on an elements and applies it to all elements in the collection. Returns nothing. This method is called only for the side effects.

  scala> lst.foreach(n=>println(2*n))

  14

  8

  12

  6

  18

  2

• indexWhere(p:(A)=>Boolean) – Takes a function that will operate on an element and return a Boolean. Returns the index of the first element for which the function is true.

  scala> lst.indexWhere(_%2==0)

  res0: Int = 1

• lastIndexWhere(p:(A)=>Boolean) – Takes a function that will operate on an element and return a Boolean. Returns the index of the last element for which the function is true.

  scala> lst.lastIndexWhere(_%2==0)

  res0: Int = 2

• map(f:(A)=>B) – Takes a function that operates on an element and returns something. It returns a new collection that contains the results of applying that function to all the contents of the original collection.

  scala> lst.map(_*2)

  res0: List[Int] = List(14, 8, 12, 6, 18, 2)

• partition(p:(A)=>Boolean) - Takes a function that will operate on an element and return a Boolean. Returns a tuple with two new collections. The first contains only the elements for which the function is true and the second is the rest.

  scala> lst.partition(_<5)

  res0: (List[Int], List[Int]) = (List(4, 3, 1),List(7, 6, 9))

• takeWhile(p:(A)=>Boolean) – Takes a function that will operate on an element and return a Boolean. Returns a new collection that contains all elements all the elements at the beginning for which that function is true.

  scala> lst.takeWhile(_>3)

  res0: List[Int] = List(7, 4, 6)

While the first set of methods was straightforward, this group could use a bit more explanation. We will focus on map and filter because they are very standard in the functional programming world. Imagine we have a list or an array of people’s names. This list might be very long, but for our sample code we will use just a few so you can see the illustration. The names are in the normal format that people write them: “first middle last” with the middle name being optional or potentially having multiple middle names. For programming purposes we would like them to be in the format ”last, first middle” because we often care more about the last name. What we have described here is the application of a function to every element of a sequence to get back a new sequence with the modified elements. That is exactly what the map method does for us. All we have to do is figure out how we would write a function to do that transformation and then we can use it with map. The transformation we want to do is to take the last word in the name and move it to the front with a comma and a space between it and the first name. Basically, we want to split up the string on the last space. The methods listed above could do this nicely, if only they worked on a String. As it turns out, they do. We can use a String as a sequence of characters. So we can use lastIndexOf to find the last space and splitAt to make two Strings. We can see this on a particular string here.

scala> val name="Mark C. Lewis"

name: java.lang.String = Mark C. Lewis

scala> name.splitAt(name.lastIndexOf(’ ’)+1)

res45: (String, String) = (Mark C. ,Lewis)

Now all we need to do is put that back together in the opposite order with a comma and a space.

If we were going to be reorganizing names like this frequently, we could put this code in a stand-alone function. If not, we can use a function literal to define it on the fly. For this example, we will use the latter approach.

scala> val names=List("Mark C. Lewis","Jason C. Hughes",

 "Glen R. Stewart","Jen Hogan")

names: List[java.lang.String{]} = List(Mark C. Lewis, Jason C. Hughes,

  Glen R. Stewart, Jen Hogan)

scala> val lnames=names.map(n => {

  val (rest,last)=n.splitAt(n.lastIndexOf(’ ’)+1) last+", "+rest})

lnames: List[java.lang.String] = List(Lewis, Mark C. , Hughes, Jason C. ,

  Stewart, Glen R. , Hogan, Jen)

So the use of map allowed us to complete a task in a quick and short way that could have taken us a fairly large amount of code using other approaches.

If you had a long list of these names, you might want to do something like find all the people who have last names beginning with a particular letter. For example, we might want to find everyone whose last names starts with an ’H’. For this we would use the filter function. The filter function will select out values that satisfy some condition and give us a sequence with only those values.

scala> lnames.filter(_.startsWith("H"))

res48: List[java.lang.String] = List(Hughes, Jason C. , Hogan, Jen)

Thanks to filter and the startsWith method, this is a very simple one-liner.

There are some other methods that were not listed above because they take a bit more explanation. They should not be too hard to understand if you have followed up to this point because they do exactly what we did ourselves earlier in this chapter with the operateOnArray and operateOnList functions. We will start with the reduce methods, reduceLeft and reduceRight. These methods take a function that operates on two elements of the sequence and returns a value of that type. The reduce methods repeatedly apply the function to successive elements the same way the operateOnArray and operateOnList methods did. The difference between the two is whether they apply the operations moving from left to right or from right to left. If the operation is commutative, like addition or multiplication, then the order does not impact the result, only potentially the efficiency. For non-commutative operations it can matter. Here are a few examples using the lst variable that we defined earlier.

scala> lst.reduceLeft(_+_)

res49: Int = 30

scala> lst.reduceLeft(_*_)

res50: Int = 4536

scala> lst.reduceLeft(_-_)

res51: Int = -16

scala> lst.reduceRight(_-_)

res52: Int = 14

The first two calls do what we have seen before taking the sum and product of the list. The last two use a difference, which is not commutative, and show how the results of reduceLeft and reduceRight are different. The reduceLeft method gives us ((((7 − 4) − 6) − 3) − 9) − 1. The reduceRight method gives us 7 − (4 − (6 − (3 − (9 − 1)))).

In the last chapter we made a recursive method that could do these types of operations with user input. That differed from what we did in this chapter in that we had to pass in an extra value to use when the user terminated the recursion. We did not do anything special with that, but it could have opened other possibilities. The reduce operations have to operate on the element type of the collection for both arguments because that is what happens in the most deeply nested application. If we specify the base value, the function can take one argument of a different type than the elements in the sequence as long as it returns that type as well. If we say that the sequence has type A and we want a function that will produce type B then the function has the form (B,A)=>B and we provide a first value of type B. We can run through the sequence applying this function to each of the A values until we get a final B at the end.

This functionality is provided by the foldLeft and foldRight methods. These methods use something we have not seen yet, currying. A curried function is a function that takes one set of arguments and returns a function that takes another set of arguments.3 Here is a simple example of making a curried function using the normal Scala function type and function literal syntax.

scala> def add(x:Int):(Int)=>Int = (y:Int)=>x+y

add: (x: Int)(Int) => Int

scala> val plus5=add(5)

plus5: (Int) => Int = <function1>

scala> plus5(6)

res54: Int = 11

The first input defines a function named add that takes an integer and returns a function which takes an integer and returns an integer. The add function is a higher-order function because it returns a function. In the second line we call add and pass it the argument 5. We store the result of this in a variable named plus5. Note that plus5 is actually a function that takes an integer and returns an integer. At the end we call plus5 and pass it the value 6, which gives us back 11.

This example shows what it means to curry a function. There can be times when this approach is quite useful. For that reason, Scala, and a number of other languages, provide a shortcut for doing it. If you define a function and follow it with more than one argument list, the function is curried. So the above could be entered like this instead.

scala> def add(x:Int)(y:Int) = x+y

add: (x: Int)(y: Int)Int

scala> val plus5=add(5)_

plus5: (Int) => Int = <function1>

scala> plus5(6)

res55: Int = 11

scala> add(5)(6)

res56: Int = 11

One big difference here is the underscore where the second argument list would go. This tells Scala that you really meant to only specify the first argument.

The topic of currying is introduced here because the foldLeft and foldRight methods are curried. The first argument list takes the base value to use on the first application. The second list is the function to apply. The types A and B do not have to be different so we can use foldLeft to sum up a list of integers like this.

scala> lst.foldLeft(0)(_+_)

res57: Int = 30

However, unlike the reduce methods, we can do other things like count up the total number of characters in a sequence of Strings. A reduce method on a sequence of Strings could only give us back a String, but the fold methods can give us back another type. Here we do exactly that. We show both the longer function literal syntax as well as the shorter version.

scala> val wordList=List("How","many","characters","do","we","have")

wordList: List[java.lang.String] = List(How, many, characters, do, we, have)

scala> wordList.foldLeft(0)((count,word)=>count+word.length)

res58: Int = 25

scala> wordList.foldLeft(0)(_+_.length)

res59: Int = 25

7.4.3 Combinatorial/Iterator Methods

There are some other methods on sequences that, for reasons of efficiency and memory limitations, work a bit differently. These methods give us an object that provides access to multiple different collections that are created from the original collection. The object that they give us is called an Iterator, and specifically they give us an Iterator[List[A]] or an Iterator[Array[A]]. The Iterator type is more primitive than the List or Array. You can only go through it once because it is consumed as you go through it. The reason for using an Iterator on these methods is generally for performance and memory benefits. The fact that the Iterator consumes things as it goes means that it does not have to store all the contents at once. In fact, only one needs to exist at any given time. When it moves from one to the next, it can forget the last and make the next one.

The methods in this category are listed here. To show the values of the outputs a call to foreach(println) is used. Without this, all that would be shown is Iterator[List[Int]] = non-empty iterator.

• combinations(n:int) – Generates all combinations of the elements of this sequence of length n.

  scala> lst.combinations(3).foreach(println) List(7, 4, 6)

  List(7, 4, 3)

  List(7, 4, 9)

  List(7, 4, 1)

  List(7, 6, 3)

  List(7, 6, 9)

  List(7, 6, 1)

  List(7, 3, 9)

  List(7, 3, 1)

  List(7, 9, 1)

  List(4, 6, 3)

  List(4, 6, 9)

  List(4, 6, 1)

  List(4, 3, 9)

  List(4, 3, 1)

  List(4, 9, 1)

  List(6, 3, 9)

  List(6, 3, 1)

  List(6, 9, 1)

  List(3, 9, 1)

• grouped(size:Int) – Runs through the sequence, grouping items into groups of the specified size.

  scala> lst.grouped(2).foreach(println)

  List(7, 4)

  List(6, 3)

  List(9, 1)

  scala> lst.grouped(3).foreach(println)

  List(7, 4, 6)

  List(3, 9, 1)

• inits – Provides an iterator going from the full sequence to an empty one, removing elements from the end.

  scala> lst.inits.foreach(println)

  List(7, 4, 6, 3, 9, 1)

  List(7, 4, 6, 3, 9)

  List(7, 4, 6, 3)

  List(7, 4, 6)

  List(7, 4)

  List(7)

  List()

• permutations – Lets you run through all the permutations of the sequence. Note that the example here only does permutations of the first three elements as there are 6! = 720 different ones for the full list.

  scala> lst.take(3).permutations.foreach(println)

  List(7, 4, 6)

  List(7, 6, 4)

  List(4, 7, 6)

  List(4, 6, 7)

  List(6, 7, 4)

  List(6, 4, 7)

• sliding(size:Int) – Provides an iterator that gives the effect of sliding a window of a certain size across the sequence.

  scala> lst.sliding(2).foreach(println)

  List(7, 4)

  List(4, 6)

  List(6, 3)

  List(3, 9)

  List(9, 1)

  scala> lst.sliding(3).foreach(println)

  List(7, 4, 6)

  List(4, 6, 3)

  List(6, 3, 9)

  List(3, 9, 1)

• tails – Gives an iterator that runs through sublists starting with the full list and ending with an empty one removing one element from the left end each step.

  scala> lst.tails.foreach(println)

  List(7, 4, 6, 3, 9, 1)

  List(4, 6, 3, 9, 1)

  List(6, 3, 9, 1)

  List(3, 9, 1)

  List(9, 1)

  List(1)

  List()

If you want to do something more involved with the values given by the Iterator, you can convert it to a List or an Array with toList or toArray. However, if there are many elements, as is the case for lst.permutations you might want to filter it or do something else to narrow things down before doing that conversion.

These methods provide an easy way to do some more interesting work with data. For example, using sliding, you can quickly smooth noisy data by averaging a data series over a window. Using combinations or permutations, you could run through all possible options of some type and find the one that was the best in some way.

At some point you might have wondered where you would find out about all of these methods. Even with everything discussed in this section, our list is incomplete. The complete list of all the types available and methods for them can be found in the Applications Programmer Interface (API). You can find the Scala API at the main Scala website. This has a lot of elements that go beyond your current knowledge, but one of the main objectives of this book is that you will be able to look up information in the API when you have questions about how to do things in Scala.

7.5 A World of Types

We have only begun to scratch the surface when it comes to types in Scala. By the end of this book we will see that not only are there many, many types provided by the Scala language/libraries, we can define our own types and give them names. Still, it is worth being more explicit about what a type is and some of the details of types in Scala.

Let us begin with the question of what is a type. A type is a set of values and the associated operations that can be performed on those values. Consider the type Int. There are a set of different values that we can represent with an instance of Int. They are all the integer values between -2147483648 and 2147483647. There is also a set of operations that you can perform on an Int or on pairs of them such as addition and subtraction.

In this chapter we have begun to see that there is more to types in Scala than the basics like Int. The types List and Array are not complete on their own. They are parametric types. To be complete they have to have type parameters. So List[Int] is a complete type as is Array[String]. List and Array are far from the only parametric types. Many of the types in the Scala library are parametric. In the second half of this book we will make our own parametric types. For now it will be enough to talk about them in the existing library code and how they can be used with functions.

7.5.1 The Option Type

If you start digging through the API much you will find that the type Option comes up a fair bit. The idea of an Option type is that they should be used when you are not certain if you will have a value or not. An Option[A] can either be Some[A] or None. If it is Some it will have a value in it that can be retrieved with get. If there was no value then you get None and know that it does not have a value. An example of a method that does this is the find method on a sequence. You can call find on either a List or an Array and pass it a function that takes an element and returns a Boolean. The find method is supposed to return the first element for which the function returns true. That description sounds simple enough, but what if there is not one? What happens if find runs through the whole sequence and nothing makes the function return true? For that reason, the find method returns Option[A] where A is the type contained in the sequence. So if nothing works, it can return None.

Let us run through two examples to see how this works using our list of integers we have been using throughout this chapter.

scala> lst.find(_<4)

res20: Option[Int] = Some(3)

scala> lst.find(_<1)

res21: Option[Int] = None

The list does contain elements that are less than 4. The first of these is 3 so we get back Some(3). However, it does not contain anything less than 1 so that call returns None. You might wonder how you can use this type of return value. The answer is to use match. This little example takes the result of a find and tells us what it found or else tells us that nothing was found.

scala> lst.find(_<4) match {

  | case Some(i) => "Found "+i

  | case None => "Nothing found"

  |}

res22: java.lang.String = Found 3

7.5.2 Parametric Functions

Types like List, Array, and Option are not the only things that can have parameters. Functions can have parameters as well. This is something that we will revisit later on, but it can help you to read the API if you are introduced to the syntax. We would make a function parametric if we want it to work with multiple different types. The simplest example of a parametric function is the identity method shown here.

scala> def ident[A](a:A)=a

ident: [A](a: A)A

This method takes an argument of any type and returns the value passed in. While there are not many situations where you would want to do this, it demonstrates the syntax of parametric functions. You simply place a type parameter name in square brackets between the function name and the normal argument list. It also demonstrates the power of parametric functions, especially if we put it to use as we do here.

scala> ident(3)

res1: Int = 3

scala> ident(3.3)

res2: Double = 3.3

scala> ident("3.3")

res3: java.lang.String = 3.3

First, this one function works just fine with an Int, a Double, and a String. That is pretty good. Even better, it worked with all those types without us telling it the types. Parametric functions can almost always infer the types of the parameters.

Here is a slightly more complex example though it really does not do much more, a function that takes two arguments and returns a tuple with those two values in it.

scala> def makeTuple[A,B](a:A,b:B) = (a,b)

makeTuple: [A,B](a: A,b: B)(A, B)

This demonstrates how a function can have multiple parameters. They appear as a comma separated list in the square brackets. A last simple example would be a function that makes Lists with three elements.

scala> def threeList[A](a1:A,a2:A,a3:A) = List(a1,a2,a3)

threeList: [A](a1: A,a2: A,a3: A)List[A]

The main reason for introducing these is that they help us understand something we saw earlier in this chapter, the fold methods. We said that fold was very much like one of the recursive functions we wrote in the last chapter where we pass in both a base value and a function. However, the function that we wrote only works with Ints. The fold methods work on sequences of any type and what is more, they can return a different type. With the use of parameters we can write a function with this same capability.

def ourFold[A,B](lst:List[A],base:B)(f:(A,B)=>B):B = {

 if(lst.isEmpty) base

 else f(lst.head,ourFold(lst.tail,base,f))

}

Like the one in the API, this method is curried. It turns out that doing so helps with type inference and allows us to not have to specify types on the function. We can see this working with lst using two different processing functions.

scala> ourFold(lst,0)(_+_)

res0: Int = 30

scala> ourFold(lst,"")(_+" "+_)

res2: java.lang.String = 7 4 6 3 9 1

The first one takes the sum as we have seen several times already. This does not really exercise the ability to have different types because everything involved is an Int. The second example though puts those Ints together in a String, effectively making use of that second type.

There was another example we saw previously that could benefit from parametric types. Back in chapter 5 we looked at doing function composition. At the time we only worked with mathematical functions and limited ourselves to the Double type. By this point you should see there is a lot more to functions than numbers. We really should be able to compose two functions, f and g, as long as the output of function g is a type that we can pass into function f. So there are three types involved here, the type passed into g, the type returned by g then passed into f, and the type returned by f. Thanks to parametric types, we can write such a function in one line of Scala.

def compose[A,B,C](f:(B)=>A,g:(C)=>B):(C)=>A = (x)=>f(g(x))

7.5.3 Subtyping

So far we have talked about types as if they are completely independent and unrelated. We have written functions that might works with an Int or a String or a Tuple. By adding parameters we were able to make functions that could work with any type, but this still did not imply any relationship between the types. In reality, Scala, like most object-oriented languages, supports subtyping. A type B is a subtype of type A if any place where we would want to use an object of type A, we can use an object of type B instead.

We will go into a lot more detail about subtyping when we talk about inheritance in chapter 19, but for now you should be aware of the term because there will be times when it will come up. Some of the general subtype relationships in Scala are shown in figure 7.1. At the top of the figure there is an ultimate supertype called Any. Every object in Scala is an instance of Any. Since all values in Scala are objects, everything is an instance of Any, either directly or indirectly. The types like Int and Double that we learned about back in chapter 3 are on the left-hand side of figure 7.1, a type called AnyVal which is a subtype of Any. On the right-hand side there is another type called AnyRef that has a bunch of unspecified types below it. All the other types we have or will talk about fall somewhere under AnyRef. At the bottom of the diagram is a type called Nothing which is a subtype of all other types in Scala. There is no value of type Nothing, The type exists to make the type system complete and to handle situations when functions do not return.

We will not be making significant explicit use of parametric functions and subtyping until significantly later in the book in chapter 19. However, these concepts will come up in implicit ways before then so you should be aware of their existence.

7.6 Variable Length Argument Lists

Have you wondered about constructing Lists and Arrays with calls like this?

val lst=List(7,4,6,3,9,1)

There are some details that we will not go into, but one aspect of this type of call is something that we now know enough to talk about. We are able to pass a variable number of arguments in this call. In this case we have passed six arguments, but it would work just as well with any other number. The functions we have written can not do this. Every function we have written so far has had an argument list with a specific number of values in it. So how can we make it so our function will let us pass in a variable number of arguments? In fact, it is not hard to do. Simply add an asterisk after the last type of the last argument in the parameter list. This will allow the caller to pass zero or more of that type.

A convenient place to do this would be an average function like we might use for calculating a grade. Such a method might look something like this.

def average(nums:Double*):Double =

...

The question is, how do we use nums inside of the function? As you might guess, this topic goes into this chapter because we treat nums just like a List or an Array. Technically, it is a Seq, a supertype of both, and all of the methods discussed in this chapter are available on it. These methods will make it very easy to write the average function.

def average(nums:Double*):Double =

 nums.sum/nums.length

That is it. Nothing more is needed because we can use sum on a sequence of Double values and we can get the length of any sequence.

What if we want the average with the minimum value dropped? That does not add much complexity because there is a min method that we can call as well.

def averageDropMin(nums:Double*):Double =

 (nums.sum-nums.min)/(nums.length-1)

We could use these along with the fullAve function from chapter 5 to make a revised version of courseAverage.

def courseAverage(test1:Double,test2:Double,assn1:Double,

  assn2:Double,assn3:Double,quiz1:Double,quiz2:Double,

  quiz3:Double,quiz4:Double):Double = {

 val aveTest=average(test1,test2)

 val aveAssn=average(assn1,assn2,assn3)

 val aveQuiz=averageDropMin(quiz1,quiz2,quiz3,quiz4)

 fullAve(aveTest,aveAssn,aveQuiz)

}

This gives us less total code than before because we were able to reuse the average function. However, now that we know about Lists and Arrays, the way we call this method is a little bit unpleasing. This takes a fixed number of test grades, assignment grades, and quiz grades. This would be a lot more flexible if we passed in Lists of these different values instead. Then the function would look more like this.

def courseAverage(tests:List[Double],assns:List[Double],

  quizzes:List[Double]):Double = {

 ...

}

Unfortunately, if you try to write this in the first way that comes to mind you will find that Scala does not like it.

def courseAverage(tests:List[Double],assns:List[Double],

 quizzes:List[Double]):Double = {

 val aveTest=average(tests) val aveAssn=average(assns)

 val aveQuiz=averageDropMin(quizzes)

 fullAve(aveTest,aveAssn,aveQuiz)

}

You will get an error that looks like this.

<console>:10: error: type mismatch;

 found : List[Double]

 required: Double

   val aveTest=average(tests)

      ^

<console>:11: error: type mismatch;

  found : List[Double]

  required: Double

  val aveAssn=average(assns)

      ^

<console>:12: error: type mismatch;

 found : List[Double]

 required: Double

  val aveQuiz=averageDropMin(quizzes)

        ^

This is because List[Double] is not the same type as Double*. However, the two are very similar in practice and it seems that you should be able to quickly and easily use the Lists in a place that calls for a variable length argument. Indeed, you can. You have to tell Scala that is what you are doing. You do this with a syntax much like specifying the type of something with a colon after the name followed by the type. You do not use Double* as the type though, instead you use _* because Scala really does not care about the specific type.

def courseAverage(tests:List[Double],assns:List[Double],

 quizzes:List[Double]):Double = {

  val aveTest=average(tests:_*)

  val aveAssn=average(assns:_*)

  val aveQuiz=averageDropMin(quizzes:_*)

  fullAve(aveTest,aveAssn,aveQuiz)

}

Now we have a function that computes an average with Lists so it is flexible in the number of grades passed in and rather simple to call and use in a larger program. If you do enough testing on this code you will find there there is a bug. You can make it produce incorrect output. We leave it as an exercise for the reader to find this bug.

7.7 Mutability and Aliasing

In this chapter we have seen that List is immutable while Array is mutable. It has been stated that the functional style will tend to use immutable and that while mutable data has significant benefits for some operations, it is also potentially less safe. You might wonder why it is less safe though. After all, it should not be too hard to make sure that you do not make changes to an Array. That is true in small programs, but it gets harder and harder as the programs get larger and for reasons that you probably do not fully grasp at this point.

A big part of the problem comes from something called aliasing. This is when two different names refer to the same object. To understand this, we need to refine our view of what is happening in the memory of the computer. Consider the following variable declarations.

var i1=5

var d1=5.9

var s1="Scala is fun!"

var l1=List(1,2,3,4)

var a1=Array(1,2,3,4)

All of these have been made as vars just to give us the option of altering them below. Normally we would want to use a val unless we explicitly found a reason why we had to change them. In this case the reason is just for illustration.

The memory layout looks something like what is shown in figure 7.2. This is an idealized representation. In reality memory is all linear and has structure to it that will be discussed in chapter 13. For now, this view is sufficient. On the left are boxes that represent the variables. In Scala the best mental better picture is to see the variables as boxes that store references to values. In some situations Scala will put the actual values in the boxes for the variables, but that is an optimization that you do not really have control over and it will not alter the behavior, so it is good to picture the memory like this.

What happens to this picture if we change the value of two of the variables? For example, say that now we execute these two lines of code.

i1=8

s1="New string."

The first one changes i1 so that it references the value 8. The second one changes the s1 so that it references this alternate String. What would this look like in memory? The result is shown in figure 7.3. The 5 and the String “Scala is fun!” have not been changed. They remain in memory just like before. Because nothing references them, these objects will be collected and disposed of automatically. What has changed is the references in i1 and s1. They now point to new objects in new chunks of memory that hold these new values. Both the Int and String types are immutable. As a result, once the objects are created, nothing can change them. They do not allow any operations that would alter their values. If we had made these variables using val we would not be able to change where the arrows point either.

Indeed, all of the types used here are immutable with the exception of the Array. So Array is the only one where we can change the value in the box on the right. To see how this can matter we will consider only the List and the Array variables and add two more lines of code to the picture.

val l2=l1

val a2=a1

This gives us a slightly different picture that is shown in figure 7.4. Now we have two different variables that point to each of the List and Array objects. These second references to the same object are often called aliases. Aliasing is where mutability starts to cause problems. If you have not figured out why yet, perhaps this code will make it clear.

scala> a2(3)=99

scala> a1

res1: Array[Int] = Array(1, 2, 3, 99)

In the first line we change the value in the last slot in a2. On the next line we look at the value of a1. Note that it is changed. We did not explicitly do anything with a1, but the value is changed because a2 is an alias of a1. You can not do this with l2 because the List type is immutable.

There are times when the ability to make an alias and change it is great. There are some tasks for which this can make things much more efficient. However, if you lose track of what is going on and what values are aliases of what values, you can run into serious problems.

7.8 Basic Argument Passing

Now that we have looked at the way memory is organized for variable declarations and the aliasing issue, we should take another look at what happens when you call a function. The two are actually very similar. When you pass values into a function, the function has local vals with the local argument names, but they reference the same objects that the outside variables referenced. Consider the following code from a script.

def getAndClear(arr:Array[Int],index:Int):Int = {

 val ret=arr(index)

 arr(index)=0

 ret

}

val numbers=Array(7,4,9,8,5,3,2,6,1)

val place=5

val value=getAndClear(numbers,place)

// Other stuff

The function is passed an Array of Ints and an index for a location in that array. It is supposed to return the value at that location and also “clear” that location. The meaning of “clear” here is to store a zero at that location. To see how this works look at figure 7.5 which shows the arrangement of memory. The function is defined and the variables numbers and place are both declared and initialized. We get new objects for them to reference.

When the getAndClear function is called, numbers and place are passed in to be the values of the arguments arr and index. While the code is in getAndClear, arr is an alias for the object referred to by numbers and index is an alias for the object referred to by place. This is significant because the getAndClear method has a side effect. It modifies one of the values stored in the Array that is passed to it, when the code gets down to “Other stuff”, the memory looks a bit different as shown in figure 7.6. At that point, the function has finished so its local variables are no longer needed. In addition, the 6th element in the array numbers has been changed. The function managed to change the value for the Array as seen outside that function. With a name like getAndClear you could probably figure out that this type of side effect might happen. However, when you pass any mutable value into a function, you need to be aware that the function could change your value, even if you do not really want it to.

How would this be different with a List? Well, the List type is immutable so it would be impossible for the function to change the list. If you wanted it changed, the function would need to return a tuple including both the value gotten and a new List with that value changed. The code below shows how that could be done with some of the methods we have introduced in this chapter.

def getAndClear(lst:List[Int],index:Int):(Int,List[Int]) = {

 (lst(index),lst.zipWithIndex.map(tup => {

 val (n,i)=tup

 if(i==index) 0 else n}))

}

There is only one expression in this function, the tuple to return. The first element in the tuple is lst(index). It looks up the proper value and uses the value there. Remember that looking things up in this way on a List is not really efficient, but we have to do so if given a List and an index. The second part of the tuple is a bit more complex. It called the method zipWithIndex on lst. This returns a new List where each element is a tuple that contains an elements from the List along with the index of that element. We have to do this because we need the index in order to decide if it is the one to be cleared or not. If we were clearing based on value instead of position this would not be needed.

The method map is immediately called on the List of tuples and it is given a function literal that takes one argument called tup, short for tuple. This function literal uses curly braces and has two lines. The first line is a val that pulls the two parts out of the tuple. The number from the List is called n and the index is called i. The function literal finished with an if expression that checks the index and gives the value of 0 or n based on if i is the same as index. There are other ways to write this. One that could be more efficient when index is small compared to the length of the List is shown here.

def getAndClear2(lst:List[Int],index:Int):(Int,List[Int]) = {

 (lst(index),lst.take(index):::(0::lst.drop(index+1)))

}

This version uses the cons operator, ::, which we saw before. It adds one new element to the front of a List and gives that back. It also uses an operator that we have not seen previously, the ::: operator. This does roughly the same thing as :: except that the argument on the left is a full List that should be appended to the front of the second List.

Of course, because the List version is having to rebuild the List, it could go a step further and truly clear the value. It could remove it from the List instead of overwriting it with zero. This would be done with filter instead of map on the first version. The second version is even easier to change. We leave that as an exercise for the reader to create and try.

An interesting question now becomes which of these is better? Is it better to use an Array which can be mutated or a List which can not? The answer is that it depends on whether you want a function to be able to mutate the data. If the function is supposed to mutate the data then there can be a speed benefit to passing something mutable. However, if you do not want the data mutated then there is a problem with passing mutable data. When you pass mutable data into a function, you have no control over whether it is mutated. In situations where you do not want your data mutated, this requires that you make a defensive copy. To protect your version of the data, you make a copy of it and pass the copy into the function.

For this reason, the question of whether you want to use a mutable or immutable structure depends a lot on the way in which you use that data. If it is going to be mutated frequently then it might make sense for it to be mutable. However, if it is not going to be mutated frequently then immutable likely makes sense so you do not have to make defensive copies. Even in situations where there might be a fair bit of mutation, you need to consider how much defensive copying will be needed if you choose mutable.

7.9 Pass-By-Name

Earlier we looked at the way in which arguments are passed in Scala. This is a style called pass-by-value. The function gets a copy of what the variable was in the calling code. The function can not change that variable, it can only change what it refers to if what it refers to is mutable. Some languages provide an alternate way of passing things called pass-by-reference. When something is passed by reference, the function has the ability to change the variable in the calling function itself. The fact that all variables in Scala basically are references blurs the line between the two, but fundamentally Scala only allows pass-by-value and the function can only modify things seen to the outside if the variable refers to a mutable object.

While Scala does not provide a true pass-by-reference, it does provide a passing style that few other languages provide, pass-by-name. The idea of pass-by-name is that the argument is passed not as a value, but as a thunk that is basically a set of code that will be executed and give a value when the parameter is used in the function. You can imagine pass-by-name as automatically creating a function that takes no argument and returns a value that will be executed each time the argument is used. To help you understand this and see the syntax, we will give a simple example. We will start making a basic increment function in the way we are used to doing.

scala> def incr(n:Int):Int = {

 | println("About to increment.")

 | n+1

 |}

incr: (n: Int)Int

The print statement is just to help us keep track of what is happening when. Now we will write the same function again, but this time pass the argument by name instead.

scala> def incrByName(n : =>Int):Int = {

 | println("About to increment.")

 | n+1

 |}

incrByName: (n: => Int)Int

The syntax for passing an argument by name is to put a rocket before the type of the argument. This is the same arrow used in function literals. If we were to put empty parentheses in front of it to get ()=> we would have the type of a function that takes no arguments and returns an Int. The by-name argument is much the same only when you call the function you do not have to explicitly make a function. To start off, we will call this function in the simplest way we possibly could.

scala> incr(5)

About to increment.

res0: Int = 6

scala> incrByName(5)

About to increment.

res1: Int = 6

No surprises here. They appear to both do the same thing. Both print the statement and give us back 6. However, the two are not really doing the same thing. To make that clear, we will call them again and have the argument be a block that includes a print.

scala> incr({println("Eval"); 5})

Eval

About to increment.

res2: Int = 6

scala> incrByName({println("Eval"); 5})

About to increment.

Eval

res3: Int = 6

Now it is clear that they are not doing the same thing. When you pass an argument by value, it is evaluated before the function starts so that you can have the value to pass through. When you pass by name, the evaluation happens when the parameter is used. That is why the line “Eval” printed out after “About to increment.” in the second case. The println in the function happens before the value of n is ever accessed.

Using pass-by-name gives you the ability to do some rather interesting things when mutations of values comes into play. To see that, we can write a slightly different function.

scala> def thriceMultiplied(n : => Int):Int = n*n*n

thriceMultiplied: (n: => Int)Int

It might seem that this method should be called cubed, but as we will see, this might not always apply for it because it uses pass-by-name. To start with, let us call it with an expression that gives a simple value, but prints something first.

scala> thriceMultiplied({println("Get value."); 5})

Get value.

Get value.

Get value.

res4: Int = 125

Note that the println statement happened three times. This is because the value n was used three times in the function. Had the parameter not been passed by-name, that would not have happened. It would have printed once, when the function was called. Try this for yourself.

This particular call still gave us a valid cube though. So why was the function not simply called cube? The reason is that if the code in the argument does the right thing, the result won’t be a cube. Here is an example.

scala> var i=5

i: Int = 5

scala> thriceMultiplied({i+=1; i})

res5: Int = 336

336 is not a perfect cube. So how did we get this value? In this example we introduced a var. The code in the pass-by-name argument alters this var. As a result, every time that n is used, the value given by n is different. The first time we use n the value is 6 because the original 5 was incremented and then returned. The next time it is 7 because the 6 that it was set to the previous time is incremented again. The last time it is 8. So the answer is 6 * 7 * 8 = 336.

These calls with both parentheses and curly braces might seem odd. The creators of Scala thought so. As a result, they made it so that if a function or method takes an argument list with only one value in it, that value can be in curly braces instead of parentheses. This allows a shorter syntax for the call that looks like this.

scala> thriceMultiplied {i+=1; i}

res6: Int = 990

You might be tempted to think that leaving off the parentheses changed what happened because the result is different. It was not the parentheses though. Remember that after the last call i had been incremented up to 8. So this time the result was 9 * 10 * 11 = 990.

7.10 Fill and Tabulate

One of the reasons for introducing pass-by-name in this chapter is that there are some other ways to make Arrays and Lists. One of them uses pass-by-name. Previously we saw how we could follow Array or List with a list in parentheses to get back either an Array or a List with those values in it. We could also use new to get a large array of default values or :: to put together Lists. There are also methods we can call on Array and List called fill and tabulate. Both can be used to make a new Array or List. They both work well for making large Arrays and Lists, unlike the version where you have to specify the individual values. Let us look at how these work.

The fill method is a curried method that takes a first argument specifying how many elements to make and a second argument, which is a pass-by-name argument giving the value. The simplest invocation of this might look like the following.

scala> Array.fill(10)(4)

res3: Array[Int] = Array(4, 4, 4, 4, 4, 4, 4, 4, 4, 4)

scala> List.fill(6)(23)

res4: List[Int] = List(23, 23, 23, 23, 23, 23)

scala> List.fill(6)("hi")

res5: List[java.lang.String] = List(hi, hi, hi, hi, hi, hi)

If the second argument is a constant, then the call simply fills the whole Array or List with that value. However, that argument is passed by-name so it is actually re-evaluated for each element of the sequence and if it has side effects, they will happen multiple times.

The easiest way to see this is to have the second argument print something.

scala> Array.fill(4){println("Evaluating argument"); 5}

Evaluating argument

Evaluating argument

Evaluating argument

Evaluating argument

res6: Array[Int] = Array(5, 5, 5, 5)

Note that here the second argument has been put in curly braces only. Remember that Scala allows you to do that for an argument list that only has one argument. You can add an extra set of parentheses, but you will still need the curly braces because this is a block of code with two expressions in it. This example is illustrative, but not really all that useful. A more interesting example involves using a var.

scala> var i=1

i: Int = 1

scala> List.fill(5){i*=2; i}

res7: List[Int] = List(2, 4, 8, 16, 32)

Here the var i is initialized to be 1. The value argument multiplies i by 2 and stores that value back in i. Then it gives back i as the value to use. You can see in the output that this gives us powers of 2. While there are situations where this can be helpful, this method of filling an array with powers of two is likely to confuse most people reading your code. An even more useful example is to have the value argument read input.

scala> Array.fill(5){readInt()}

res8: Array[Int] = Array(6, 4, 8, 2, 3)

This is what we started off the chapter doing, writing functions to read values into an Array or List. It turns out that as long as we know how many elements we want, we can do this with a single line of code thanks to fill and pass-by-name.

It is often helpful, when calculating values for an Array or List, to know the index of the value you are calculating for. The fill method does not do this for us by default. We could use a var to keep track of that, in a manner similar to what we did above, but this is a pain and quite error prone. That is why the tabulate method exists. You call tabulate much like you do fill, only the second argument is not a pass-by-name variable, it is a function that takes an Int and returns the type the sequence should be filled with. So if you want to fill an array with the result of evaluating a polynomial on the index you could do the following.

scala> Array.tabulate(6)(x => 3*x*x+5*x-7)

res9: Array[Int] = Array(-7, 1, 15, 35, 61, 93)

This fills the array with values of 3x2 + 5x − 7 where x is the index in the array.

7.11 Complete Grades Script/Software Development

In chapter 5 we spent some time writing functions to calculate averages in a class. We now have the ability to put together everything that we have learned and write a script that will keep track of the grades for a single student and be able to calculate that student’s average. This could be extended to multiple students, but we will not do that here.

When we solve a large problem there are certain steps that much be taken. The first is to get a clear description of what problem you are solving. This step is called analysis. The analysis step does not involve any coding or even thinking about coding. We just want a description that has enough detail that we know what it is we are supposed to create. Once we have that we can move on to the next step which is called design. In the design step we figure out how we are going to go about solving the problem described in the analysis. The design step does not involve coding either, but it specifies what we will do when we get to the coding. The design phase is where we do our problem decomposition. We think about how to break the problem down and what pieces we will need to put together to get a single, whole solution to the problem. After we have a design we get to the implementation phase. This is where we will actually write the program. Ideally, by the time that we get to implementation we have worked out most of the problems we will run into. The ability to see the problems we will encounter requires a lot of experience. As novice programmers, you should try to spend time on design, thinking about how to break the problem down, but do not become so intent on having a complete design that you stall out and never get to implementation.

After you have an implementation you have to make sure it works and fix any problems. This is called the testing and debugging phase because it is where you test the code to find all the bugs and fix them. For real software, after all the bugs are fixed and the software has been rolled out, you worry about maintenance. This is where you continue to make alterations to the software to improve it or address customer requests.

At the level you are at now, you typically don’t do much analysis or maintenance. You do not do much analysis because generally your instructor or this book will give you a fairly complete description of what you are doing. You do not do maintenance because you do not have a customer base that is using the software. A little of each of these can still creep into your work when you make sure you fully understand the description of a problem and then perhaps if you are given a later problem that incorporates code you had done previously.

You should spend a significant amount of time working on design and debugging. In fact, the implementation phase is often the shortest phase of the software creation process.4 If done properly, most of the thinking goes into the design phase so implementation is simply typing in what you had designed. Testing and debugging is extremely variable in time. It is possible to write your program and have everything work perfectly the first time. That gets less likely as programs get longer and is especially rare for novice programmers, though the static type checking in Scala will help to make it so that if everything in your program checks out it has a better chance of working. When things do not work, debugging can take arbitrarily long periods of time and is often the longest phase of software development.

In real software development these different phases are not always so distinct, and they are rarely done in sequential order. It is common that in one phase of development you realize something that was missed in an earlier phase. Some approaches to software development mix the phases together so that the developer is involved in more than one at any given time. If you continue on in Computer Science, these topics should be covered in full detail in a course on Software Engineering.

At this point we have a very vague description of the problem that we are going to solve. For that reason, we need to do some analysis up front so that we have a clear description of exactly what we are going to solve. This script is going to use a text menu to give the user options. The options will include the ability to add grades of different types as well as an option to print the current grades and average. Types of grades are tests, quizzes, and assignment. For the final average, the tests and assignments count 40% each and the quizzes make up the remaining 20%. The lowest quiz grade should be dropped. The menu will have numbers by each option and users enter a number to select that option. That is probably a sufficient analysis for our needs here. We can start working on the design and if we hit anything we have questions on, we can go back and add some detail to the analysis before we proceed further with the design.

So how are we going to break this problem down? At the top level we have code that repeats over and over and each time a menu is printed, the user selects an option, and we execute code to perform the selected option. The only way we currently know how to do something repeatedly an unspecified number of times is with a recursive function. So we will need a recursive function that contains all this other functionality. That function will call itself until we hit the condition where it exits. There is a natural decomposition at this point. Printing the menu is an obvious function. We have already seen that we can write functions for taking averages or averages dropping the minimum grade as well as one to calculate the final average.

That breaks down the functionality. If you were to run to the keyboard now and start typing you would quickly realize that something significant was left out of the design, how we are storing the grades. There are many ways that we could do this, but given that our only functionality is to add grades and calculate averages, the solution is fairly clear. Our only real options at this point are Arrays and Lists. Arrays have a fixed size and are inefficient to add to. That is less than ideal for this application because we will be adding grades and have not specified how many there can be. So Lists make more sense. We can use three Lists that store the three different types of grades. If we do this in an imperative style, the Lists will be declared with var before the main recursive function. If we use a functional style, they will be passed into the next call for the iteration. We will look at both to illustrate the differences. Most of the functions will not be altered by this distinction.

That gives us a decent design for this little application. Now we turn to the implementation. We will reuse the course average function from section 7.6 and the functions that it calls for now. We need new functions for our main recursive function and printing the menu. We will start with an imperative version of the main function and look at a functional adaptation afterward.

def printMenu {

 println("""Select one of the following options:

 1. Add a test grade.

 2. Add a quiz grade.

 3. Add an assignment grade.

 4. Calculate average.

 5. Quit.""")

}

var tests = List[Double]()

var quizzes = List[Double]()

var assignments = List[Double]()

def mainGrades {

 printMenu

 readInt() match {

 case 1 =>

 println("Enter a test grade.")

 tests = readDouble() :: tests

 case 2 =>

 println("Enter a quiz grade.")

 quizzes = readDouble() :: quizzes

 case 3 =>

 println("Enter an assignment grade.")

 assignments = readDouble() :: assignments

 case 4 =>

 println("The average is "+courseAverage(tests,assignments,quizzes))

 case 5 =>

 return

 case _ =>

  println("Unknown option. Try again.")

 }

 mainGrades

}

This begins with the printMenu function which simply prints a menu. The only thing of interest here is the use of the triple quote string so that the string can be made to span multiple lines. If you do not do this, you will have to use to denote line breaks.

In this imperative version, the printMenu function is followed by the declaration of three variables. They are all vars and they are of the type List[Double]. The have to be vars because the List itself is immutable. So whenever something is added we have to change the variable reference and point to a new List. Remember, this can be done efficiently for the List type so that is fine.

If you type this code in and play with it a bit, you will probably find that you can make it behave poorly. In particular, you can get it so that when you ask for the average you get an output like this.

The average is NaN

This should lead you to two questions. First, what is this thing called NaN? Second, what is causing this? Technically the second matters more because we need to know that to fix it. However, knowing the answer to the first can help you figure it out if you were not able to do so from your testing. The Double type, as we have discussed previously, is used to represent numeric values that have fractional parts. It has a rather large range and good precision, but it is technically a fixed precision type. You can not represent any real number with it. In addition, some mathematical operations produce results that are not well defined. Consider the following.

scala> 1.0/0.0

res2: Double = Infinity

scala> -1.0/0.0

res3: Double = -Infinity

You should have learned in a math class that you can not divide by zero. If you do this with Ints you get an error. However, if you do it with Doubles you get what you see here. Any operation that goes outside the range of the Double will also get you either Infinity or -Infinity, depending on which side of the range it goes out on as is shown here.

scala> 1e150*1e200

res6: Double = Infinity

What does all of this have to do with NaN? Well, NaN stand for “Not-a-Number” and it is the result of an operation when it is not clear what the result should be. One way to get this is to add Infinity and -Infinity or do other operations with Infinity or -Infinity that the computer can not know the result of. Consider this example.

scala> 1e150*1e200-1.0/0.0

res10: Double = NaN

In general the computer can not know if this would be out of range on the positive or negative so it goes to NaN because it gives up. There is one other way to get a NaN: divide zero by zero.

scala> 0.0/0.0

res11: Double = NaN

This is what is happening to cause our error, and it happens when zero test or assignment grades or only one quiz grade have been entered.

If we have no test or assignment grade, the normal average will return 0.0/0, as the sum is the Double 0.0 and the length is the Int 0. If the list of quiz grades only has one element, then that one is the minimum. So the function returns (x-x)/(1-1) where x is the one grade as a Double. Clearly that is going to be a NaN. So how do we fix this? We need to make the average and the averageDropMin functions a bit smarter so that they have special cases in the instances when they should not do division. We can do this by putting if expressions in both.

def average(nums:Double*):Double =

 if(nums.isEmpty) 0 else nums.sum/nums.length

def averageDropMin(nums:Double*):Double =

 if(nums.isEmpty || nums.tail.isEmpty) 0 else

 (nums.sum-nums.min)/(nums.length-1)

If you use these versions of the functions things should work well.

Now to the functional alternative. The imperative version uses three var declarations outside of the function. These declarations can be seen by anything in the script that follows them. We typically refer to this as the global scope. For small scripts this might not be a problem, but you do not want to get into the habit of making things global. Anything that is global in a large program can be messed up by any line of code, making it very hard to track down certain types of errors. It is better to have our variables declared in a local scope, inside of a function.

If we simply declare the variables inside of mainGrades, it will not work because when you make a recursive call, you get new versions of all of the local variables. Instead, we want to pass the three lists into the function as arguments. The arguments to a function act just like local val declarations except that the value is provided by the calling code. This new version will not include any var declarations, nor will it have any mutable values as everything is stored in immutable Lists. So other than the printing, it is completely functional. Here is what such a function might look like.

def mainGrades(tests:List[Double],assignments:List[Double],

 quizzes:List[Double]) {

 printMenu

 readInt() match {

 case 1 =>

  println("Enter a test grade.")

  mainGrades(readDouble() :: tests,assignments,quizzes)

 case 2 =>

  println("Enter a quiz grade.")

  mainGrades(tests,assignments,readDouble() :: quizzes)

 case 3 =>

  println("Enter an assignment grade.")

  mainGrades(tests,readDouble() :: assignments,quizzes)

 case 4 =>

  println("The average is "+courseAverage(tests,assignments,quizzes))

  mainGrades(tests,assignments,quizzes)

 case 5 =>

 case _ =>

  println("Unknown option. Try again.")

  mainGrades(tests,assignments,quizzes)

 }

 }

Instead of mutating values, this version passes the newly built List into the recursive call where it is a completely new argument value for the next level down in the recursion. The options that do not change the Lists simply pass through the same values.

7.12 End of Chapter Material

7.12.1 Problem-Solving Approach

Despite the length of this chapter, no new valid statement types were introduced. Instead, a significant amount of flexibility was added in what you might do with the existing statement types. In particular, you can now use expressions with collection types and call methods on those collection types. You also learned that types themselves can be more complex with type parameters. You can make functions that take variable numbers of arguments and you can pass arguments into functions using pass-by-name.

7.12.2 Summary of Concepts

• Arrays and Lists are collections that allow us to store multiple values under a single name. They are sequences, meaning that the values have an order and each one is associated with an integer index. Indexes start at zero.
• Both can be created in a number of ways.
  • Array(e1,e2,e3,...) or List(e1,e2,e3,...) to make short collections where you provide all the values.
  • new Array[Type](num) will make an Array of the specified type with the specified number of elements. All elements will have a default value. This is the least common usage in Scala.
  • Use the :: operator with Lists to append elements to the front and make a new List. Use Nil to represent an empty List.
  • Array.fill(num)(byNameExpression) will make an Array of the specified size with values coming from repeated execution of the specified expression. This will also work for Lists.
  • Array.tabulate(num)(functionOnInt) will make an Array with num elements with values that come from evaluating the function and passing it the index. Often function literals are used here. This will also work with List.
• Arrays have a fixed size and are mutable. Access and mutate using an index in parentheses: arr(i).
• Lists are completely immutable, but you can efficiently add to the front to make new Lists. Can be accessed with an index, but using head and tail is typically more efficient.
• The Scala collections, including Array and List, have lots of methods you can call on to do things.
  • There are quite a few basic methods that take normal values for arguments and give you back values, parts of collections, of locations where things occur.
  • The real power of collections is found in the higher-order methods. The primary ones you will use are map, filter, and foreach.
  • There are a handful of methods that give you back various pieces of collections, including combinatorial possibilities such as permutations and combinations.
• You can make the last parameter of a function accept a variable number of arguments, var args, by putting an asterisk after the type. The name given to that parameter functions as a sequence. To pass a real sequence into a function in place of a var args parameter, follow it with : _* to tell Scala you want that seen as a * argument of some type.
• When two variables refer to the same object in memory we call them aliases.
• Mutable objects can cause problems with aliases because changes to the object can be made using any of the aliases and they will be reflected in all of them.
• By default, arguments in Scala are passed by-value. The value of the reference is passed into the function. This automatically makes an alias of the object. If you want to protect a mutable object from unintended changes when it is passed to a function you need to make a defensive copy.
• Scala also allows pass-by-name parameters. Instead of passing a value, these pass a chunk of code called a thunk that is evaluated every time the parameter is used.

7.12.3 Self-Directed Study

Enter the following statements into the REPL and see what they do. Try some variations to make sure you understand what is going on. Some of these are intended to fail. You should understand why.

scala> val arr = Array(1, 2, 3)

scala> arr(0)

scala> arr(1)

scala> arr(0) = 5

scala> arr.mkString(" ")

scala> val lst = List(2, 3, 5, 7, 11, 13, 17)

scala> lst.head

scala> lst.tail

scala> val bigArr = new Array[String](100)

scala> bigArr(0) = "A string"

scala> bigArr(1) = "Another string"

scala> bigArr(0).length

scala> bigArr(2).length

scala> val lst2 = 1 :: 2 :: 3 :: 4 :: 5 ::

Nil scala> lst.zip(lst2)

scala> lst.zipWithIndex

scala> val arr3 = Array.fill(5)(readLine())

scala> val lst3 = List.tabulate(20)(i => i*i)

scala> def printList(lst:List[Int]) = lst match {

 case h::t =>

 println(h)

 printList(t)

 case Nil =>

}

scala> printList(lst3)

scala> lst3.mkString(" ")

scala> lst3.map(i => math.sqrt(i))

scala> arr3.map(s => s.length)

scala> bigArr.filter(s => s!=null)

scala> arr.permutations.foreach(println)

scala> lst.sliding(4)

scala> def printWords(copies:Int,words:String*) {

 words.foreach(w => println(copies*w))

}

scala> printWords(3,"Hi")

scala> printWords(2,"This","is","a","test")

scala> val numWords = lst.map(_.toString)

scala> printWords(4,numWords)

scala> printWords(4,numWords:_*)

scala> val arrAlias = arr

scala> arrAlias.mkString(" ")

scala> arr.mkString(" ")

scala> arrAlias(0) = 42

scala> arr.mkString(" ")

scala> def alterArray(a:Array[Int]) {

 a(0) = 99

 a(1) = 98

 a(2) = 97

}

scala> alterArray(arr)

scala> arr.mkString(" ")

scala> def getIndex[A](index:Int,a:Array[A]):Option[A] = {

 if(index<a.length) Some(a(index)) else None

}

scala> getIndex(1,arr)

scala> getIndex(4,arr)

scala> lst.find(_ == 5)

scala> lst.find(_ == 9)

scala> def recursiveWhile(cond: =>Boolean)(body: =>Unit) {

 if(cond) {

 body

 recursiveWhile(cond)(body)

 }

}

scala> var i=0

scala> recursiveWhile(i<10) {

 println(i)

 i += 1

}

7.12.4 Exercises

1. Think of as many ways as you can to make an Array[Int] that has the values 1-10 in it. Write them all to test that they work. The first two should be easy. If you work you can get at least three others knowing what has been covered so far.
2. Think of as many ways as you can to make a List[Int] that has the values 1-10 in it. Write them all to test that they work. The first two should be easy. If you work you can get at least three others knowing what has been covered so far.
3. Make a List[Char] that contains ’a’-’z’ without typing in all the characters. (Use toChar to make this work.)
4. Given two Array[Double] values of the same length, write a function that returns the element-wise sum. This is a new Array where each element is the sum of the values from the two input arrays at that location. So if you have Array(1,2,3) and Array(4,5,6) you will get back Array(5,7,9).
5. Write a function that produces a sequence of prime numbers. You can use the isPrime function that you wrote for exercise 9 (p.130). The function should take an argument for how many prime numbers need to be in the list.
6. Write a function that takes a number of values and returns the average excluding the largest and smallest values.
7. Write a function that takes a number of grades and returns the average with the lowest two grades dropped. Make sure this function behaves reasonably even for smaller input sets.
8. Write several versions of code that will take an Array[Int] and return the number of even values in the Array. Each one will use a different technique. To test this on a larger array you can make one using Array.fill(100)(util.Random.nextInt(100))
   1. (a) Use a recursive function.
   2. (b) Use the count higher-order method.
   3. (c) Use the filter higher-order method in conjunction with a regular method.
   4. (d) Use the map higher-order method in conjunction with a regular method.
9. Write a version of getAndClear that uses a List and completely removes the value at the specified index.
10. You can treat a String as a sequence of Char and use all the methods that we introduced here for List and Array on it. Using that, what code would you use to do the following? For all of these assume that str is a String provided by the user through readLine().
    1. (a) Get a version of the String with all the spaces removed.
    2. (b) Get a version of the String with all vowels removed.
    3. (c) Split off the first word of the String. Write code that gives you a (String, String) where the first element is everything up to the first space in str and the second one is everything else.
    4. (d) Convert to a sequence that has the integer values of each of the characters in str.
    5. (e) Write code that will take a sequence of Int, like the one you just made, and give you back a String. (Note that if you get a sequence of Char you can use mkString to get a simple String from it.)

7.12.5 Projects

1. We can express a general polynomial as

   $A_n{x}^n+A_{n-1}{x}^{n-1}+A_{n-2}{x}^{n-2}+\mathrm{...}+A_2{x}^2+A_{1}x+A_0$

   where the A values are the coefficients on different terms. You can view a sequence of Doubles as a polynomial by saying that the value at index n is the value of An. Using this representation, Array(1.0,0.0,2.0) would represent 2x2 + 1. Note that the order when you look at the Array is the opposite of the order seen in the polynomial.

   Using this representation of polynomial, write functions that do addition and subtraction of two polynomials. You can assume that the Arrays passed in are the same length. Also write functions that gives you the derivative of a polynomial and the anti-derivative.5 Note that the anti-derivative function will need and extra argument for the value of the constant term.

   To help you learn, try to write these functions using both recursion with an index and using standard methods on sequences. For the former option try doing it with Lists as well using :: to build the Lists in the recursion. For the latter a hint when you write add and subtract is to consider using the zip method.

   If you want an extra challenge, try writing multiplication as well. This is a significantly harder problem, but if you can do it with both recursion and the built-in methods you should feel good about your understanding.

2. This project has you implement a simple form of encryption and decryption. You should write at least two functions called encrypt and decrypt.

   The form of encryption we are using is offset encryption where you simply offset letters in the alphabet. If you pick an offset of 1, then if there is an ’a’ in the original message, the encrypted message will have a ’b’. For a first cut, write these functions so they just add or subtract a specified offset to all characters. (Note that when you do arithmetic on a Char you get an Int. Use the toChar method to get back that type. So (’a’+1).toChar will give you ’b’.) Your methods will both take a String and an Int and return a String. The Int passed in is the offset to apply to the characters.

   This approach is easy, but it produces non-letters in certain situations like when you do an offset on ’z’. Refine your functions so that they skip any characters that are not letters and wraps around so that if the offset goes above ’z’ it comes back to ’a’. You have to handle capital letters as well. (Note that the Char type has methods called isLetter, isUpper, and isLower that can help you with this. You can also do comparisons and math with the Char type.)

   If you want an extra challenge and you want to make it harder for someone to try to break your code, revise your methods so that they take an extra Int and insert random characters at intervals of that spacing. So if the value is 5, you will insert an extra random character between every fifth character from the message. You can generate a random letter character with the expression (’a’+util.Random.nextInt(26)).toChar.

   For this whole problem remember that you can treat Strings as sequences. So you can use them like an Array[Char] except that they are not mutable.

3. For this project you will be doing some simple data analysis. If you go to the book website and look at the page for this chapter you will find a text file for this exercise that has values in it. It is weather data for 2/17/2010 in San Antonio, TX from the Weather Underground (http://www.wunderground.com). It has one line for each hour and each line has a single number that it the temperature for that hour. Write a function that will read this into an Array[Double] using redirection and readDouble. Then write functions to calculate the following: standard deviation and change per hour. The standard deviation will return a Double. The change will return an Array[Double] that is one shorter than the original data set.

4. This project is to be built on top of project 6.3. For this one you make functions that will take a List or Array of the values used to represent spheres and planes and return the impact parameter of the first one the ray hits and the information on that geometry.

5. For this project, you will write a function that could help people playing Scrabble®. You will want to break this down so you have multiple functions in the end, but the last one is what really matters. If you go to the book’s website, the page for this chapter will have a data file for this exercise called 2of12.txt. This is a file with a list of 41238 English words. There is one word per line. Using input redirection and readLine you will read the contents of this file into an Array[String].

   Once you have this file read in, your goal is to give back words that the person could likely make using letters he/she has to play. Your end goal is a function that takes the list of the dictionary words and a String of the letters the person has to play, which returns all the words that can be made from their letters plus one other letter. The one other letter is something you do not know that should have been played somewhere on the board. For our purposes here we do not care what it is. You should give back any word that can be formed with some subset of the player’s letters plus one extra.

   To do this you really want to use functions to break the problem down. Consider what higher order methods could be helpful and what types of functions you need to use with them. To make this all work with input redirection download and edit the 2of12.txt file and insert a top line where you put the letters the player has in Scrabble. The script will read that line to get the letters and then read the proper number of lines to get all the words.

   Lastly, to help you solve this problem consider using the diff method. This method tells you the difference between two sequences. Play around with calling diff using different strings to see what it does. Start with "aabbcc".diff("abcde") and abcde".diff("aabbcc").

6. Now that you can keep store multiple values in Lists and Arrays, you can push the recipe program to use an arbitrary number of items. Make a script that asks the user for items in their pantry. It should ask for item names and how much they have until the user enters a name of “quit”. After that, the program will let the user run through recipes, entering one recipe name, followed by a number of ingredients, followed by the name and amount of each ingredient. It should then tell the user if they have enough to make that recipe and ask if they want to check another recipe.

7. Every semester you get to build a schedule of the courses that you will take in the following semester. This is the start of some projects at the end of which you write a program that will help you do so. For this first part, you want to have the user input courses he/she is interested in taking as well as how much they want to take those courses. The user should then tell the program how many courses should be taken the next semester and the minimum score for the “want to take” sum that will be accepted. The program should print out all of the schedule combinations with that many courses that make the cut. (Hint: Use combinations to run through all the possibilities. For each possibility, you can use map and sum to get the total “score” for that option.)

8. Write a function that takes a Double* and returns the median value as a Double. Your solution is not expected to be efficient. This is more of a test of your ability to do logic using the methods that were presented in this chapter.6

9. Write a function that takes an Int* and returns the mode of the values. As with the previous project, the goal here is more for you to think about how to make a solution than to make an efficient solution.

There are additional exercises and projects with data files to work on posted on the book’s website.

1The value null represents an invalid reference or a reference to nothing. Trying to do something with a null value will cause an error. For this reason, we will typically avoid this approach to making arrays. We will generally prefer to use Array.fill or Array.tabulate, which will be introduced later in this chapter.

2The return type of the function f that is passed into flatMap is technically a GenTraversableOnce[B]. This is more general than a Seq[B], but for now the difference is not important.

3The term currying comes from the name of Haskell Curry, a mathematician and logician.

4At least if you do things properly the implementation will be short. I like to tell my students that hours of coding can save minutes of thinking. The point of this is that if you do not sit and think about design before you go to the keyboard and write code you are likely to spend hours hashing out the design that you could have nailed down in a few minutes by thinking about it to begin with.

5You might recognize this better as an indefinite integral.

6The API includes a number of methods for sorting. Those could be used to make a more efficient and shorter solution to this problem, but the goal here is for you to do this without sorting.