teaching machines

CS 330: Lecture 27 – Lambdas and Higher-Order Functions

April 13, 2018 by . Filed under cs330, lectures, spring 2018.

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. Using sum and ^. It might help to start without composition and point-free style.

Here’s my solution.
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.

  1. Let’s write scalebias to map a value using a linear function: 
    scalebias :: Double -> Double -> Double -> Double
scalebias scale bias x = scale * x + bias     -- without composition
scalebias' scale bias = (+ bias) . (* scale)  -- with composition
    Now we write calc2fahren like we should have back in high school: 
    c2f :: Double -> Double
c2f = scalebias' 1.8 32
  2. 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
  3. 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!

Sincerely,

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