Homework 2

Assigned 22 Sept, due 4 Oct

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`person`

s 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`candidate`

s 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.)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:- An
`automobile`

has a fuel capacity (a number, in gallons) and a fuel efficiency (a number, in miles per gallon).

(I was going to call this "car", but that already means something in Scheme.) - A
`solar-car`

has a top speed (a number, in miles per hour). - A
`bicycle`

has a number of gears (an integer).

- An
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:- A
`spring`

has a numeric`volume`

, how much water the spring produces (in gallons per hour). - A
`section`

has a numeric`length`

(in miles), and another`river`

at the far end. - A
`branch`

has two`river`

s,`left`

and`right`

.

- A
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.**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.

**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.

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 `ftree`

s.

Last modified: Stephen Bloch / bloch@adelphi.edu