This assignment is to be done in PLT Scheme/Racket, PLAI language. You should get at least 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. I recommend using define/contract and
define-struct/contract whenever you can, in order to catch
type errors as early as possible.
Using the definition of person from class,
write a function older? that takes in two
persons and tells whether the first is older than the
second.
Using the definition of candidate from class,
(define-struct/contract candidate ((name string?) (votes integer?)))
write a function who-won that takes in three
candidates and returns the name of the winner, or
"tie" if there's a tie for first place.
Write a struct definition to represent a time of day, with hours, minutes, and seconds. (Assume a 24-hour clock.)
Write a function secs-since-midnight that takes in
one of your time-of-day objects and returns the number of seconds since
the most recent midnight.
Write a function add-a-vote which takes in a
candidate and returns one just like it, but with one more
vote.
Write a function add-a-second which takes in a
time-of-day object and returns another one a second later. (Note that
the number of seconds should not exceed 59, the number of minutes
should not exceed 59, and the number of hours should not exceed
23.)
Note: To write a function contract involving
lists, use the built-in listof function, which takes in a type predicate
and returns a type predicate. For example, (listof integer?) is a
type predicate that checks whether something is a list of integers; if it isn't a
list, or if any of the elements aren't integers, it'll complain.
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 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 (using define-type)
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 (using define-type)
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 rivers,
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.
Let's try to describe a person's family tree.
A person has a name, a year of birth, and an eye color
(a string, an integer, and a string respectively). A person also has
a mother and a father; what types should they be? The obvious answer is
"person"... except that then they in turn have to have mothers and
fathers, and so on, and you can never finish writing down even one
example of a person. And in practice, sometimes you run out of
information: you may know about yourself, your parents, your
grandparents, and one or two of your great-grandparents, but not the
others, nor any of your great-great-grandparents. So we need a way to
say "unknown". Let an ftree be either an
unknown (which has no information) or a
person, which in turn has a string, an integer, another
string, and two ftrees.
Define this data type in Racket.
Write a count-people function that takes in an
ftree and returns how many people are in it.
Write an any-blue-eyed? function that takes in an
ftree and tells whether there is at least one blue-eyed
person in it.
Write a max-depth function that takes in an
ftree and returns its maximum depth. A
person with unknown parents has depth 1; a person with at
least one known parent but unknown grandparents has depth 2; etc.
Write a list-names function that takes in an
ftree and returns a list of all the names in the tree
(don't worry about removing duplicates). Question: in
what order should they appear? A "prefix" ordering would list the
person, then all the names on the mother's side, then all the names on
the father's side. A "postfix" ordering would list the names on the
mother's side, the names on the father's side, and then the person
him/her-self. An "infix" ordering would list the names on the mother's
side, the person him/her-self, and then the names on the father's side.
More difficult is a "breadth-first" ordering, which lists the person
him/her-self, then both parents, then all the grandparents, then all the
great-grandparents, etc.