teaching machines

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 RatedMovies 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