HtDP Solution Set

Section 10



Problem 1 (Solution):
#|
A Frequency is a Number
 
A List-of-frequency is one of
- empty
- (cons Frequency List-of-frequency)
|#
 
;;filter-freq : Frequency Frequency List-of-frequency -> List-of-frequency
;; - return list of frequences below threshold
(define (filter-freq f-low f-high a-lof)
(cond
[(empty? a-lof) empty]
[(cons? a-lof)
(cond
[(and (>= (first a-lof) f-low) (<= (first a-lof) f-high))
(cons (first a-lof) (filter-freq f-low f-high (rest a-lof)))]
[else
(filter-freq f-low f-high (rest a-lof))])]))
 
#| Tests |#
 
(filter-freq 100 300 empty)
"should be" empty
(filter-freq 100 300
(cons 50 (cons 100 (cons 200 (cons 299 (cons 300 (cons 350 empty)))))))
"should be" (cons 100 (cons 200 (cons 299 (cons 300 empty))))
 
 


Problem 2 (Solution):
#|
A List-of-number-and-symbol is one of
- empty
- (cons Number List-of-number-and-symbol)
- (cons Symbol List-of-number-and-symbol)
|#
 
(define (symbol-count a-lons)
(cond
[(empty? a-lons) 0]
[(number? (first a-lons))
(symbol-count (rest a-lons))]
[(symbol? (first a-lons))
(+ 1 (symbol-count (rest a-lons)))]))
 
(symbol-count empty)
"should be" 0
(symbol-count (cons 1 empty))
"should be" 0
(symbol-count (cons 'a empty))
"should be" 1
(symbol-count (cons 1 (cons 'a (cons 2 (cons 'b (cons 'c empty))))))
"should be" 3
 
 


Problem 3 (Solution):
#|
A Bid is a structure
(make-bid Number Number Number)
|#
 
(define-struct bid (bidder item amount))
#|
A Non-empty-list-of-bid is one of
- (cons Bid empty)
- (cons Bid Non-empty-list-of-bid)
 
|#
 
;;highest-bid : Number Non-empty-list-of-bid -> Bid
(define (highest-bid an-item a-nelob)
(cond
[(empty? (rest a-nelob)) (first a-nelob)]
[(cons? (rest a-nelob))
(cond
[(and (= (bid-item (first a-nelob))
an-item)
(> (bid-amount (first a-nelob))
(bid-amount (highest-bid an-item (rest a-nelob)))))
(first a-nelob)]
[else (highest-bid an-item (rest a-nelob))])]))
 
 
#| Tests |#
(highest-bid 1000 (cons (make-bid 252 1000 12) empty))
"should be" (make-bid 252 1000 12)
(highest-bid 1000 (cons (make-bid 252 1000 12)
(cons (make-bid 253 1001 14)
(cons (make-bid 254 1000 16) empty))))
"should be" (make-bid 254 1000 16)
 


Problem 4 (Solution):
#|
A Substance is a Symbol.
 
A Tank is a structure
(make-tank Substance Number)
|#
 
(define-struct tank (subst liters))
 
;remove : Substance List-of-tank -> List-of-tank
; - produce new list of tanks without any containing given substance
(define (remove s a-lots)
(cond
[(empty? a-lots) empty]
[(cons? a-lots)
(cond
[(symbol=? s (tank-subst (first a-lots)))
(remove s (rest a-lots))]
[else (cons (first a-lots)
(remove s (rest a-lots)))])]))
 
;combine : Substance List-of-tank -> Number
; - combine tanks with same substance into new tank
(define (combine a-substance a-lots)
(cond
[(empty? a-lots) 0]
[(cons? a-lots)
(cond
[(symbol=? (tank-subst (first a-lots)) a-substance)
(+ (tank-liters (first a-lots))
(combine a-substance (rest a-lots)))]
[else (combine a-substance (rest a-lots))])]))
 
;consolidate : List-of-tank -> List-of-tank
; - combine all tanks with same substances into new list of tanks
(define (consolidate a-lots)
(cond
[(empty? a-lots) empty]
[else
(cons
(make-tank (tank-subst (first a-lots))
(combine (tank-subst (first a-lots)) a-lots))
(consolidate (remove (tank-subst (first a-lots)) (rest a-lots))))]))
 
#| Tests |#
(remove 'sugar empty)
"should be" empty
(remove 'sugar (cons (make-tank 'sugar 1000)
(cons (make-tank 'tar 2000)
(cons (make-tank 'sugar 3000)
empty))))
"should be" (cons (make-tank 'tar 2000) empty)
 
(combine 'sugar empty)
"should be" 0
(combine 'sugar
(cons (make-tank 'sugar 2000)
(cons (make-tank 'oil 1000)
(cons (make-tank 'sugar 1000)
empty))))
"should be" 3000
 
(consolidate empty)
"should be" empty
(consolidate (cons (make-tank 'tar 2000) empty))
"should be" (cons (make-tank 'tar 2000) empty)
(consolidate (cons (make-tank 'tar 2000)
(cons (make-tank 'syrup 1000)
(cons (make-tank 'tar 1000) empty))))
"should be" (cons (make-tank 'tar 3000) (cons (make-tank 'syrup 1000) empty))
 


Problem 5 (Solution):
#| A list-of-strings is either 
- empty
- (cons String list-of-strings)
|#
 
;which-toppings : SB-list -> list-of-string
;- compute the list of strings that are associated with true in a-sb-list
(define (which-toppings a-sb-list)
(cond
[(empty? a-sb-list) empty]
[else (cond
[(second (first a-sb-list))
(cons (first (first a-sb-list)) (which-toppings (rest a-sb-list)))]
[else (which-toppings (rest a-sb-list))])]))
 
#| Tests |#
 
(which-toppings empty)
"should be" empty
(which-toppings
(cons (cons "anchovies" (cons false empty))
(cons (cons "cheese" (cons true empty))
empty)))
"should be"
(cons "cheese" empty)



Jamie Raymond
Matthias Felleisen
 

23 september 2002