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

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:

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:

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:

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!

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.

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.

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.

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.