You need to use Intermediate Language Level for this lab.
The material in this lab will not be tested in 1101 -- it's is for your educational enrichment only.
By now, you've noticed that many of the functions we write over lists have the same flavor. For example, consider the following two functions:
;; extract-positives : list-of-number -> list-of-number
;; consumes list of num and produces list of all positive nums in list
;; (uses built-in operator positive?)
(define (extract-positives alon)
(cond [(empty? alon) empty]
[(cons? alon) (cond [(positive? (first alon))
(cons (first alon) (extract-positives (rest alon)))]
[else (extract-positives (rest alon))])]))
;; short-strings : number list-of-string -> list-of-string
;; consumes num and list of string and produces list of all strings shorter than given num
(define (short-strings limit alos)
(cond [(empty? alos) empty]
[(cons? alos) (cond [(< (string-length (first alos)) limit)
(cons (first alos) (short-strings limit (rest alos)))]
[else (short-strings limit (rest alos))])]))
These do almost the same thing, minus the test that they use to
decide whether or not to keep the first item on the list. Shouldn't
we be able to write a helper function that captures all the common
code between these two functions? We certainly could, and as a matter
of fact, that helper is already built-in: it is called
filter. Here's the definition of filter:
;; filter : (alpha -> boolean) list[alpha] -> list[alpha]
;; extracts elements of list for which given keep function returns true
(define (filter keep? alst)
(cond [(empty? alst) empty]
[(cons? alst)
(cond [(keep? (first alst))
(cons (first alst) (filter keep? (rest alst)))]
[else (filter keep? (rest alst))])]))
Notice a couple of things about filter: it takes a function as an argument; that is denoted in the contract as (alpha -> boolean). This is fine -- Scheme lets you pass operators as inputs to other functions. Notice also that the contract uses the greek letter alpha, rather than a type like number or string. That is because filter can work on lists of any type. We use alpha as a variable over types.
Using filter, we could write our original functions as follows:
;; extract-positives : list-of-number -> list-of-number ;; consumes list of num and produces list of all positive nums in list (define (extract-positives alon) (filter positive? alon))
extract-positives is fairly easy -- just send the
operator positive? as the keep?
parameter.
short-strings is a bit harder:
;; short-strings : number list-of-string -> list-of-string ;; consumes num and list of string and produces list of all strings shorter than given num (define (short-strings limit alos) (filter __________ alos))
We can't just put (< (string-length (first alos))
limit) in place of _________, because it is not a function.
Yet we can't easily make an outside function for this, because the
function (a) can only take one argument according to the filter
contract, but (b) needs to use limit. To write this, we
need to show you how to define functions inside other functions.
;; short-strings : number list-of-string -> list-of-string
;; consumes num and list of string and produces list of all strings shorter than given num
(define (short-strings limit alos)
(local [(define (short? astr) (< (string-length astr) limit))]
(filter short? alos)))
Notice that short? looks like any other function
definition, but since it is inside short-strings, it can
refer to the inputs to short-strings without taking them
as inputs itself. You can put as many definitions as you want between
the square brackets of a local (but you can't define the same name
more than once).
Use filter to write the following programs over dillos (recall that
we had (define-struct dillo (length dead?))):
dead-dillos, which consumes a list of dillos and
returns a list of the dead dillos from the list.
live-dillos, which consumes a list of dillos and
returns a list of the live dillos from the list.
short-and-dead, which consumes a list of dillos
and returns a list of dead dillos with length less than 5.
Filter is good for extracting some elements from a list, but we've
written other kinds of list programs as well. Consider a program like
double-all, which consumes a list of numbers and returns
a list of numbers of the same length, but with every number doubled:
;; double-all : list-of-number -> list-of-number
;; consumes list of num and returns list with all nums doubled
(define (double-all alon)
(cond [(empty? alon) empty]
[(cons? alon) (cons (* (first alon) 2) (double-all (rest alon)))]))
For functions like this, that run some function on every element of
a list and return the same size list, Scheme provides a built-in
function called map:
;; map : (alpha -> beta) list[alpha] -> list[beta]
;; returns list of results from applying function to each element
;; of the input list
(define (map f alst)
(cond [(empty? alst) empty]
[(cons? alst) (cons (f (first alst))
(map f (rest alst)))]))
So, for example, we could write double-all as:
(define (double-all alon)
(local [(define (double n) (* n 2))]
(map double alon)))
By combining map and filter, you can write a lot of list programs very compactly.
Assume that we want to develop an inventory database for an online CD store. For each CD, the database stores its title, artist, price, how many copies are in stock, and its category of music (such as rock, blues, or country). Write a data definition for CD inventories.
Write a function all-titles that consumes an
inventory and produces a list of all titles in the inventory.
Write a function titles-in-stock that consumes an
inventory and produces a list of all titles in the inventory with at
least 1 copy in stock.
Write a function restock that consumes a CD title,
number of new copies of that CD and an inventory and produces an
inventory in which the named CD has the given number of additional
copies (and all other CDs remain the same).
Write a function titles-by that consumes an artist name
and inventory and produces a list of titles of CDs by that artist.
Write a function copies-in-stock that consumes a CD
title, artist name and an inventory and produces the number of copies of that item
that are in stock. Return 0 if the named CD isn't in the inventory.
Write a function blues-sale that consumes an inventory
and produces an inventory in which all blues CDs are discounted by 10\%.
Write a function carry-cd? that consumes a title
and artist name and produces a boolean indicating whether that item is
in the inventory (whether in or out of stock).
You can make up a whole host of other functions to write for practice. Be creative!