To get your participation credit, make sure you
upload your Definitions file to turnin before you leave the lab!
(This work will not be graded---full credit just for submitting.)
map
and filter
, Racket's loops
You need to use Intermediate Student with Lambda language level for this lab!
Put your name in a comment at the top of the Definitions area.
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 each of the following functions using filter
and/or map
, or argue why it cannot be written using these
(in which case you do not need to write the function).
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 total-stock
that consumes an
inventory and produces the total number of copies of CDs that are in stock.
Write a function copies-in-stock
that consumes an inventory, a CD
title and artist name, 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 an inventory, a CD title
and artist name, and produces a boolean indicating whether that item is
in the inventory (whether in or out of stock).
For these exercises, we will work with the following data
definition for binary trees (notice that
the contract for node
appears inside the contract for bintree
):
;; A bintree[alpha] is either ;; - false, or ;; - (make-node alpha bintree bintree) (define-struct node (item left right))
Write the template for functions over bintrees. You can check
for false using boolean?
.
Write a function sign-tree
that consumes a
bintree[number] (i.e., a bintree where the items at each node are
numbers) and returns a bintree[symbol] with the same structure as the
input tree, but with each number replaced with one of the symbols
'positive, 'negative, or 'zero, as appropriate.
Write a function flip-tree
that consumes a
bintree[posn] and returns a bintree[posn]. The returned tree should
have the same structure as the input tree, but each posn should have
its x- and y-coordinates flipped, i.e., (make-posn 3 4)
would become
(make-posn 4 3)
.
Recall that (define-struct posn (x y)) is built into DrRacket.
The functions sign-tree
and flip-tree
have a similar structure. Write a function tree-map
that
takes a bintree and a function and applies the function to each node
in the tree. Show how to implement sign-tree
and
flip-tree
using tree-map
. Be sure to
include a correct contract for tree-map
.
Write a function tree-andmap
that consumes a
function of type (alpha -> boolean) and a bintree[alpha] and returns a
boolean indicating whether the given function returned true at every
node. Can you implement tree-andmap
using a simple call
to tree-map
? By "a simple call", I mean can you just
fill in the ... in the code below to implement this function? If not,
why not?
(define (tree-andmap func abt) (tree-map ...))
Note: to check whether a value is false
, you can use
(and (boolean? value) (not value))
Using tree-andmap
, implement pos-tree?
that consumes a bintree[number] and determines whether all numbers in
the tree are positive.