...
| 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 ...