COMPSCI 220 Programming Methodology

Exercise Assignment 03: Functional Functions

Overview

This exercise assignment introduces several functions that are commonly used in functional programming. Lists are the most common data structure in functional programming, and functions like map and foldLeft are the building blocks of programs that work with lists. Instead of recursion or looping, we define what transformations we’d like to apply to the contents of the list and let our building blocks do the work.

You may find Chapters 2 and 3 of Functional Programming in Scala to be very helpful. You will be relying heavily on recursion and pattern matching, so please be familiar with these concepts. I particularly enjoy this blog post as a quick pattern matching reference.

All of these functions will manipulate the Scala List type, not the List type used in the Functional Programming in Scala book. The blog post above goes into it a bit, but here’s some examples.

val list = List(1,2,3)
list match {
// Matching single element:
    case l :: _ => println(s"The head of the list is $l")
// Matching the rest of the list:
    case _ :: ls => println(s"The tail of the list is $ls")
// Match both parts:
    case l :: ls => println("Use l for something, then recurse with ls!")
// Checking if the list is empty:
    case Nil => println("Nil represents the empty list")
// Matching an element at the end of the list:
    case l :: Nil => println(s"$l is the last element of the list.")
// Matching a specific list:
    case List(1,2,3) => println("The lists are identical")
// Matching an unknown element:
    case List(1,2,n) => println(s"The last element is $n")
// Guards let you match on a condition (l > 2, in this case):
    case l :: ls if (l > 2) => println("The first element is greater than 0")
// A default case is often useful:
    case _ => println("The underscore matches everything.")
}

Scala will complain at compile time if you have too few cases and if you have too many.
Too few cases means the match can’t be completed successfully, and Scala will thrown an error.

list match {
    case l :: Nil => println("This only matches a list with 1 element.")
    // There's no other cases -- uh oh!
}

“Too many cases” means multiple cases can match the same thing. At least one of the cases will be unreachable!

