» CS 330 Lecture 27

CS 330 Lecture 27 – Fold

April 12, 2017 by Chris Johnson. Filed under cs330, lectures, spring 2017.

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 incoming String (use toUpper :: Char -> Char)
any, which yields true if any of the boolean elements of the list is true, and false otherwise
product, which yields the product of all the elements in the list
size, which counts the number of elements in the list
join, which concatenates together all the elements of the list
twice, which generates a new list like the original, but with every element doubled
sum, which yields the sum of all the elements in the list
all, 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!

Sincerely,