CPSC110 problem set 10 solution

(@problem 1)
;;
;; Complete the design of the following func:on.
;;
;; Hint: some:mes for func:ons with accumulators it is useful for
;; the trampoline to deal with the special case of the empty
;; list or empty tree using an if expression.
;;

(@htdf max-num-repeats)
(@signature (listof String) -> Natural)
;; produce maximum number of :mes same string appears consecu:vely in los0
(check-expect (max-num-repeats empty) 0)
(check-expect (max-num-repeats (list "cat")) 1)
(check-expect (max-num-repeats (list "cat" "bird" "dog")) 1)
(check-expect (max-num-repeats (list "cat" "cat" "bird" "dog")) 2)
(check-expect (max-num-repeats (list "cat" "cat" "bird" "dog" "dog" "dog"))
3)
(check-expect (max-num-repeats (list "cat" "cat" "cat"
"bird"
"boy" "boy" "boy"
"toy" "toy" "toy" "toy" "toy"
"trick"
"zebra" "zebra" "zebra" "zebra"))
5)
(check-expect (max-num-repeats (list "dog" "cat" "bird"
"dog" "dog" "dog"
"moose" "dog"))
3)

(@template-origin (listof String) accumulator)

;(define (max-num-repeats los) 0)

(define (max-num-repeats los0)
(local [(define (max-num-repeats los rsf prev)
(cond [(empty? los) (if (< rsf prev) prev rsf)]
[else
(if (member (first los) (rest los))
(max-num-repeats (rest los) (add1 rsf) prev)
(if (< prev rsf)
(max-num-repeats (rest los) 1 rsf)
(max-num-repeats (rest los) 1 prev)))]))]
(max-num-repeats los0

, (if (empty? los0)
0
1)
0)))


(@problem 2)
;;
;; Complete the design of the following func:on.
;;
;; Your solu:on MUST BE TAIL RECURSIVE.
;;

(@htdf list-range)
(@signature (listof Integer) -> Natural)
;; produce the difference between the max and min integer in the list
;; CONSTRAINT: loi0 has at least one element
(check-expect (list-range (list 100)) 0)
(check-expect (list-range (list 2 -5 -10 50 80)) 90)
(check-expect (list-range (list 5000 -5 -100 50 0)) 5100)
(check-expect (list-range (list 3 8 1 2 9 4 2 3 -5)) 14)
(check-expect (list-range (list -5000 3 2 2 4 5000 4 2 3)) 10000)
(check-expect (list-range (list 400 500 500 400)) 100)

(@template-origin (listof Integer) accumulator)

;(define (list-range loi) 0)

(define (list-range loi0)
(local [(define (list-range loi acc max min)
(cond [(empty? loi) (- max min)]
[else
(list-range (rest loi) (- max min)
(if (> (first loi) max)
(first loi)
max)
(if (< (first loi) min)
(first loi)
min))]))]
(list-range loi0 0 -inf.0 +inf.0)))

(@problem 3)
;;
;; Complete the design of the following func:on.