University of British Columbia CPSC 110 LAB 8

(@problem 1)

;; The first four problems use the following data definition,
;; which represents a path through a binary search tree.

(@htdd Path)
;; Path is one of:
;; - empty
;; - (cons "L" Path)
;; - (cons "R" Path)
;; interp.
;; A sequence of left and right 'turns' down through a binary tree
;; (list "L" "R" "R") means take the left child of the root, then
;; the right child of that node, and the right child again.
;; empty means you have arrived at the destination.




m
er as
(define P1 empty)
(define P2 (list "L" "R"))




co
eH w
(define P3 empty)
(define P4 (cons "L" (cons "R" empty)))




o.
rs e
(define P5 (cons "L" (cons "R" (cons "R" empty))))
ou urc
(@dd-template-rules one-of atomic-distinct self-ref self-ref)
(define (fn-for-path p)
o

(cond [(empty? p) (...)]
aC s

[(string=? (first p) "L") (... (fn-for-path (rest p)))]
vi y re


[(string=? (first p) "R") (... (fn-for-path (rest p)))]))
ed d




;; Design an abstract function (including signature, purpose, and tests)
ar stu




;; called num-lr to simplify the lefts-minus-rights and rights-minus-lefts
;; functions defined below.
;;
is




;; Then re-define the original lefts-minus-rights and rights-minus-lefts
;; functions to use your abstract function. Remember, the signature and tests
Th




;; should not change from the original functions. For simplicity, assume
;; that all numbers throughout this problem have type Integer.
sh




(@htdf lefts-minus-rights)
(@signature Path -> Integer)
;; produce the difference between left turns and right turns

(check-expect (lefts-minus-rights empty) 0)


This study source was downloaded by 100000805705997 from CourseHero.com on 10-14-2021 21:14:32 GMT -05:00


https://www.coursehero.com/file/82100404/LAB8docx/

, (check-expect (lefts-minus-rights (list "R" "L" "R")) -1)
(check-expect (lefts-minus-rights (list "L" "R" "L")) 1)

(@template use-abstract-fn)
(define (lefts-minus-rights p)
(num-lr add1 sub1 p))

(@htdf rights-minus-lefts)
(@signature Path -> Integer)
;; produce the difference between right turns and left turns

(check-expect (rights-minus-lefts empty) 0)
(check-expect (rights-minus-lefts (list "R" "L" "R")) 1)
(check-expect (rights-minus-lefts (list "L" "R" "L")) -1)




m
er as
(@template use-abstract-fn)
(define (rights-minus-lefts p)




co
eH w
(num-lr sub1 add1 p))




o.
rs e
;; Use the space below to design the abstract function for Problem 1:
ou urc
(@htdf num-lr)
(@signature (Integer -> Integer) (Integer -> Integer) Path -> Integer)
o

;; produce the difference between left and right turns
aC s
vi y re


(check-expect (num-lr add1 add1 empty) 0)
(check-expect (num-lr add1 add1 empty) 0)
(check-expect (num-lr add1 sub1 (list "L" "R" "L")) 1)
(check-expect (num-lr sub1 add1 (list "R" "L" "R")) 1)
ed d




(check-expect (num-lr add1 sub1 (list "R" "L" "R")) -1)
ar stu




(check-expect (num-lr sub1 add1 (list "L" "R" "L")) -1)

(@template Path)
is




(define (num-lr f1 f2 p)
Th




(cond [(empty? p) 0]
[(string=? (first p) "L") (f1 (num-lr f1 f2 (rest p)))]
[(string=? (first p) "R") (f2 (num-lr f1 f2 (rest p)))]))
sh




(@problem 2)
;;
;; Use your abstract function from the previous problem to design a function
;; called path-length that determines the length of a given path.


This study source was downloaded by 100000805705997 from CourseHero.com on 10-14-2021 21:14:32 GMT -05:00


https://www.coursehero.com/file/82100404/LAB8docx/