Higher-Order Functions Clinic
1 Introduction
2 Extra TA Hours
3 A Note on Time
4 Map
5 Filter
6 Fold
7 All Three:   Flu Predictor
8 Writing Your Own:   Find
9 Exercise:   A Better Flu Predictor
10 Challenge:   Maximizing Revenue

Higher-Order Functions Clinic

This document was created by Vincent Kubala and the rest of the cs019 TA staff.

    1 Introduction

    2 Extra TA Hours

    3 A Note on Time

    4 Map

    5 Filter

    6 Fold

    7 All Three: Flu Predictor

    8 Writing Your Own: Find

    9 Exercise: A Better Flu Predictor

    10 Challenge: Maximizing Revenue

1 Introduction

Higher-order functions are functions that either consume another function as input, produce another function, or both. In this course, you will typically see higher-order functions that consume another function as input.

The goal of this clinic is to give you exercises that will help you hone your skills and feel comfortable taking advantage of higher-order functions in code that you write. Developing this skill will help you think and communicate about problem-solving in functional programming, and it will make your code faster to write, more compact, and more readable.

2 Extra TA Hours

Extra TA hours will be hosted to help with this clinic exclusively. You can come to ask TAs questions and collaborate (again, ONLY on this clinic) with other students. They will be in the MS Lab (CIT 167) at the following times:

Saturday 10/17: 2-4 pm

Sunday 10/18: 10am-12, 6-8pm

3 A Note on Time

We took your workload into consideration when writing this. Although there are many functions to implement, most of them are one-liners, and this will go very fast if you understand the concepts. You may also decide that you want to do some parts and not others. That’s fine. This is not a graded assignment, so you can do whatever will help you. If you feel that you already understand how to use higher-order functions and want to check your understanding, skip to All Three: Flu Predictor.

We put time into creating this because we agreed that it would have helped us when we took the course. Every minute that you spend on this will pay off and save you time later.

4 Map

map is a useful higher-order function for lists. Given a list, l, of elements of some type T, and a function f that operates on an input of the same type T, map produces a list of the same length, where each element is the result of applying f to the corresponding element in l.

Consider the example below:

fun add2(x :: Number) -> Number:

   x + 2

end

 

check:

   lon = [list: 0, 1, 6, -2]

   map(add2, lon) is [list: 2, 3, 8, 0]

end

Here, mapping add2 on lon produces a list where 2 has been added to every element of lon. This could also have been written more compactly by using a lambda expression:

check:

   lon = [list: 0, 1, 6, -2]

   map(lam(x): x + 2 end, lon) is [list: 2, 3, 8, 0]

end

For more details on lambda expressions in Pyret, see the documentation.

Now that you have revisited lambda expressions and map, try to complete the exercises in hofc-lam-expressions.arr and hofc-map.arr.

5 Filter

filter in a computer program works just like a filter in the real world: some things can pass through, but others cannot. For list l of elements of some type T, you specify which elements can pass through a filter by supplying a function (the predicate) f that consumes elements of type T and produces a Boolean. If the value is true the element is kept; if the value is false, it isn’t. filter produces a list of just those elements in the input for which the predicate produced true. These are in the same order as in the consumed list.

See the example of filter below:

check:

   lon2 = [list: -1, 6, -2, 5, 7, 0, -4]

   filter(lam(x): x > 0 end, lon2) is [list: 6, 5, 7]

end

The second line of code above filters lon2 such that only its positive elements remain.

Now, you should be ready to use filter to complete the exercises in hofc-filter.arr.

6 Fold

fold converts a list of elements of some type T1 into a single value of type T2. You supply fold with a function (we’ll call it the folder) that takes two values of types T1 and T2 and combines them to produce a T2. You also supply a base value of type T2, which is the first T2 used by the folder; subsequent applications of the folder use the previous T2 that it produced.

The following example on a list of numbers, where the function supplied is the addition function and the base is 100, should help illustrate this idea:

check:

   lon3 = [list: 7, 3, 2]

   fold(lam(x, y): x + y end, 100, lon3) is 112

end

The computation carried out by the fold function above is ((100 + 7) + 3) + 2, which evaluates to 112.

Now, you should be ready to use fold to complete the exercises in hofc-fold.arr.

7 All Three: Flu Predictor

This section is designed to help you assess your ability to use map, filter, and fold together.

Imagine the following scenario. You have created a mathematical model that accurately assesses the probability that a given person will get the flu this year, based on several features (perhaps that person’s age, the number of people who live with them, and some others). Using a simple program, you apply this model to a list of several people given data on their relevant features, producing a list of corresponding probability numbers, one for each person. However, sometimes, some of the data for a person is missing. When this happens, the program stores -1 instead of a probability number for this person so that the program does not crash when the model tries to use values that do not exist. Thus, the output of the program is a list of numbers, where each is either a probability, from 0 to 1, inclusive, or -1.

Each of the functions in the Flu Problems section operates on the output list of data. Implement the functions in hofc-flu.arr, remembering to take advantage of map, filter, and fold wherever appropriate and to abstract out any repetitive code.

8 Writing Your Own: Find

You can, of course, create your own higher-order functions! Some of these will be of general use, while others will be useful for a specific application you are creating.

find is a higher-order function on lists that produces the first element of a list that satisfies a given predicate (a term we defined earlier). Look at the Pyret documentation for example input-output pairs of find.

You’ll notice that find produces an Option. You may not have seen this datatype before, but it is very useful in cases, like this one, in which for some inputs a function may not be able to produce a meaningful output. You can find out more about Options in the Pyret documentation.

Implement your own version of find by completing the stencil code for my-find in hofc-make-your-own.arr.

9 Exercise: A Better Flu Predictor

A better version of the Flu Predictor would have used the Option type for probabilities—to indicate that one might not exist—rather than the magic value -1. In general, you should not use magic values like this: you’re more likely to make mistakes in your program. Consider rewriting your Flu Predictor to use the Option type, so that only true probability values are represented by numbers.

10 Challenge: Maximizing Revenue

This last problem involves a lot of the skills that you worked on above, and it should prove to be at least moderately more challenging than all of the previous exercises. You are encouraged to come to hours if you have trouble solving it.

For the purposes of this exercise, a demand function is simply a function that maps the price of a good to the total quantity of that good that people will buy. A typical demand function decreases with price, since as price of a good increases, it is usually the case that fewer people are interested in purchasing it.

A firm (which, for simplicity, sells only one good) that wants to maximize its revenue, the amount of money that it receives from customers, faces a trade-off: increasing its price will decrease the number of goods that it sells but increase the amount of money that it earns for each one sold, and decreasing its price will do the opposite. Your job is to define a higher-order function, best-price, which takes in a demand function and a list of price choices and produces the price choice that will generate the greatest revenue for the firm. If two prices tie for generating the most revenue, choose the price that comes first in the input list.

Hint: You may find using the higher-order function map2 convenient for part of this problem.