...
Code Block |
---|
;; Auxiliary function ;; Contract and purpose ;; insert: number list-of-numbers -> list-of-numbers ;; Purpose: (insert n alon), where alon is in increasing order, returns a list containing n and the elts of alon in ascending order ;; Examples and Tests: (check-expect (insert 17 empty) '(17)) (check-expect (insert 17 '(17)) '(17 17)) (check-expect (insert 4 '(1 2 3)) '(1 2 3 4)) (check-expect (insert 0 '(1 2 3)) '(0 1 2 3)) (check-expect (insert 2 '(1 1 3 4)) '(1 1 2 3 4)) #| Template instantiation (define (insert n a-lon) (cond [(empty? a-lon) ...] [(cons? a-lon) ... (first a-lon) ... ... (insert n (rest a-lon)) ... ])) |# ;; Code (define (insert n a-lon) (cond [(empty? a-lon) (cons n empty)] [(cons? a-lon) (if (<= n (first a-lon)) (cons n a-lon) (cons (first a-lon) (insert n (rest a-lon))))])) |
...
Termination Argument: (
...
Only programs using generative forms of recursion given in Chapter 23
...
and beyond)
If the template does not guarantee that a function terminates, you are required to explain why that function will terminate for all possible inputs. The standard structural recursion templates guarantee termination.
Example 7. Termination argument for
quick-sort
:Code Block ;; quick-sort list-of-number -> list-of-number ;; Purpose: (quick-sort lon) sorts lon into ascending order ;; ;; Examples: ;;(check-expect (quick-sort empty) => empty) ;;(check-expect (quick-sort '(1)) => '(1)) ;;(check-expect (quick-sort '(1 4 3 5)) => '(1 3 4 5)) ;; (quickcheck-sortexpect '(1 4 3 4 2 5)) => '(1 2 3 4 4 5)) ;; ;; Termination: ;; On each call, quick-sort partitions the list alon into three sublists using ;; smaller-than, larger-than, and equal-to. The lists produced by smaller-than ;; and larger-than are sorted using recursive applications of quick-sort. Since ;; the lists produced by smaller-than and larger-than are strictly shorter than ;; alon (the given list), quick-sort terminates. (define (quick-sort alon) (cond [(empty? alon) empty] [else (append (quick-sort (smaller-items alon (first alon))) (equal-to alon (first alon)) (quick-sort (larger-items alon (first alon))))])) ;; Remainder of this example (including the "Testing quick-sort:"definitions of smaller-items and larger-items) is elided ...