Lab 6: Higher-order functions
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
Submission: For this lab, you will submit your solutions to the tasks in Section 6.1.1 The submission is due at the end of your lab period. You may work with your lab partner on this, but your submission will be individual. This will be graded for correctness and design. Note that TA remarks about what you may or may not lose points for are not the final word. They often do not have final rubrics and cannot answer grading questions.
6.1 Higher-order functions
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.
Note that we are using the functions provided from Java’s functional interfaces rather than the ones we developed in class. 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.