Due: Tuesday, Nov 23, end of your lab session
Lab 9: Higher-Order Functions
This week, you will practice programming with higher-order functions. The use
of higher-order functions provides alternatives to the recursive
function templates you have been using so far. In fact, once you are
familiar with their use, you will in many cases prefer higher-order
alternatives to functions that are explicitly recursive.
Today, you will be using three common built-in higher order functions,
map, filter and
the family of fold functions.
Preliminaries: Data Structures
We will develop the definitions of a
bill (phone bill) and a
plan (calling plan) as follows.
A weekday is one of the following symbols:
'Sun, 'Mon, 'Tue, 'Wed, 'Thu, 'Fri, 'Sat.
A call is either a us
or an intl.
A us (for calls within the US) is a
(make-us min day)
where min is a number of minutes and
day is a weekday.
An intl (for international calls) is a
(make-intl min day)
where min is a number of minutes and
day is a weekday.
A bill is a list of calls.
Note: all calls that are part of a given bill
should be understood to have happened in the same
month.
A plan is a
(make-plan monthly-fee us-rate intl-rate free-days)
where monthly-fee is number of dollars,
us-rate is a number of cents per minute,
intl-rate is a number of cents per minute,
and free-days is a list of
weekdays.
Here's a sample calling plan:
(make-plan 50 5 80 (list 'Sat 'Sun))
This plan costs $50 per month, plus 5 cents per minute for all domestic calls,
80 cents per minute for all international calls, but nothing extra for
calls made on Saturday or Sunday.
Another plan might have no monthly fee, but high prices for
individual calls, and no free days:
(make-plan 0 25 100 empty)
You may assume for the sake of simplicity that all phone calls take
place entirely on a single day.
You should convince yourself that you could more realistically model
an actual calling plan with straightforward modifications to the model
presented here, such as recording dates, times and phone numbers
along with the lengths of calls, and maintaining a
richer rate structure.
Part 1
[Note: For full credit complete functions call$,
bill$, us-calls, intl-calls, us% and intl%).
For check+ credit, you should also complete functions best-plan and best-plan/list.
There will be no homework based on this lab.]
Define the following
functions, using map, filter
and foldl/foldr wherever possible:
- , to return a number of
dollars a particular call costs under a given plan,
- , to return a number
of dollars a bill costs under a given plan,
- , to return only
the domestic calls on a given bill,
- , to return only
the international calls on a given bill,
- , to return the
percent of money spent on domestic calls on a given bill,
- , to return the
percent of money spent of international calls on a given bill.
For check+ credit, define the following functions:
- , to
determine the plan yielding the lowest cost for a given bill, and
- , to
determine the plan yielding the lowest total cost for a given list
of bills.
You may wish to revert to the design template for the last two functions.
Verify your functions by testing carefully.
Hand in your work
To receive full credit, you should complete the first 6 functions in Part 1 (functions call$,
bill$, us-calls, intl-calls, us% and intl%).
For check+ credit, you should also complete functions best-plan and best-plan/list.
There will be no homework based on this lab.
Save all your files and submit all your work according to the submission instructions.
Material designed by Adam Shaw.