;; A List of Numbers (LON) is one of ;; -- empty ;; -- (cons Number LON) ;; constructor: ;; construct a new list from f and r ;; Number LON --> LON ;; (cons f r) ;; predicate -- is the given datum a cons? (of any kind of data) ;; Any --> Boolean ;; (cons? a-list) ;; selector for the first element of the list ;; LON --> Number ;; (first a-list) ;; selector for the remainder of the list ;; LON --> LON ;; (rest a-list) ;; produce a sorted list of numbers from this list of numbers ;; LON --> [LON (sorted)] (define (sort a-list) (cond [(empty? a-list) empty] [else (insert (sort (rest a-list)) (first a-list))])) ;; Template ;; ... (empty? a-list) ... -- Boolean ;; ... (cons? a-list) ... -- Boolean ;; ... (first a-list) ... -- Number ;; ... (rest a-list) ... -- LON ;; ... (sort (rest a-list)) ... -- [LON (sorted)] ;; ... (insert (sort (rest a-list)) Number) ... -- [LON (sorted)] ;; produce a sorted list by inserting a number into a sorted list ;; [LON (sorted)] Number --> [LON (sorted)] (define (insert s-list num) (cond [(empty? s-list) (cons num s-list)] [else (cond [(< num (first s-list)) (cons num s-list)] [else (cons (first s-list) (insert (rest s-list) num))])])) ;; Template ;; ... (empty? a-list) ... -- Boolean ;; ... (cons? a-list) ... -- Boolean ;; ... (first a-list) ... -- Number ;; ... (rest a-list) ... -- [LON (sorted)] ;; ... (insert (rest a-list)) Number) ... -- [LON (sorted)] ;; examples (equal? empty (sort empty)) (equal? (list 2 4 6 8) (sort (list 4 8 2 6))) (equal? (list 2 4 6 8) (insert (list 4 6 8) 2)) (equal? (list 2 4 6 8) (insert (list 2 6 8) 4)) (equal? (list 2 4 6 8) (insert (list 2 4 6) 8))