CS 330: Lecture 27 – Lambdas and Higher-Order Functions
Dear students:
Let’s start with a Program This:
Using composition and point-free style, write a function that yields the square of the elements’ sum. UsingHere’s my solution.sumand^. It might help to start without composition and point-free style.
squaredSum :: Num a => [a] -> a
squaredSum list = sum list ^ 2 -- the old way
squaredSum = (^2) . sum -- the hip way
I think we should write a few more compositions together.
- Let’s write
scalebiasto map a value using a linear function:Now we writescalebias :: Double -> Double -> Double -> Double scalebias scale bias x = scale * x + bias -- without composition scalebias' scale bias = (+ bias) . (* scale) -- with composition
calc2fahrenlike we should have back in high school:c2f :: Double -> Double c2f = scalebias' 1.8 32
- Let’s write a function that gives us a list of the unique items within another list:
onlies :: Ord a => [a] -> [a] onlies = concat . filter single . group . sort where single list = length list == 1
- Let’s write a function that gives us the mode in a list of data:
mode :: Ord a => [a] -> a mode = head . head . reverse . sortWith length . group . sort
What do you suppose the type signature of . is? Recall that f . g is the same as f(g(x)). If g has type a -> b, that means that f must accept a b. Who knows what it produces. Therefore, the type of the compose operator is something like (.) :: (b -> c) -> (a -> b) -> (a -> c).
Both partial evaluation and composition eliminate a lot of the overhead that we programmers find ourselves doing. Much of our development life is spent gluing together abstractions into some mega-abstraction, and these two techniques give us some of our life back.
Lambdas are expressions that yield a function, but which don’t give it a name. This lambda adds 1 to its parameter:
\x -> x + 1
This lambda reports if its parameter is the empty list or a list with one element:
\l -> null l || length l == 1
The general grammar of lambdas is this:
\param1 param2 param3 -> definition
Pattern matching is legal in the formals list. Here’s a lambda for swapping fields in a 2-tuple:
\(a, b) -> (b, a)
I could assign these lambdas to identifiers:
add1 = \x -> x + 1
few = \l -> null l || length l == 1
But that’s not usually what we do. If we wanted a named function, we would have used that syntax. Instead, lambdas love to be anonymous. They love to be used for a moment and thrown away. They are firecrackers. We light them and toss them into the hands of our friend functions, where they explode in glory.
Those functions that are willing to take on other functions as parameters are called higher-order functions. We’ve seen at least one of them: filter. Let’s write a function that filters out all the numbers in a particular range:
innies :: Ord a => a -> a -> [a] -> [a]
innies lo hi = filter (\x -> lo <= x && x <= hi)
Let’s use a lambda to write a function that gives us back a list of only the non-duplicated items in a list:
onlies :: Ord a => [a] -> [a]
onlies = concat . filter (\list -> length list == 1) . group . sort
Let’s also write count, which is a higher-order function that accepts a predicate and a list. It runs this algorithm:
count = 0
for each element in list
if predicate is true of element
count += 1
return count
We implement this in Haskell like so:
count :: (a -> Bool) -> [a] -> [a]
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 two of those patterns today and implement their abstractions in Haskell. Eventually we will look at them in other languages.
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..]
And there we go. See you next time!
P.S. It’s time for a haiku!
I don’t name functions
Otherwise I’m a puddle
When I send them HOF
P.P.S. Here’s the code we wrote together:
lecture.hs
import Data.List
scalebias scale bias = (+ bias) . (* scale)
c2f = scalebias (9 / 5) 32
c2k = scalebias 1 273.15
-- onlies :: [a] -> [[a]]
onlies :: Ord a => [a] -> [a]
onlies = concat . filter single . group . sort
where single l = length l == 1
innies lo hi = filter (\v -> lo <= v && v <= hi)
count :: (a -> Bool) -> [a] -> Int
count _ [] = 0
count predicate (first : rest)
| predicate first = 1 + count predicate rest
| otherwise = count predicate rest