This assignment is to be done in PLT Scheme/Racket. You should get at least some of these functions written in class on Sept. 16, and do the rest on your own time. You are encouraged to do this in teams of two, both students working together on each function; if you do this, turn in one homework with both names on it.
For all functions, follow the design recipe: each function must have a contract, a good collection of test cases, and a function definition.
In order to get your homeworks graded quickly, I won't actually grade every one of these problems, but rather a sample including problems of various levels of difficulty. The rest are practice. If there's one that you want to make sure I look at, call my attention to it when you turn in the homework.
Switch languages to PLAI for the following exercises, which are
intended to be done using define-type
and
type-case
. Note that PLAI doesn't have
check-expect
, but has several other built-in
forms for testing; look them up in the Help Desk.
Define a data type vehicle
with three variants:
automobile
has a fuel capacity (a number, in gallons) and a fuel
efficiency (a number, in miles per gallon). solar-car
has a top speed (a number, in miles per
hour).bicycle
has a number of gears (an integer).
Define a function range
which takes in a vehicle and
tells how far it can go, as follows: the range of an automobile is its fuel
capacity times its fuel efficiency; the range of a solar-car is its
top speed times 12 (hours of sunlight); and the range of a bicycle is
50 miles.
Define a data type shape
with two variants:
circle
has a numeric radius and a center
(of type posn
; since the PLAI language doesn't have
"posn" built in, you'll need to define it with
(define-struct posn (x y))
).rectangle
has a numeric width, numeric height, and
top-left (of type posn
).
Define a function area
which takes in a shape and returns
its area.
Define a function contains?
which takes in a shape and a
posn
and tells whether the posn is inside the shape.
Modify your data definition so there's a third variant:
union
has two shapes, which we'll call by the
names "a" and "b".area
and contains?
functions to
work correctly for this new variant. area
, you may assume that the
two shapes of a union don't overlap, so you can just add their areas.
(Otherwise this becomes a complicated geometry problem, and that's not
what I want you to worry about right now.) For
contains?
, your function should work correctly regardless
of whether the two shapes overlap.
Define a data type river
with three variants:
spring
has a numeric volume
, how
much water the spring produces (in gallons per hour).section
has a numeric length
(in
miles), and another river
at the far end.branch
has two river
s,
left
and right
.
Define a function volume
that takes in a river and
returns the total amount of water flowing out of it (in gallons per
hour). This is obvious for a spring. For a section, the volume is
the same as the volume at the far end (let's pretend there's no
evaporation). For a branch, the volume is the sum of the volumes of
the two branches.
Define a function max-length
that takes in a river and
returns the longest distance to any spring.
You can do these exercises in either PLAI, Beginner, or Beginner with List Abbreviations language.
Write a function add-up
which takes in a list of
numbers and returns the sum of the numbers.
Write a function any-matches?
which takes in a
string and a list of strings, and tells whether the string matches any
of the strings in the list.
Write a function count-matches
which takes in a
string and a list of strings, and tells how many list
elements match the string (possibly 0).
Write a function count-over
which takes in a
number and a list of numbers, and tells how many list elements are
larger than the specified number.
Write a function average
that takes in a list of
numbers and returns their average. For a first version of this
function, you may assume there is at least one number in the
list. For full credit, your function should generate an
appropriate and user-friendly error message for the empty-list case.
Write a function convert-reversed
that takes in
a list of numbers (which you may assume are all integers in the range
0-9), interprets them as digits in a decimal number, ones place
first (trust me, this makes it easier!), and returns the number
they represent. For example,
(convert-reversed (list 3 0 2 5))
should be
5203.
Write a function dollar-store?
that takes in a
list of numbers -- the prices of things at a store -- and tells whether
or not everything in the store is priced under a dollar.
Write a function multiply-all
that takes in a list
of numbers and returns their product. Hint: What is
the "right answer" for the empty list? It may not be what you think
at first!
Write a function largest
that takes in a non-empty
list of numbers and returns the largest one.
Hint: There are several possible ways to handle the
empty case....
Write a function total-votes
that takes in a list
of candidate
structures (from homework 1) and returns the
total number of votes cast.
Write a function winner
that takes in a list of
candidate
structures and returns the name of the winner,
or the word "tie"
if there was a tie for first place.
(How do you want to handle the empty-list case? I guess we could call
it a "tie"....)
Write a function square-each
that takes in a list
of numbers and returns a list of their squares, in the same order.
For example,
(square-each (list 4 -3 1 12))
should return (list
16 9 1 144)
.
Write a function substitute
that takes in two
strings and a list of strings, and returns a list the same length as
the given list, but with all occurrences of the first string replaced
by the second. For example,
(substitute "old" "new" (list "this" "that" "old" "new"
"borrowed" "old" "blue"))
should return
(list "this" "that" "new" "new" "borrowed" "new" "blue")
Write a function remove-first
that takes in a
string and a list of strings, and returns the same list but with the
first occurrence (if any) of the given string removed. For example,
(remove-first "old" (list "this" "that" "old" "new" "borrowed"
"old" "blue"))
should return
(list "this" "that" "new" "borrowed" "old"
"blue")
.
Define a data type bst
(short for "binary search
tree") with two variants:
leaf
has no fields at all.node
has a numeric value and two
bst
's named "left" and "right".
A proper bst is one in which every node
's value
is larger than any of the numbers in its left bst
, and
smaller than any of the numbers in its right bst
.
Define a function proper-bst?
which takes in a
bst
and tells whether it is proper.
Define a function in-bst?
that takes in a number
and a proper bst
, and tells whether that number appears
in the bst
. Hint: use the assumption
that the bst
is proper to help you efficiently find the
number, if it's there, or know for certain that it isn't there.
Define a function path-to
that takes in a number and a
proper bst
, and returns a list of node values
encountered
on the way from the root of the tree to the number in question (or to
where it would be if it were there). The list should end with the
desired number if it was in the tree.
Define a function insert
that takes in a number and a
proper bst
, and returns a proper bst
just
like the given one, but containing the specified number. If the
number was already there, you may return the exact same
bst
.
Define a function make-bst
that takes in a list
of numbers and returns a proper bst
containing exactly those
numbers. [I left out the word "proper" when I originally gave this assignment.]