teaching machines

CS 330 Lecture 33 – Fold

April 25, 2016 by . Filed under cs330, lectures, spring 2016.




Today we round out our discussion of the fold pattern. We start by implementing join and illustrating its execution. Then we see just how encompassing fold is in a Program This:

Write function map using our fold' function. Recall that it accepts a transformation function, applies it to each element in the list, and gives back a new list.

If you finish early, consider how we might write filter as a fold.

Back to join, what if we wish to separate the the strings with some text? What do we do to support that?

Let’s also implement maximum and minimum.



-- fold' glom identity list 

fold' _ identity [] = identity
fold' glom identity (first:rest) = glom first (fold' glom identity rest)

join' :: [String] -> String
join' = fold' (++) ""

map' xform = fold' (\x accum -> xform x : accum) []
filter' pred = fold' (\x accum -> if pred x then x : accum else accum) []

maximum' [] = error "You are maximum error."
maximum' (first:rest) = fold' max first rest