Homework 9
Due Date: Friday March 28, 9pm
Purpose Practice with functions of multiple complex inputs
Expectations
You should submit three .rkt files, each containing your response to one of the 3 exercises below, via the Handin Server; the three files should be named "HW9-1.rkt", "HW9-2.rkt", and "HW9-3.rkt". We accept NO email submissions. Failure to submit a .rkt file will result in a 0 for that part.
You are only allowed to use the language specified at the top of this page: failure to do so will result in a 0. For this assignment, you must use ISL+Lambda (remember to correctly set the mode in DrRacket). Using the wrong language will invalidate your submission and result in a score of 0, so please be careful.
Your code must conform to the guidelines outlined in the style guide on the course website. Pay particular attention to the list of prohibited functions in the guide. The style guide may be updated as the semester progresses so please remember to read it before submitting each assignment.
Unless otherwise stated, all data and functions you design must be designed according to the data and function design recipes (DR), resp., following all four steps in each case, with the exception of functions that call big-bang, for which you need no check-expects, as justified in class, and local functions, which need example comments in place of check-expects. All functions used inside big-bang must have check-expects, along with the other three steps of the design recipe.
-----------------------------------------------------------------------------
Exercise 1 Multiple lists
A diagonal matrix is a quadratic matrix whose entries are all 0, except those on the diagonal. For example,
is a representation of a 3x3 diagonal unit matrix (whose diagonal entries are all 1). Design a function diag-matrix that takes two numbers n and d as input and returns a diagonal matrix, in the above representation, of dimension nxn, with all diagonal entries equal to d.
Design the function append-no-dups that accepts two lists of elements of the same type, and an equivalence relation (a function that compares two elements of the same type and returns #true if they are equal) and produces a list with all of the elements from both source lists with all duplicates removed. The order of elements in the list should reflect the order in the original lists, with elements from the first list coming before elements of the second list, but which of the duplicates is removed is up to you. Note that there can be duplicates even within one or the other list, and there might even be more than two copies of a single value, in which case you must drop all but one.
Examples:
(append-no-dups (list 1 2 2 3) (list 3 4 5) =) ; -> (list 1 2 3 4 5) (append-no-dups (list "a" "b" "c" "b") (list "d" "b" "e") string=?) ; -> (list "a" "b" "c" "d" "e") (Note that the second example above might have a different possible outcome depending on which of the duplicates you decide to drop.)
Exercise 2 Weaving lists:
Design an abstract function zip that takes two arbitrary lists and "zips" them together. That is, it produces a list of TwoLists. A TwoList is a list of size 2. The first TwoList contains the respective first element of each list, the second TwoList contains the respective second element of each list, and so on. If one of the two lists runs out of elements, ignore the remaining elements of the other list. For instance, given (list 1 3 5 7) and (list 2 4 6), the output should be (list (list 1 2) (list 3 4) (list 5 6)); the 7 is ignored. According to this specification, what happens if one input lists is empty? Include an appropriate test case.
Begin with a proper data design for TwoList. Then design your zip function. "Abstract" means that your signature must be as general as possible.
As we found out in the recent lab, the map function can work for multiple input lists. For example, (map + (list 1 2) (list 3 4) (list 5 6)) would produce (list 9 12). To get a sense of how this works, you are to design the function map-2list, which takes a function and two lists, and applies the function to the first element of both lists, then the second of both lists, ... You are not allowed to use any list abstraction for this problem. The function should produce an error (using the error function) if the lists are not the same size (you can use check-error to check that your function works correctly in these cases).
Exercise 3 Consider the following data definitions:
(define-struct student [name nuid]) ; A Student is a (make-student String Number) ; Interpretation: (make-student name nuid) represents a student. (define EX-STUDENT-1 (make-student "Alice" 1)) (define EX-STUDENT-2 (make-student "Bob" 2)) (define EX-STUDENT-3 (make-student "Carol" 3)) (define (student-template s) (... (student-name s) ... (student-nuid s) ...)) (define-struct grade [nuid course value]) ; A Grade is a (make-grade Number String Number) ; Interpretation: (make-grade nuid course grade) represents the grade that ; a student received in a course. (define (grade-template g) (... (grade-nuid g) ... (grade-course g) ... (grade-value g) ...)) (define EX-GRADE-1 (make-grade 1 "Fundies 1" 95)) (define EX-GRADE-2 (make-grade 1 "Psychoceramics" 65)) (define EX-GRADE-3 (make-grade 2 "Programming Languages" 85)) (define EX-GRADE-4 (make-grade 2 "Fundies 1" 75)) (define EX-GRADE-5 (make-grade 3 "Fundies 1" 68)) (define EX-GRADE-6 (make-grade 3 "Cybernetics" 82)) (define EX-GRADE-7 (make-grade 3 "Phonology" 89)) (define EX-GRADE-8 (make-grade 4 "Fundies 1" 55)) (define-struct student-grades [name grades]) ; A StudentGrades is a (make-student-grades String [List-of Number]). ; Interpretation: (make-student-grades name grades) represents the grades ; that a student has received in all courses. (define (student-grades-template sg) (... (student-grades-name sg) ... ; i.e., template for [List-of Number] (lon-template (student-grades-grades sg)) ...)) (define EX-STUDENT-GRADES-1 (make-student-grades "Alice" (list 95 65))) (define EX-STUDENT-GRADES-2 (make-student-grades "Bob" (list 85 75))) (define EX-STUDENT-GRADES-3 (make-student-grades "Carol" (list 68 82 89))) Design a function students->student-grades that receives a list of Students and list of Grades, and produces a list of StudentGrades, where each StudentGrade in the result is the list of all the grades received by a student in all courses takes by that student.
NOTE: The list produced by students->student-grades should have an item for every student in the input list, even if there are no grades for that student.