## CS 330 Lecture 32 – Filter and Memoization

*April 24, 2015 by Chris Johnson. Filed under cs330, lectures, spring 2015.*

### Agenda

- what ?s
- program this
- type synonyms
- memoization

### Intentions

- I can use the filter pattern with custom predicates to extract a subset of data.
- I can employ memoization to cache and quickly recall the results of function calls.

### Program This

- Write a function
`maxAll`

that accepts a list of numbers and yields the maximum.

### Problems

- Write a function
`nonzeroes`

that accepts a list of numbers and yields a list containing only the nonzero elements. For example, `nonzeroes [0, 1, -3, 0]`

yields `[1, -3]`

.
- Write a function
`overs`

that accepts an n and a list of strings and yields a list containing only those strings whose length is greater than n. For example, `overs 3 ["the", "quick", "brown", "fox"]`

yields `["quick", "brown"]`

.
- Write a type synonym for a String-Double pair called
`RatedMovie`

. Write a function `rejects`

that accepts a list of `RatedMovie`

s and yields a subset of those with less than 2 star ratings.

### Code

#### Doowop.hs

import Data.Function.Memoize
foldr' mix accum [] = accum
foldr' mix accum (first:rest) = foldr' mix (mix accum first) rest
maxAll :: (Ord a) => [a] -> a
maxAll [] = error "no max"
maxAll (first:rest) = foldr' (\maxSoFar usurper -> if (maxSoFar > usurper) then maxSoFar else usurper) first rest
-- maxAll (first:rest) = foldr' max first rest
nonzeroes :: [Int] -> [Int]
nonzeroes [] = []
nonzeroes (first:rest)
| first == 0 = nonzeroes rest
| otherwise = first : nonzeroes rest
filter' :: (t -> Bool) -> [t] -> [t]
filter' predicate [] = []
filter' predicate (first:rest)
| predicate first = first : filter' predicate rest
| otherwise = filter' predicate rest
type RatedMovie = (String, Double)
rejects :: [RatedMovie] -> [RatedMovie]
rejects = filter' (\(_, rating) -> rating < 2)
fib' x
| x <= 1 = x
| otherwise = fib' (x - 1) + fib' (x - 2)
fib = memoize fibhelper
where
fibhelper :: Int -> Int
fibhelper x
| x <= 1 = x
| otherwise = fib (x - 1) + fib (x - 2)

### Haiku

**on cache misses**

Ask a child questions

It puts a hole in their brain

That wants to be filled

Chris could you please post the code from this lecture.

Thanks!