Lecture: Higher-order Functions

Dear students:

There are lots of fascinating choices that language designers have made about functions, but we're going to focus on just one very important feature: higher-order functions. Sometimes our algorithms need us to send them not just data, but also chunks of code.

Blocks

Some languages let us put functions in a variable and pass them around as parameters. You can do this in some form in JavaScript, Java, and even C. Ruby does not let us put functions in a variable exactly. But we can pass around code using blocks.

Suppose we had a list of numbers and wanted to measure the jumps between these numbers: this one is up 9 from the previous, this one is down 7. Suppose also we had an abstraction named each_pair that visited each each consecutive pair of elements in an array. We could use it to solve our problem by passing it a block that examined a pair and printed out a description of the delta:

xs = [1, 5, 3, 8, 20]
each_pair(xs) do |a, b|
  if b > a
    puts "up #{b - a}"
  elsif a > b
    puts "down #{a - b}"
  else
    puts "hold"
  end
end

xs = [1, 5, 3, 8, 20]
each_pair(xs) do |a, b|
  if b > a
    puts "up #{b - a}"
  elsif a > b
    puts "down #{a - b}"
  else
    puts "hold"
  end
end

There's no loop in this code. Nowhere am I getting caught up in the details of the iteration mechanics. The block deals only with a single pair of elements at a time.

The higher-order function each_pair is what actually holds the loop. It walks through the indices and invokes the block using the yield command:

def each_pair(items)
  i = 0
  while i < items.size - 1
    yield(items[i], items[i + 1])
    i += 1
  end
end

def each_pair(items)
  i = 0
  while i < items.size - 1
    yield(items[i], items[i + 1])
    i += 1
  end
end

Any time we need to process consecutive pairs in an array, we can call upon the very reusable each_pair. However, we'd be better off using Ruby's builtin each_cons.

Sometimes we have two separate or parallel arrays that we want to process in tandem, like names and IDs, book titles and authors, and so on. In a language with only loops, we'd write code like this every single time we encounter this problem:

stop = [xs.size, ys.size].min
for i in 0...stop
  # process xs[i], ys[i]
end

stop = [xs.size, ys.size].min
for i in 0...stop
  # process xs[i], ys[i]
end

Wouldn't it be nice if we could abstract this pattern out to a utility function that did everything but the processing? We can. The pattern is called zip, and we can implement it in an each-like fashion:

def each_zip(as, bs)
  stop = [as.size, bs.size].min
  for i in 0...stop
    yield(as[i], bs[i])
  end
end

def each_zip(as, bs)
  stop = [as.size, bs.size].min
  for i in 0...stop
    yield(as[i], bs[i])
  end
end

Suppose that we wanted to produce a new array instead of achieve a side effect. Maybe we want to sum up the two arrays? Or take the larger item of each pair? Then we write a map-like zip:

def zip(as, bs)
  stop = [as.size, bs.size].min
  cs = []
  for i in 0...stop
    c = yield(as[i], bs[i])
    items.push(c)
  end
end

def zip(as, bs)
  stop = [as.size, bs.size].min
  cs = []
  for i in 0...stop
    c = yield(as[i], bs[i])
    items.push(c)
  end
end

Here's how we'd form first- and last-name pairs with our zip:

firsts = %w{Scott Barb Cara}
lasts = %w{Mass Ru Mass}
joins = zip(firsts, lasts) { |first, last| "#{first} #{last}" }

firsts = %w{Scott Barb Cara}
lasts = %w{Mass Ru Mass}
joins = zip(firsts, lasts) { |first, last| "#{first} #{last}" }

Again, Ruby's Array class offers a builtin zip function that we should favor over our own.

Map, Filter, and Fold

Many higher-order abstractions have already been written for us in the Ruby standard library. The most famous of these are map, filter, and fold/inject. All accept a block parameter. Let's examine each of these with a short example:

fs = is.map { |i| i.to_f }

fs = is.map { |i| i.to_f }

swords = words.filter { |word| word.start_with?('S') }

swords = words.filter { |word| word.start_with?('S') }

min = xs.inject { |smallest, x| x < smallest ? x : smallest }

min = xs.inject { |smallest, x| x < smallest ? x : smallest }

Next we give you a chance to be a client of these higher-order functions. I'll present you with a collection of tasks, and you'll solve one of them with your neighbors.

Map

Use map in all answers.

1. Turn an array of words into URLs for looking up their definitions. For example: ["squalor", "dearth"] → ["https://dictionary.com/browse/squalor", "https://dictionary.com/browse/dearth"].
2. Turn an array of counts into array of stars of corresponding length. For example: [3, 1, 0] → ["***", "*", ""].
3. Abbreviate an array of strings to their first two letters. For example: ["Mars", "Venus"] → ["Ma", "Ve"].
4. Halve an array of numbers. For example: [100, 99.2, 99] → [50.0, 49.6, 49.5].
5. Round an array of numbers to nearest multiple of 10. For example: [87, 7, 432] → [90, 10, 430].
6. Extract an array of keys (as strings) from a hash. For example: {author: "Barbara Picard", title: "One is One", year: 1965} → ["author", "title", "year"].

Filter

Use filter in all answers.

1. Keep names that have a space. For example: ["van Gogh", "Granger", "Hernandez Rivera"] → ["van Gogh", "Hernandez Rivera"].
2. Keep key-value pairs where the key is shorter than the value. For example: {"Barack": "Michelle", "Jada": "Will", "Taylor": "Travis"} → {"Barack": "Michelle"}.
3. Keep numbers within [0, 100]. For example: [-57, 20, 100] → [20, 100].
4. Keep words that are all uppercase. For example: ["NO", "Sugar", "CAN"] → ["NO", "CAN"].
5. Keep strings that contain a digit. For example: ["l8r", "bus", "ground0"] → ["l8r", "ground0"].
6. Keep numbers that are multiples of both 4 and 3. For example: [48, 16, 120] → [48, 120].

Fold

Use inject in all answers.

1. Extract the key-value pair with the smallest value. For example: {"Waynesboro" => 7, "Harrisonburg" => 3, "Staunton" => 9} → ["Harrisonburg", 3].
2. Report if all numbers are negative. For example: [-3, 10] → false.
3. Sum up the even numbers. For example: [2, 19, 14] → 16.
4. Extract the longest string. For example: ["sheetz", "pilot", "liberty"] → "liberty".
5. Build an acronym. For example: %w{you only live once} → "yolo".
6. Count the number of strings containing a Z. For example: %w{tizzy wizard} → 3.

TODO

Here's your list of things to do before we meet next:

See you next time.

P.S. Here's a haiku for you!