Lab 12: Generative recursion 2
Remember to follow (and when necessary, adapt) the design recipe for each function. When you write a generative recursive function, you must provide a termination argument. A termination argument must say why the function always eventually stops, not just when it stops.
1 Binary search
Searching is a very common task: we might want to know how many times a given word occurs in a book, or find someone’s phone number in a contact list or phonebook. In Problem set 7: Lists, you implemented searching through a list of frequencies. In Problem set 10: Prefix trees, you implemented searching through a tree of letters. A list and a tree represent two different ways to decompose a search problem. Searching through a list can be slower than searching through a tree, because in a list, the target can be buried much farther from the root.
Binary search is a general and efficient search algorithm. It requires the data to be sorted, like the headwords in a dictionary. To look for a word in a dictionary using binary search, first we flip to the middle of the dictionary, and compare the word in the middle to the word we want. If they happen to be the same, then we’re lucky and done. If they’re different, then depending on their relative order, we can always throw away half of the dictionary. For instance, if we’re looking for “bro” and the middle of the dictionary is “law”, then we can throw away the second half of the dictionary, and continue with the middle of the first half.
If the list has an odd number of elements (say 9), then split it into two equally long halves (4 each), and leave the middle element.
If the list has an even number of elements (say 4), then split it into two equally long halves (2 each), and remove the first element from the right half to become the middle element.
Stop only when the list is empty. Any non-empty box, such as or even just , must be decomposed further.
; A SearchTree is one of: ; - (make-not-found) ; - (make-try SearchTree String SearchTree) (define-struct not-found []) (define-struct try [left middle right])
Exercise 3. Design a function search-tree-contains? that determines whether the given SearchTree contains the given string. For example, neighbors contains "Monroe" but not "Middlesex".
Instead of generative recursion, stick with structural recursion and follow the template for processing a SearchTree. Do not search through the entire tree; that’s way slower. Instead, assume that the tree is sorted. So, every time you come to a try, you can compare its middle against the given string (using string=? and string<?) to decide whether to go left, stop, or go right. The video above only makes 3 comparisons! In other words, never make both of the two recursive calls offered by the template.
The goal of the rest of this section is to generate a SearchTree from a sorted list of county names. The problem decomposition can use some helper functions.
; take : {X} NaturalNumber [ListOf X] -> [ListOf X] ; take the first that-many elements of the list (check-expect (take 2 (list "almond" "pecan" "walnut" "pistachio")) (list "almond" "pecan")) (define (take n l) (cond [(or (= n 0) (empty? l)) empty] [else (cons (first l) (take (- n 1) (rest l)))]))
; drop : {X} NaturalNumber [ListOf X] -> [ListOf X] ; drop the first that-many elements of the list (check-expect (drop 2 (list "almond" "pecan" "walnut" "pistachio")) (list "walnut" "pistachio")) (define (drop n l) (cond [(or (= n 0) (empty? l)) l] [else (drop (- n 1) (rest l))]))
Exercise 6. Design a function right-half that takes a non-empty list as input and returns its second half without its middle element. If the input list has 9 elements, then the output list should be its last 4 elements. If the input list has 4 elements, then the output list should contain just its last element.
Exercise 7. Design a function generate-search-tree that decomposes a given [ListOf String] into a SearchTree. Follow the decomposition strategy in Exercise 1.
Hint: Use generative recursion. Again, remember to make your function terminate, and explain how by writing a termination argument. Use left-half, middle-element, and right-half.
Is Monroe an Indiana county name?
Is Middlesex an Indiana county name?
Challenge. There’s a bug! Decatur is an Indiana county name, and it is in the text file, but search-tree-contains? fails to find it. What’s causing this bug? How can you fix it without reordering the names?
2 Generative terrain
; A CurveTree is one of: ; - (make-segment Posn Posn) ; - (make-connect CurveTree CurveTree) (define-struct segment [p1 p2]) (define-struct connect [c1 c2])
(require 2htdp/image) ; draw-curve-tree : CurveTree Image -> Image ; Draw the given CurveTree on the given image (define (draw-curve-tree c i) (cond [(segment? c) (scene+line i (posn-x (segment-p1 c)) (posn-y (segment-p1 c)) (posn-x (segment-p2 c)) (posn-y (segment-p2 c)) "blue")] [(connect? c) (draw-curve-tree (connect-c1 c) (draw-curve-tree (connect-c2 c) i))]))
(check-expect (midpoint (make-posn 50 100) (make-posn 350 500)) (make-posn 200 300))
(check-expect (almost-midpoint (make-posn 50 100) (make-posn 350 500) -1 2) (make-posn 199 302))
; drift : Number -> Number ; pick a random number between (- amount) and amount (check-random (drift 5) (- (/ (random 10001) 1000) 5)) (define (drift amount) (* amount (- (/ (random 10001) 5000) 1)))
Exercise 13. Design a function between that takes two Posns as input and returns a Posn that is almost their midpoint, but randomly moved a little bit. The picture below illustrates the difference between the functions midpoint and between.
(check-random (between (make-posn 50 100) (make-posn 350 500)) (make-posn (+ 200 (drift 100)) (+ 300 (drift 100)))) (check-random (between (make-posn 50 80) (make-posn 60 80)) (make-posn (+ 55 (drift 2)) (+ 80 (drift 2)))) ; dist : Posn Posn -> Number ; compute the distance between the given Posns (check-expect (dist (make-posn 50 100) (make-posn 350 500)) 500) (check-expect (dist (make-posn 50 80) (make-posn 60 80)) 10) (define (dist p q) (sqrt (+ (sqr (- (posn-x p) (posn-x q))) (sqr (- (posn-y p) (posn-y q))))))
; generate-terrain : Posn Posn -> CurveTree ; generate a random terrain connecting the two given points ; *Termination*: ??? (define (generate-terrain p q) (cond [??? (make-segment ??? ???)] [else (local [; r : Posn (define r (between p q))] (make-connect (generate-terrain ??? ???) (generate-terrain ??? ???)))]))