Lab 6: Higher-order functions
Exam 1 prep: Before beginning the lab problems, please do the Hourglass tutorial at https://hourglass1.khoury.northeastern.edu/. This will allow you to become familiar with the tool we will use for Exam 1 on the 20th. Please use Firefox for using Hourglass.
Goals: The goals of this lab are to practice writing operations using higher-order functions, and implement a new higher-order function.
Problem 1: Generics and higher-order functions
6.1 The Convolve higher-order function
We have seen the following higher-order functions:
Filter IList<T> -> IList<T>: Takes a Predicate<T> object.
Map IList<T> -> IList<U>: Takes a Function<T,U> object.
Fold IList<T> -> U: Takes an initial U value, and a BiFunction<T,U,U> object.
You can find an implementation of these operations in the attached code.
6.1.1 Practice with higher order functions
Add templates to the provided IList<T> classes.
Create a list of strings in the ExamplesLists class. The list should contains the months of the year. Write tests for the following, using higher-order functions:
Find all the months that begin with the letter ’J’
Find how many months end with "er" (without writing a separate length() method for IList)
Create a list of all the 3-letter abbreviations of each month. The 3-letter abbreviation of a month is simply the first 3 letters of its name
6.1.2 The Convolve operation
The convolve operation is best understood using lists of numbers. Consider two lists W and L of numbers, of the same length. The convolution of these two lists produces a list that represents their per-element combination in some way. For example, a list of numbers C can be produced where each element in C is the product of the respective elements in W and L. If W=[0.3 0.5 0.1 -0.3] and L=[2.0 4.0 3.0 1.0] then C=[0.6 2.0 0.3 -0.3]. Another convolution can be the concatenation: CO=[0.3,2.0 0.5,4.0 0.1,3.0 -0.3,1.0]. If the lists are not the same length, then the length of the result is equal to the smaller of the two lengths. For example if W=[0.3 0.5 0.1] and L=[2.0 4.0 3.0 1.0] then CO=[0.3,2.0 0.5,4.0 0.1,3.0].
Implement the convolve operation on lists. We recommend that you approach this problem as follows:
Plan out how you will implement convolve on two specific lists to produce a specific output (e.g. ILoString and ILoNumber producing ILoString). This operation should not need any other methods, so you can write these classes out quickly with just the convolve operation and any helpers it needs.
Although you do not have to write complete working code with tests for this step, it will really help you in the next steps if you do.
Hint: We have two different lists. Double-dispatch is our friend!
Generalize the method signature of the convolve method for IList<T>. Remember to identify what function objects you would need, and what to return. As the above examples show, the same two lists may be convolved into lists of different types. Getting this step right is half the battle, so make sure you spend some time with this!
Create empty implementations of this method in the ConsList<T> and MtList<T> classes.
Create examples and write tests for the convolve operation on IList<T> now. This will allow you to clearly visualize how these methods will be used.
Look at your implementation for the specific lists, and plan the generic implementation. This usually means a line-by-line translation of the code, replacing specific operations with more general-purpose operations.
Repeat the last four steps for any helpers. Again, first get the signatures right!
6.1.3 A Pair sequence
Use the convolve operation to create a list that creates a list of pairs of the objects in the two lists. For example, a list of months of the year and a list of the number of days in each months can be convolved into a list of (month,days) pairs.