list match {
    case l :: Nil => println("This will match if the list has one element.")
    case _ => println("This will match any list.")
    case l :: ls => println("This will never be reached due to the previous case.")

Learning Goals

• To understand the methodology behind common functions like map and fold.
• To understand how the functions may be used in your programs.
• To understand how to combine these functions in order to elegantly program complex tasks.
• To practice using these functions in simple and complex ways.

Test Files

In the src/test/scala directory, we provide ScalaTest test suites that will help you keep on track while completing the assignment. We recommend you run the tests often and use them to help create a checklist of things to do next. But, you should be aware that we deliberately do not provide you the full test suite we use when grading.

We recommend that you think about possible cases and add new test cases to these files as part of your programming discipline. Simple tests to add will consider questions such as:

• Do your methods handle edge cases such as integer arguments that may be positive, negative, or zero? Many methods only accept arguments that are in a particular range.

• Does your code handle unusual cases, such as empty or maximally-sized data structures?

More complex tests will be assignment-specific. To build good test cases, think about ways to exercise functions and methods. Work out the correct result for a call of a method with a given set of parameters by hand, then add it as a test case. Note that we will not be looking at your test cases (unless otherwise specified by the assignment documentation), they are just for your use and will be removed by the auto-grader during the evaluation process.

If you modify the test cases we provided or you added your own it is important to know that they will not be used. The auto-grader will use its own copy of the public and private tests. If you modify any source files in the src/test/scala directory your changes will not be reflected in the grading of your submission.

Before submitting, make sure that your program compiles with and passes all of the original tests. If you have errors in these files, it means the structure of the files found in the src directory have been altered in a way that will cause your submission to lose some (or all) points.

Project Structure

The project should normally contain the following root items:

• src/main/scala: This is the source folder where all code you are submitting must go. You can change anything you want in this folder (unless otherwise specified in the problem description and in the code we provide), you can add new files, etc.

• src/instructor/scala: This folder contains support code that we encourage you to use (and must be used to pass certain tests). You must not change or add anything in this folder. The auto-grader will replace your submitted src/instructor directory with the original during the evaluation process. If you make changes or add/remove anything it can lead to problems in your submission and will result in a 0 for the assignment.

• src/test/scala: The test folder where all of the public unit tests are available.

• tools/grading-assistant.jar: This is the grading assistant that you can run to give you an estimate of your score as well as package your project to be submitted to Moodle. More on this later. Do not remove.

• activator: This is a Unix helper script that can be used to run the activator interactive build tool. You can use this on Linux and Mac OSX. Do not remove.

• activator.bat: This is a Windows helper script that can be used to run the activator interactive build tool. You can use this on Windows. Do not remove.

• activator-launch-1.3.2.jar: This is a Scala/Java library that runs the activator tool and is used by the previously mentioned scripts. Do not remove.

• build.sbt: This is the build definition file. It provides build information to activator to build your project. Do not remove.

• .gitignore: This is a special file used by git source control to ignore certain files. You should not touch this file and please do not remove. This file may not be present if the assignment does not call for git usage.

Testing, Grading Assistant, and Console

As mentioned previously, you are provided a set of unit tests that will test various aspects of your implementation. You should get in the habit of running the tests frequently to see how you are doing and to understand where you might be going wrong. The ScalaTest testing framework is built-in to the activator tool and you can easily run the tests by issuing the following command from the command line (Mac/Linux):

./activator test

For Windows users you would issue the following command from the command window:

activator.bat test

This will compile your code and run the public ScalaTest unit tests. After you compile and run the tests you will notice that a target directory has been created. The target directory contains the generated class files from your source code as well as information and results of the tests. Activator uses this directory so it must not be removed. After you run the tests you can get a grade report from the Jeeves tool by issuing this command from the command line (Mac/Linux):

scala -cp tools/grading-assistant.jar autograder.jeeves.Jeeves

For Windows users you would issue the following command from the command window:

scala -cp tools\grading-assistant.jar autograder.jeeves.Jeeves

Note, issuing the above command from the activator console will not work! This will print a report to the console showing you the tests you passed, tests you failed, and a score based on the public tests. Although this gives you a good estimate as to what your final score might look like, it does not include points from our private tests. You may run Jeeves as often as you like, however, you must run the tests before your run Jeeves to give you an updated result.

Another very useful approach to test and play with the code you write is the activator/Scala console. You can run the console with this command (Mac/Linux):

./activator console

For Windows users you would issue the following command from the command window:

activator.bat console

This will load up the Scala REPL (read-eval-print-loop). You can type code directly into the console and have it executed. If you want to cut and paste a larger segment of code (e.g., function declaration) you simply type :paste in the console, then paste in your code, then type control-D.

In addition, you can run activator without any commands and you will be presented with the following prompt:

./activator
>

Or on Windows:

activator.bat
>

From the activator prompt you can type in any of the following commands:

• compile: this will compile your code
• ~compile: this will watch your files for changes and compile them when a change is detected.
• test: this will compile your code, the test code, and run the tests
• console: runs the scala console.

Editors and IDEs

You are welcome to use any editor or IDE you choose. We recommend using a basic text editor such as Atom, SublimeText, Notepad++, emacs, or vim.

If you use a text editor you should use activator in a separate terminal window to compile, run, and test your code.

If you have successfully installed and imported your project into IntelliJ you are welcome to continue using it.

Programming Task: The Functional Functions

This exercise is roughly split into four sections: list basics, folding, mapping, and combining functions. Each function has a comment in the functions.scala file, which explains the desired behavior of the function. Further details and hints may be found here. You’ll have to write the signature for each function, except for the few that we’ve provided.

Every function must be written either recursively with pattern matching or by using functions you already implemented.

You must NEVER use explicit iteration, including for loops and for comprehensions, in ANY of these functions.

Additionally, you will rarely need to define variables or use if statements. If you find yourself doing so, try to see if there’s another way to implement the function. If in doubt, ask an instructor!

List Basics

These functions are simple enough that you won’t need to call any other functions to implement them. All you need is pattern matching and recursion!

• tail: tail takes a list and returns all but the first element. This isn’t a recursive function, but you still need to use pattern matching in order to catch when the input is Nil. Calling tail on an empty list throws an IllegalArgumentException.
  Example: tail(List(1,2,3)) = List(2,3)
• setHead: setHead takes a list and replaces the first element. If the list is empty, it simply inserts the element into the empty list.
  Question: Can you use tail for this?
  Example: setHead(List(1,2,3), 0) = List(0,2,3)
• drop: drop removes the first N elements from the given list. If the number of elements to remove exceeds the number of elements in the list, drop will return an empty list.
  Hint: You have multiple base cases here. How can you match the number of elements to remove and the list at the same time?
  Example: drop(List(1,2,3,4), 3) = List(4).
• init: init is the opposite of tail: It removes the last element of the list. Remember that you’re not modifying the input list, but building a new list. Calling init on an empty list throws an IllegalArgumentException. Example: init(List(1,2,3)) = List(1,2).

Folding Lists

To “fold” a list means to reduce it down to a single value. You’ve done this before; for example, mkString takes a list (or array, vector, etc.) and turns it into a single String. In this section, we’re generalizing that into a generic foldLeft function and seeing just what we can do with it. After you implement foldLeft yourself, you must use it to implement the remaining functions in this section.

• foldLeft: One of the real bread-and-butter functions. foldLeft takes a list, an initial value, and a function, then computes a value by iteratively applying the function to the elements of the list and carrying the result along. You should have seen foldRight already; they’re very similar functions, but they perform the operations in different order. The difference is subtle; the key takeaway is that foldLeft is tail recursive.
  You should implement your own version of foldLeft using pattern matching and recursion. We’ve provided the function signature for you due. The function that foldLeft takes has two arguments: the accumulative result and the current element of the list.
• sum: sum takes a list of doubles and computes the sum. That’s it! Very straightforward.
  Example: sum(List(1.0, 2.0, 3.0)) = 6.0
• product: product takes a list of doubles and computes the product. This should be very similar to sum.
  Example: product(List(1.0, 2.0, 3.0)) = 6.0
• length: length computes the length of the input. This is a case where the result of foldLeft isn’t directly related to the input data! foldLeft doesn’t have to use the data, it just iterates over the list.
  Example: length(List(1,2,3,4,5,6)) = 6.
• reverse: reverse reverses a list. Yes, you can do this with foldLeft, too!
  Example: reverse(List(1,2,3)) = List(3,2,1)
• flatten: flatten turns a nested list into a single list. This is more straightforward than it sounds.
  Example: flatten(List(List(1,2,3), List(4,5,6))) = List(1,2,3,4,5,6)

At this point, you may be wondering about the difference between foldLeft and foldRight. Try this out in the Scala REPL: (Using Scala’s own fold functions, not ours.)

val h = List("H","e","l","l","o")
h.foldLeft("")(_ + _)
h.foldRight("")(_ + _)

Those should be the same. Now try this:

h.foldLeft("!")(_ + _)
h.foldRight("!")(_ + _)

Map and Filter

map and filter are two more building blocks. map is incredibly useful: it applies a function to each element of a list, producing a new list of the same length containing the results. filter lets you remove unwanted elements from a list using a function.

(Thought-provoking question: Why are map (the function) and Map[A,B] (the data structure) named the same thing?) (This isn’t a graded question.)

Reminder: Recursion and Pattern Matching are your friends.

• map: map takes a list and a function, then builds a new list by applying the function to each element of the list. This is the third or fourth time you’ve read that description so far in this exercise. Still unsure what it does? Ask!
  Unlike foldLeft, map’s function takes only a single argument.
• filter: filter applies a predicate (a function that returns a Boolean value) to the elements of the list, and discards the ones for which the predicate returns False.
  Example: filter(List(1,2,3,4,5))( _ % 2 == 0) = List(2,4)
• flatMap: flatMap is a cross between map and flatten. Instead of a single value, flatMap’s function returns a list of values. flatMap collects all of these values into a single list.
  Hint: Don’t overthink it.

Combining Functional Functions: Bringing It All Together

You’ll notice there weren’t any neat small functions for the Map and Filter section like there were for the Folding Lists section. Instead, we’re going to jump right into solving some interesting and complex problems using the functions you’ve written so far.

Note: These functions are all independent. You must use the functions you implemented in the previous parts, but you won’t be using these functions to implement each other unless specifically noted otherwise.

• maxAverage: maxAverage takes as input a list of tuples of doubles. It then finds the average of the largest values in each tuple.
  Hint: You need to transform the input list into a list of the max values, then find the average of that list. What function(s) can you use for that?
• variance: variance calculates the statistical variance of a population, or the squared deviation from the mean. Statistics!
  In more detail: variance is the average of the squared difference of each element from the average of the whole list. So if the average of the whole list is M, the variance is sum((l - M)^2)/length. (Sometimes, you will see the sum divided by length - 1. Don’t worry about that – we’re treating the list as a whole population instead of a random sample.)

Submission

When you have completed the changes to your code, you must run the following command to package up your project for submission (Mac/Linux):

scala -cp tools/grading-assistant.jar submission.tools.PrepareSubmission

On Windows:

scala -cp tools\grading-assistant.jar submission.tools.PrepareSubmission

This will package up your submission into a zip file called submission-DATE.zip, where DATE is the date and time you packaged your project for submission. After you do this, log into Moodle and submit the generated zip file.

After you submit the file to Moodle you should ensure that Moodle has received your submission by going to the activity page for the assignment and verifying that it has indeed been uploaded to Moodle. To further ensure that you have uploaded the correct zip file you should download your submission from Moodle and verify that the contents are what you expect.

We do not allow re-submissions after the assignment due date even if you failed to submit the proper file or forgot. There are no exceptions so be very sure that you have submitted properly.

You should test that you can run the PrepareSubmission tool early so you do not have trouble packaging your assignment up for submission minutes before the deadline.