CSC 160
Homework 8

Assigned 25 Apr, due 4 May

1. write an English-language data definition,
2. write a define-struct,
3. write down the contracts of all the functions that "come for free" with the define-struct,
4. write a template for functions that take a parameter of this type. Note that once you've written this for a given struct, you can copy-and-paste it as a starting point for every function that takes in this kind of parameter.

For example, if I were to say

Design a structure to represent an employee, with a name, salary, and employee ID number,

Problems on posns

• Exercise 16.3.6: the posn=? function
• Exercise 16.4.2: the swap-x-y function
• Exercise 16.4.4: the add-posns function

Problems on other structs

• Employees

  This is sort of a "warm-up" exercise; we'll do most of it in class.

  1. Design a structure to represent an employee, with a name, salary, and employee ID number. (This is done for you in the file employee.scm; please download this file and use it as a starting point for the following two problems.)

  2. Using the template, develop a function named earns-over-100K? which takes an employee and returns a Boolean telling whether the employee earns over $100,000/year.

  3. Using the template, develop a function named give-10%-raise which takes an employee and returns a new employee with the same name and ID number, but earning 10% more.

• Computerized elections

  1. Recall the who-won function from the previous homework. It has a serious disadvantage: since it has the names "Anne", "Bob", and "Charlie" hard-coded in, it'll need to be rewritten every time different candidates run for office. Let's fix that.
     Design a structure to represent a candidate in an election. The structure should contain both the candidate's name and how many votes the candidate received.

  2. Using the template for functions working on candidate structures, develop a function named who-won which takes in three candidate structures and returns the winning candidate structure. For now, you may assume that there are no ties. (Hint: You won't be able to re-use the old who-won function here, because the old function was specific to the names "Anne", "Bob", and "Charlie".)

  3. Develop a function named winner-name which takes in three candidate structures and returns the name of the winner. (This can be done using the template, but there's a much easier way, by re-using previously defined functions.)

  4. Using the template for functions working on candidate structures, develop a function named add-vote which takes in a candidate structure and returns a candidate structure just like it, but with one more vote.

• Extra credit: An animation

  This time we'll animate a rocketship moving around the screen. By the laws of physics, a rocketship keeps moving at its current velocity (i.e. speed and direction) until something happens (e.g. firing the rockets) to change its velocity. Thus to represent a moving rocketship we need several pieces of information: where it is now (in both x and y dimensions), its velocity in the x dimension, and its velocity in the y dimension. (By convention, positive x velocity means moving to the right, and positive y velocity means moving down the screen.)

  1. Design a structure to represent all this information.

  2. Using the template for functions working on rocket structures, develop a function named show-rocket which takes in one of these structures and returns an image with the rocket at the right position. For simplicity, let's just draw the rocket as a circle (or, if you prefer, you can find a small picture of a rocketship on the Web and use that instead).

  3. Using the template for functions working on rocket structures, develop a function named handle-key which takes in a rocket structure and a key, and changes the velocity of the rocket (but not its position) depending on whether the up, down, left, or right arrow was pressed, returning the resulting rocket structure.

  4. Using the template for functions working on rocket structures, develop a function named handle-tick which takes in a rocket structure and returns a new rocket structure with the same velocity as the old one, but with the position changed by the x velocity in the x dimension, and the y velocity in the y dimension.

  5. Put these together into a working animation.

Problems on lists

• Develop a function named any-matches? that takes a string and a list of strings and returns whether that string appears in the list.
  Example:

  (any-matches? "hi" (cons "hey" (cons "ho" empty))) "should be" false
  (any-matches? "hi" (cons "hey" (cons "hi" empty))) "should be" true

• Develop a function count-matches that takes a string and a list of strings and returns the number of times that string occurs in the list.
  Example:

  (count-matches "hi" (cons "hey" (cons "hi" (cons "hello" (cons "hi" (cons "bye" (cons "hi" (cons "adios" empty))))))))
  "should be" 3

• Develop a function cube-each that takes a list of numbers and returns a list the same length, containing the cubes of the respective numbers.
  Example:

  (cube-each (cons 3 (cons 5 (cons -2 empty))))
  "should be" (cons 27 (cons 125 (cons -8 empty)))

• Develop a function remove-all that takes a string and a list of strings and returns the same list with all occurrences of the given string removed.
  Example:

  (remove-all "bat" (cons "doll" (cons "bat" (cons "bat" (cons "nintendo" (cons "bat" (cons "ball" empty)))))))
  "should be" (cons "doll" (cons "nintendo" (cons "ball" empty)))

• Develop a function replace that takes two strings (referred to as old and new) and a list of strings, and returns a list of strings with old replaced throughout by new.
  Example:

  (replace "bat" "ball" (cons "doll" (cons "bat" (cons "bat"
  (cons "nintendo" (cons "bat" (cons "ball" empty)))))))
  "should be" (cons "doll" (cons "ball" (cons "ball" (cons "nintendo"
  (cons "ball" (cons "ball" empty))))))

• Develop a function named add-vote-for which takes in a string (the name of a candidate) and a list of candidate structures, and returns a list of candidate structures in which that candidate has one more vote (and all the others are unchanged). You may assume that no name appears more than once in the list of candidate structures.
  Note: it's possible that the name doesn't appear in the list at all (e.g. it's a write-in vote, or something like that); if so, the resulting list should have 1 vote for that candidate.

• Develop a function named tally-votes which takes in a list of strings (Voter 1's favorite candidate, Voter 2's favorite candidate, etc.) and produces a list of candidate structures in which each candidate name appears once, with how many votes were cast for that candidate.

What to turn in and how

As usual, turn in a log of how many errors of different kinds you encountered in the assignment, with brief comments describing each one. You may do this using the PSP forms, or simply by keeping track in a text file or on paper and turning it in.

Grading standards

Error log:       /25
(I'm not grading on how many or how few errors you encountered, only on whether you recorded them correctly.)

I sha'n't actually grade all the programming problems; consider the others "practice". For each function I grade, see the table below.

The table below has columns for each step in the design recipe. You won't turn in a separate skeleton and definition, but rather write a skeleton and then add stuff to turn it into a definition. However, if you don't get the definition working, you'll still get partial credit for a correct skeleton.

General skills:

Total:         /???