# teaching machines

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

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,