980 views
# CS 200 Lecture 2 (from OO): map, filter, testing (by Milda Zizyte and Kathi Fisler) ## Records A record in Java is a lightweight, immutable class that lets you group data together. “Immutable” means that the data cannot be changed after it’s created. To create a record, create a new Java file (e.g. Boa.java) and use the following syntax: ```=java public record Boa(String name, int length, String eats) { } ``` After we instantiate a record, we can print the record and access its fields (this code was in the main method of Lec02.java): ```=java Boa fredBoa = new Boa("Fred", 20, "lettuce"); System.out.println(fredBoa); System.out.println("Fred eats: " + fredBoa.eats()); ``` What we cannot do is change any value of fredBoa’s fields after we have already created fredBoa: ``` // NONE OF THESE WILL WORK because fredBoa (and all record instantiations) is immutable: // fredBoa.length = 40 // fredBoa.length() = 40 // fredBoa.setLength(40) ``` Instead, we can make new Boas based on the values in fredBoa: ```=java Boa longFred = new Boa(fredBoa.name(), fredBoa.length() * 2, fredBoa.eats()); System.out.println(longFred); ``` We can also write methods to work with Boas (we created these methods in Lec02.java): ```=java // returns true if the input Boa eats lettuce or carrots public static boolean isVeg(Boa b) { return b.eats().equals("lettuce") || b.eats().equals("carrots"); } // returns a new Boa, triple the length of the input Boa public static Boa growBoa(Boa b) { return new Boa(b.name(), b.length() * 3, b.eats()); } ``` ## Tests One thing we will practice in CS 200 is using tests as examples that show that our methods are working (i.e. that the expected values match the actual results of the method call). The following tests were written in Lec02Test.java (note you need the @Test annotation to make the test run) ```=java @Test public void simpleBoaTest() { Boa testBoa = new Boa("Test", 12, "Java"); Assert.assertEquals(12, testBoa.length()); } @Test public void testIsVeg() { Boa b1 = new Boa("B1", 2, "lettuce"); Boa b2 = new Boa("B2", 3, "profs"); Boa b3 = new Boa("B3", 900, "carrots"); Assert.assertTrue(Lec02.isVeg(b1)); Assert.assertFalse(Lec02.isVeg(b2)); Assert.assertTrue(Lec02.isVeg(b3)); // the test below would have failed: //Assert.assertFalse(Lec02.isVeg(b3)); } // test for Lec02.growBoa, which is supposed to triple a boa's length @Test public void testGrowBoa() { Boa b1 = new Boa("Fred", 20, "lettuce"); Boa b2 = new Boa("Rude guy", 10, "profs"); Assert.assertEquals(60, Lec02.growBoa(b1).length()); Assert.assertEquals(10 * 3, Lec02.growBoa(b2).length()); Assert.assertEquals("Rude guy", Lec02.growBoa(b2).name()); } ``` ## Immutable Lists Just as we might have immutable data like Boas, we might have immutable lists. With an immutable list, operations like add and remove return a new list that shows the result of the requested operation on the original list, As the name suggests, they do not modify the existing list. The FuncList class in our lecture code implements such a list. Here’s an example (the link method makes a list with the given value at the front of the existing list): ```=java FuncList<Integer> scoreList = new FuncList<>(); scoreList.link(98); scoreList.link(75); scoreList.link(82); System.out.println(scoreList); ``` Why is scoreList empty? Did the link not work? ```=java System.out.println(scoreList.link(98)); ``` The link worked fine. The contents of scoreList didn’t change, as fitting with an immutable list. We instead have to write: ```=java scoreList = scoreList.link(98).link(75).link(82); ``` ### Dealing with lists of Boas We can put Boas into a immutable list (in the main method of Lec02.java). ```=java FuncList<Boa> boaList = new FuncList<Boa>(); boaList = boaList.link(fredBoa).link(new Boa("Lily", 80, "ants")); ``` In CS 15, if you had wanted to see which Boas in this list were vegetarian, you might have written something like (in the main method of Lec02.java): ```=java for (Boa b: boaList) { if (isVeg(b)) { System.out.println(b); } } ``` This doesn’t work, however, because the FuncList class isn’t set up to use for loops (we’ll discuss why later). In functional programming, we think more about what kind of list processing we want to and use custom operations for different kinds of processing. What do we mean? Consider these examples assuming you had a list of records about flights from Providence (each with a flight number, destination city, and departure time): 1. get a list of all flights that go to Denver 2. get a list of all flights that leave before 9am 3. get a list all the destinations that one can fly to from Providence 4. get the earliest flight that goes to Chicago after noon 5. create a new schedule (list of flights) in which all flights depart 5 minutes earlier 6. create a new schedule (list of flights) in which all flights to Chicago on United leave 10 minutes later 7. renumber the 2:30 flight to Atlanta on Delta to 4512 Step back and ask ourselves: what kind of task do we want with the list in each case? 1. select a list of flights based on a criterion 2. select a list of flights based on a criterion 3. select a list of flights based on a criterion, remove duplicates 4. select a list of flights based on a criterion, sort it, and return the first element 5. transform a list of flights into a new list of flights 6. transform into a new list of flights where some elements are unchanged 7. transform into a new list of flights where some elements are unchanged Described this way, we start to notice patterns: selection is common, transformation is common, operations like sorting and removing duplicates come up from time to time. In Java, you would have done all of these with for-loops. In functional languages, we use a set of build-in list operations that do these different kinds of tasks. Here’s a collection of `FuncList` operations for these tasks (we’ll get to the `Function` type in a moment): ```=java public IFuncList<T> filter(Function<T,Boolean> pred); // select public <R> IFuncList<R> map(Function<T,R> transform); // transform public IFuncList<T> takeWhile(Function<T,Boolean> pred); //select prefix public FuncList<T> distinct(); // remove duplicates public double sum(); // sum a list of numbers ``` For programming with immutable lists, we break problems into combinations of these operations. We’ll see how this works back on the boas: ### Back to the Boas #### filter A way of getting back a list of just the vegetarian Boas would be (in the main method of Lec02.java): ```=java FuncList<Boa> vegBoas = boaList.filter(b -> isVeg(b)); System.out.println("with filter:"); System.out.println(vegBoas); ``` The expression `b -> isVeg(b)` is a shorthand for writing a function that takes in one input (here named b) and produces the result of running `isVeg` on `b`. The overall filter expression says: As you go through the boaList, give every item the name b in turn. Now call isVeg on b. The filter only keeps the elements of boaList for which the predicate evaluates to true. #### map Instead of using predicates to decide whether to keep elements from a list, we can also use them with a mechanism called “map” that applies a method/function to every item in the list and returns a new list with the result. To see an example of this, say we wanted to grow the length of every Boa in a list. We could write a predicate that applies growBoa to every element and put that predicate as an input to map (in the main method of Lec02.java): ```=java FuncList<Boa> looongBoas = boaList.map(b -> growBoa(b)) System.out.println("map to grow the boas:"); System.out.println(looongBoas); ``` In the IFuncList interface, the Java type `Function<T,R>`` means “a function that takes one input of type T and returns an output of type R”. The notation for writing a function is ```=java elem -> expression ``` where elem is the variable name you want to use for list elements (like b) and expression is what you want to compute. Concretely, here are the for-loop version and the filter-version to create a list of vegetarian boas: ```=java // for-loop version ArrayList<Boa> vegs = new ArrayList<>(); for (Boa b: boaList) { if (isVeg(b)) { vegs.addLast(b); } } // filter version boaList.filter(b -> isVeg(b)); ``` Notice that the list element name `b` in the for-loop version is the name of the function input in the filter version. The test expression in the for-loop version is the expression in the filter version. Here is a corresponding example for map: ```=java // for loop version ArrayList<Boa> long = new ArrayList<>(); for (Boa b: boaList) { long.addLast(growBoa(b)); } // map version boaList.map(b -> growBoa(b)); ``` What if we wanted to grow just the vegetarian boas? Is that a filter? a map? a combination? The answer lies in the OUTPUT of the operations: with filter, we produce a subset of the original list. with map, we produce a list of the same length as the input list (though perhaps with a different type). To grow the veg boas, we would perform a map, using a method that generates a new Boa only when the original Boa is vegetarian: ```=java Boa growIfVeg(b: Boa) { if (isVeg(b)) return growBoa(b); else return b; } boaList.map(b -> growIfVeg(b)); ``` #### Writing examples for map/filter We can write tests (examples) for map/filter using the same idea of expected vs. actual results. Here is an example of doing that to make sure that our filter expression only gets the odd numbers in a list (in Lec02Test.java). `Arrays.asList` is just a shortcut way of quickly initializing a list for testing. ```=java @Test public void testOdd() { FuncList<Integer> numList = new FuncList<Integer>().link(5).link(3).link(8).link(0); FuncList<Integer> expectList = new FuncList<Integer>().link(5).link(3); FuncList<Integer> oddList = numList.filter(n -> n % 2 == 1); Assert.assertEquals(expectList, oddList); } ``` Here, we put a simple mathematical expression inside of the predicate, instead of calling a method.