Comp 210 Exam #1 Solutions 1998 Fall

1. (15 pts) In the kingdom of Tuhundredtenia, citizens whose income is less than $210 are taxed 2% of their income. Those is income is more than that are taxed 2% of that first $210, and 10% of the rest of their income. Consider the a function tax: number → number which given an income, computes the tax due. (A.) Show three example input/outputs for tax, and (B.) write the function. Naturally, changing any of the above the constants should require changing only one number in your solution.

(tax   0) = 0
(tax 100) = 2
(tax 210) = 4.2
(tax 310) = 4.2 + 10 = 14.2

(define THRESHOLD 210)     ; Place where income rates change;
(define POOR_RATE 0.02)
(define RICH_RATE 0.10)
;; tax: natNum, natNum --> number
;;
(define tax
  (lambda (income)
    (if (< income THRESHOLD)
        (* income POOR_RATE)
        (+ (* POOR_RATE THRESHOLD)
           (* RICH_RATE (- income THRESHOLD)))))

2. (20 pts) List Templates

(a) Write the data definition, three examples, and the template for List-of-Number.

A List-of-Number is
  - empty
  - (cons <number> <List-of-Number>)
; Example data:
empty
(cons 3 empty)
(cons 8 (cons 3 (cons 2 empty)))
;; lon-fun: List-of-Number --> ?? [template]
;;
(define lon-fun
  (lambda (nums)
    (cond [(empty? nums) ...]
          [(cons?  nums) ...(first nums)...(lon-fun (rest nums))...])))

(b) Consider the function insert: number, List-of-Number → List-of-Number which takes in a number and an ordered (non-decreasing) list of numbers, and returns a list with the number inserted into the right place in the list. For

example, (insert 8 (list 2 4 6 10)) = (list 2 4 6 8 10) (A.) Give three

other examples, and (B.) write the function.

;; insert: Number, List-of-Number --> List-of-Number
;;
(define insert
  (lambda (newNum nums)
    (cond [(empty? nums) (list newNum)]
          [(cons?  nums) (if (<= newNum (first nums))
                            (cons newNum nums)
                            (cons (first nums) (insert newNum (rest nums))])))

(c) Consider the function insert-sort: List-of-Number → List-of-Number, which takes its unordered input, and returns the same elements in a sorted (non-decreasing)

list. For example, (insert-sort (list 8 6 2 4 10)) = (list 2 4 6 8 10)

(A.) Give two other examples, and (B.) write the function. (Be sure to follow the template!)

;; insert-sort: List-of-Number --> List-of-Number
;;
(define insert-sort
  (lambda (nums)
    (cond [(empty? nums) empty]
          [(cons?  nums) (insert (first nums) (insert-sort (rest nums)))])))

3. (25 pts) An Employee is either a secretary (who has a name and salary), or a manager (who has a salary, and a list of employees who they directly supervise).

(a) Write data definitions for List-of-Employee, and for Employee. If these data definitions use any make-someStructs, include appropriate define-structs.

A List-of-Employee is
  - empty
  - (cons <Employee> <List-of-Employee>)
An Employee is
  - (make-secretary <symbol> <number>)
  - (make-manager   <number> <List-of-Employee>)
(define-struct secretary (name salary))
(define-struct manager   (salary underlings))

(b) Give four different examples of Employees.

(define sec1  (make-secretary 'georges 500))
(define sec2  (make-secretary 'claire  500))
(define sec3  (make-secretary 'bruno   700))
(define boss0 (make-manager 1000 empty))
(define boss1 (make-manager 2000 (list sec1 sec2)))
(define ceo   (make-manager 15000 (list boss0 bruno boss1)))

(c) Write a template for Employee, and one for List-of-Employee.

;; loe-fun: List-of-Employees --> ?? [template]
;;
(define loe-fun
  (lambda (employees)
     (cond [(empty? employees) ...]
           [(cons?  employees) ...(employee-fun (first employees))
                              ...(loe-fun (rest employees))])))
;; employee-fun: Employee  --> ?? [template]
;;
(define employee-fun
  (lambda (e)
     (cond [(manager? e)
            ...(manager-salary e)...(loe-fun manager-underlings e)]
           [(secretary? e)
            ...(secretary-name e)...(secretary-salary e)...])))

(d) Consider the function cost-to-company: employee → number, which calculates the salary of that employee and any employees anywhere under their supervision (even indirectly). Next to the sample employees you wrote above, (A.) write in what cost-to-company returns on each of them. (B.) Write the function.

(cost-to-company sec1)  =  500
(cost-to-company sec2)  =  500
(cost-to-company sec3)  =  700
(cost-to-company boss0) = 1000
(cost-to-company boss1) = 3000
(cost-to-company ceo)   =19700
;; cost-of-loe: List-of-Employees --> number
;; Given a list of employees, calculate their total cost to the company.
(define cost-of-loe
  (lambda (employees)
     (cond [(empty? employees) 0]
           [(cons?  employees) (+ (cost-to-company (first employees))
                                 (cost-of-loe (rest employees))])))
;; cost-to-company: Employee  --> num
;;
(define cost-to-company
  (lambda (e)
     (cond [(manager? e)
            (+ (manager-salary e) (cost-of-loe manager-underlings e)]
           [(secretary? e)  (secretary-salary e)])))

4. (20 pts) Recall that a NatNum is either

• zero, or

• (add1 NatNum).

(a) Write the template for a function which handles two NatNums.^{1}

;; twoNatNum-fun: NatNum, NatNum --> ?? [template]
;;
(define twoNatNum-fun
  (lambda (m n)
     (cond [(and (zero? m)     (zero? n)    )    ...]
           [(and (zero? m)     (positive? n)) ...(sub1 n)...]
           [(and (positive? m) (zero? n)    ) ...(sub1 m)...]
           [(and (positive? m) (positive? n))
            ...(twoNatNum-fun (sub1 m) (sub1 n))...])))

1If your template is written such that the order in which you list the cases is essential to covering all cases, make a comment to this effect.

This could be condensed as follows; note that it requires closer inspection to make sure it covers all cases.

;; twoNatNum-fun: NatNum, NatNum --> ?? [template]
;;  Abbreviated form: the order of the cases is essential for correctness.
;;
(define twoNatNum-fun
  (lambda (m n)
     (cond [(and (zero? m) (zero? n))                  ...]
           [(zero? m)                       ...(sub1 n)...]
           [(zero? n)                       ...(sub1 m)...]
           [else   ...(twoNatNum-fun (sub1 m) (sub1 n))...])))

(b) An egalitarian computer virus, wanting to get rid of all inequality,^{2} has destroyed all computer implementations of the functions <, ≤, ≥, >, −, abs. In fact, the only surviving numerical functions are add1, sub1, zero?, positive?. Save the day by writing greater?: NatNum,NatNum → boolean, which returns whether or not its first argument is bigger than its second.

;; greater?: NatNum, NatNum --> boolean
;; Return (> m n).
;;
(define greater?
  (lambda (m n)
     (cond [(and (zero? m)     (zero? n)    ) #f]
           [(and (zero? m)     (positive? n)) #f]
           [(and (positive? m) (zero? n)    ) #t]
           [(and (positive? m) (positive? n))
            (greater? (sub1 m) (sub1 n))])))

5. (20 pts) The following code is the straightforward way of calculating the sum of a list of numbers with and without an accumulator.

;; sum: list-of-number --> number
;;
(define sum
(lambda (data)
(cond [(empty? data) 0]
      [(cons?  data) (+ (first data) (sum (rest data)))])))

;; sum-accum-helper: list-of-number, number --> number
;; Return the sum of sum-so-far and the numbers in data

2Presumably somebody who felt that Tuhundredtenia’s tax code didn’t fairly account for cost-of-living.

;;
(define sum-accum-helper
  (lambda (sum-so-far data)
    (cond [(empty? data) sum-so-far]
          [(cons?  data) (sum-accum-helper (+ sum-so-far (first data))
                                          (rest data))])))
;; sum-accum: list-of-number --> number
;; Return the sum of the numbers in nums-to-add.
;;
(define sum-accum
  (lambda (nums-to-add)
    (sum-accum-helper 0 nums-to-add)))

Hand evaluate the following expressions, showing the first two steps of the evaluation in complete detail, and then showing (only) the intermediate expressions just before calling one of the above-defined functions. Be careful not to drop/add parentheses. (Of course, if you want to claim that two expressions have equal values, use an equalsign between them.) To save a bit of writing, you may write sum-ah as shorthand for

sum-accum-helper.
  • (sum (list 7 2.718 3.14))
      (sum (list 7 2.718 3.14))
    = ((lambda (data)
         (cond [(empty? data) 0]
               [(cons? data) (+ (first data)
                                (sum (rest data)))])))
       (list 7 2.718 3.14))
    = (cond [(empty? (list 7 2.718 3.14)) 0]
            [(cons? (list 7 2.718 3.14)) (+ (first (list 7 2.718 3.14))
                                           (sum (rest (list 7 2.718 3.14))))])
      [Or, you could've eval'd primitives first,empty?,\&c. to go directly to]
    = (cond [#f 0]
            [#t (+ 7 (sum (list 2.718 3.14)))])
    = (+ 7 (sum (list 2.718 3.14)))
    = (+ 7 (+ 2.718 (sum (list 3.14))))
    = (+ 7 (+ 2.718 (+ 3.14 (sum empty))))
    = (+ 7 (+ 2.718 (+ 3.14 0)))     [optional]
    = (+ 7 (+ 2.718 3.14))           [optional]
    = (+ 7 5.858)                    [optional]
    = 12.858
  • (sum-accum (list 7 2.718 3.14))

  (sum-accum (list 7 2.718 3.14))
= ((lambda (nums-to-add) (sum-accum-helper 0 nums-to-add))
   (list 7 2.718 3.14))
= (sum-accum-helper 0 (list 7 2.718 3.14))
= (sum-accum-helper 7 (list 2.718 3.14))
= (sum-accum-helper 9.718 (list 3.14))
= (sum-accum-helper 12.858 empty)
= 12.858

Yes or no: Do sum and sum-accum always return the same answer, for all possible inputs?

No. (As seen in lab, floating-point representation entails innaccuracies, and adding the same floating-point numbers in a different order may sometimes yield a different result.