CS 330 Lecture 25 – Filter, Map, and Foreach
Dear students,
Let’s start with a Program This:
Write in Haskell a functionHere’s my solution.countthat accepts a predicate and a list. It yields the number of elements for which the predicate is true. We’d write it like is in an imperative way:count = 0 for each element in list if predicate is true of element count += 1 return countStart by writing the type signature!
count :: (a -> Bool) -> [a] -> Int count _ [] = 0 count predicate (first:rest) | predicate first = 1 + count predicate rest | otherwise = count predicate rest
We can use lambdas with count!
count (\(a, b) -> a < b) [(1, 2), (3, 3), (4, 5), (11, 10)] count (\s -> length s < 5) ["I", "think", "it's", "impossible", "to", "really", "understand", "somebody", "what", "they", "want", "what", "they", "believe", "and", "not", "love", "them", "the", "way", "they", "love", "themselves"]
Lambdas are pretty great, but be careful. What’s wrong with these?
count (\x -> x > 0) [-3..3] count (\c -> isUpper c) "You Get What You Need" count (\x -> x % 2 == 0) [-4..4]
All three of these are cases of UFW—unnecessary function wrapping. We have existing functions that do the same thing, and there’s no need to define a new one:
count (> 0) [-3..3] count isUpper "You Get What You Need" count even [-4..4]
Now, we’ve seen how easy it is to define functions on the fly and hand them off to other functions. Think about what this means for those tired old patterns we have been writing in our code. How many loops have you written that have the exact same structure, with the only difference being how you act on an element. Or how you combine it with the others. We can pull out those repeated parts into a function but push the parts that change into a parameter. That parameter has to be an action—a function.
We’ll look at three of those patterns today and implement their abstractions in Haskell, Java, and maybe Ruby.
Let’s start with filter. In SQL, this is the WHERE clause. We want to reduce a collection to some subset matching some criteria. That criteria is the hole that we must leave blank, but the looping structure is the same everytime:
keepers = []
for each item in list
if keeper meets criteria
append item to keepers
Does this algorithm look familiar to you? It should. It’s a lot like count. In Haskell, we can write it like so:
filter' :: (a -> Bool) -> [a] -> [a] filter' _ [] = [] filter' predicate (first:rest) | predicate first = first : filter' predicate rest | otherwise = filter' predicate rest
Now let’s create a collection on which to test this. First we’ll make a new Planet datatype:
-- A planet is a 3-tuple of name, distance from sun in AU, and planet-Earth size ratio data Planet = Planet String Double Double deriving Show
Then we can make a list:
planets = [
Planet "Mercury" 0.4 0.055,
Planet "Venus" 0.7 0.815,
Planet "Earth" 1.0 1.0,
Planet "Mars" 1.5 0.107,
Planet "Jupiter" 5.2 318.0,
Planet "Saturn" 9.5 95.0,
Planet "Uranus" 19.6 14.0,
Planet "Neptune" 30.0 17.0
]
We can grab a list of all the planets with more mass than Earth:
massierThanEarth (Planet name, au, mass) = mass > 1.0 massiers = filter' biggerThanEarth planets -- or using a lambda massiers' = filter' (\(Planet _ _ mass) -> mass > 1.0) planets
We can grab a list of all the planets inside the asteroid belt, whose inner radius is about 2.2 AUs:
prebelters = filter' (\(Planet _ au _) -> au < 2.2) planets
We can grab a list of all the planets that have a U in their name:
us = filter' (\(Planet name _ _) -> elem 'u' name) planets
The key idea here is that we wrote filter' once. We wrote the iteration once. We never had to write it again. We only jammed a lambda into the hole it left open in the algorithm.
The next pattern we’ll visit is map. It abstracts this general algorithm:
news = array same size as olds for each item in olds news[i] = transform olds[i] return news
What does this look like in Haskell?
map' :: (a -> b) -> [a] -> [b] map' _ [] = [] map' xform (first:rest) = xform first : map' xform rest
We can turn a list of planets into a list of planet names:
map' (\(Planet name _ _) -> name) planets
We can append , Lord of Catan to a bunch of names:
map' (++ ", Lord of Catan") ["Alice", "Bob", "Carol", "Diphthong"]
We can generate a never-ending sequence of even numbers:
map' (*2) [1..]
Here’s your TODO list:
- Don’t come to class on Friday. I will be at a conference with three students presenting their research.
See you next time, when we discuss the function to end all functions: fold/reduce/inject!
