Lab 8

Intermediate Student with Lambda

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.

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.

Your Assignment

Define the following functions, using map, filter and foldl/foldr wherever possible:

call$: plan call -> num, to return a number of dollars a particular call costs under a given plan,
bill$: plan bill -> num, to return a number of dollars a bill costs under a given plan,
us-calls: bill -> bill, to return only the domestic calls on a given bill,
intl-calls: bill -> bill, to return only the international calls on a given bill,
us%: plan bill -> num, to return the percent of money spent on domestic calls on a given bill,
intl%: plan bill -> num, to return the percent of money spent of international calls on a given bill,
best-plan: list-of-plans bill -> plan, to determine the plan yielding the lowest cost for a given bill, and
best-plan/list: list-of-plans list-of-bills -> plan, 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.

For extra credit, write best-plan with foldl or foldr.

Verify your functions by testing carefully.

Submit your work via Chalk as usual.