» CS 330 Lecture 25 – Filter, Map, and Foreach

CS 330 Lecture 25 – Filter, Map, and Foreach

April 5, 2017 by Chris Johnson. Filed under cs330, lectures, spring 2017.

Dear students,

Let’s start with a Program This:

Write in Haskell a function count that 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 count
Start by writing the type signature!

Here’s my solution.

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!

Sincerely,