CS 330 Lecture 27 – Fold
Dear students,
Let’s start with a Program This! Complete two of the following functions based on your row number. All of them accept a list. Solve them using the pattern-matching style, with base cases and general cases defined separately. All of them should be two-liners.
upped, which generates an uppercase version of the incomingString(usetoUpper :: Char -> Char)any, which yields true if any of the boolean elements of the list is true, and false otherwiseproduct, which yields the product of all the elements in the listsize, which counts the number of elements in the listjoin, which concatenates together all the elements of the listtwice, which generates a new list like the original, but with every element doubledsum, which yields the sum of all the elements in the listall, which yields true if all of the boolean elements of the list are true, and false otherwise
You will share your solutions up on the markerboard. From there we will abstract.
What do these solutions all have in common? Well, they all turn a list into some other summary value, whether that summary value is a representative number of another list. How do they different?
- In their “default” or “zero” value that is invoked in the base case.
- In their mixing or combining function, which stirs one of the elements into the summary value.
The abstraction of this algorithm is called fold, and the zero value and the mixing function will be the holes that we leave open. It’s interface will be something like this:
fold mix zero list
Let’s define it, postponing the type signature for a moment:
fold mix zero [] = zero fold mix zero (first:rest) = mix first (fold mix zero rest)
We can apply a few syntactic niceties:
fold _ zero [] = zero fold mix zero (first:rest) = mix first $ fold mix zero rest
Now, let’s rewrite all of our functions from above using fold:
upped = fold (\c rest -> toUpper c : rest) [] any' = fold (||) False product' = fold (*) 1 size = fold (\_ count -> 1 + count) 0 join = fold (++) "" twice = fold (\x rest -> 2 * x : rest) [] sum' = fold (+) 0 all' = fold (&&) True
This rounds out our discussion of the big functional patterns. They should feel like adding SQL queries to our programming languages, ‘cuz we are!
Here’s your TODO list:
- Read An introduction to the java.util.stream library and/or Java 8 Stream Tutorial. On a quarter sheet, identify an interesting “data pipeline” that you have observed in your life that involves at least filtering and mapping. Write a Java method that implements your pipeline: accept a collection of objects, filter it in some way, and map it in some way, and returns an array of the results. Use the streams API.
See you next time, when we discuss Haskell I/O!
