## 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 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!