» CS 330 Lecture 34 – Fold, Tail Recursion, and Lambdas

CS 330 Lecture 34 – Fold, Tail Recursion, and Lambdas

April 23, 2014 by Chris Johnson. Filed under cs330, lectures, spring 2014.

Agenda

what ?s
think about this
all, any, sum, product, size, join
tail recursion
fold/reduce/inject
lambdas in Java
lambdas in Ruby
lambdas in C++

Think About This

Consider our definitions for map' and filter':

map' f [] = []
map' f (first:rest) = f first : map' f rest

filter' f [] = []
filter' f (first:rest)
  | f first = first : filter' f rest
  | otherwise = filter' f rest

What are the type signatures of map' and filter'?

Code

april23.hs

stringify l = map (\n -> show n) l

all' :: [Bool] -> Bool
all' [] = True
all' (first:rest) = first && all' rest

any' :: [Bool] -> Bool
any' [] = False
any' (first:rest) = first || any' rest

sum' [] = 0
sum' (first:rest) = first + sum' rest

product' [] = 1
product' (first:rest) = first * product' rest

sumTail' sumSoFar [] = sumSoFar
sumTail' sumSoFar (first:rest) = sumTail' (sumSoFar + first) rest

fold' mix accum [] = accum
fold' mix accum (first:rest) = fold' mix (mix accum first) rest

Haiku

Papa Bear: “Names shnames.”
Mama Bear: “Name your whitespace.”
Baby bear: “Lambdas.”