» CS 330 Lecture 27 – Map, Filter, and Point-free

CS 330 Lecture 27 – Map, Filter, and Point-free

April 11, 2016 by Chris Johnson. Filed under cs330, lectures, spring 2016.

Agenda

what ?s
special case of list comprehension: map
map examples
filter pattern
partial function evaluation
point-free style

TODO

Read chapter 6 on higher-order functions in Learn You a Haskell for a Great Good. On a 1/4 sheet, write any questions or observations you have plus a function named fgmax that accepts two functions and a list. It yields a new list in which element i is the maximum of the two values computed by applying separately the two functions to element i of the source list. For example, fgmax (+1) (+2) [1..3] trivially yields [3..5] because the second function always wins. This won’t always be true.

Note

We look at a special pattern today. In imperative code, it looks like this:

dst = []
for element in src
  dst << f element

This pattern is usually called a map. We’ll write such a function in Haskell. We’ll also look at another common: filter. Both these patterns require that we pass in functions to take care of the custom work that can’t be abstracted out, making them higher order functions.

Haskell provides some features that make working with functions a pleasant experience. We’ll have a look at partial function application, where we can provide just a subset of a function’s parameters and get back a new function awaiting only the missing parameters. Haskell achieves this feature through currying. Every function really only takes one parameter, but it yields a new function that awaits the remaining parameters.

Code

hof.hs

-- (name, distance from sun in AU, planet-Earth size ratio)
planets = [
    ("Mercury", 0.4, 0.055),
    ("Venus", 0.7, 0.815),
    ("Earth", 1.0, 1.0),
    ("Mars", 1.5, 0.107),
    ("Jupiter", 5.2, 318.0),
    ("Saturn", 9.5, 95.0),
    ("Uranus", 19.6, 14.0),
    ("Neptune", 30.0, 17.0)
  ]

map' :: (a -> b) -> [a] -> [b]
map' _ [] = []
map' f (first:rest) = f first : map' f rest

appenduwec id = id ++ "@uwec.edu"

filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []
filter' pred (first:rest)
  | pred first = first : filter' pred rest
  | otherwise = filter' pred rest

wards = ["the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"]
stopwords = ["the", "an", "a"]

notStopward needle = not (needle `elem` stopwords)

biggerThanEarth (name, distance, size) = size > 1

percents = [42.42, 17.9, 100, 3, 0]
proportions = map' (/ 100) percents

-- proportionalize lop = map' (/ 100) lop
proportionalize = map' (/ 100) -- point-free style