teaching machines

CS 330 Lecture 32 – Filter and Memoization

April 24, 2015 by . Filed under cs330, lectures, spring 2015.

Agenda

Intentions

Program This

Problems

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

Comments

  1. Brandon C says:

    Chris could you please post the code from this lecture.

    Thanks!

Leave a Reply

Your email address will not be published. Required fields are marked *