...
Code Block |
---|
;; COMP 211 HW #Sample
;; Corky Cartwright <cork@rice.edu>
;; A list-of-numbers is either:
;; empty, or
;; (cons n alon) where n is a number and alon is a list-of-numbers
;;
;; Examples:
;; empty
;; (cons 10 (cons -1 (cons 5 empty)))
;; (cons 1 (cons 2 (cons 3 empty)))
;; (cons 3 (cons 2 (cons 1 empty)))
;; Template: (enclosed in block comment brackets)
(define (lon-f ... a-lon ...)
(cond
[(empty? a-lon) ...]
[(cons? a-lon) ... (first a-lon) ...
... (lon-f ... (rest a-lon) ...) ... ]))
|#
;; Main function: sort
;; Contract and purpose:
;; sort: list-of-numbers -> list-of-numbers
;; Purpose: (sort alon) returns the a list with same elements (including duplicates) as alon but in ascending order.
;; Examples:
;; (sort empty) = empty
;; (sort '(0)) = '(0)
;; (sort '(1 2 3)) = '(1 2 3)
;; (sort '(3 2 1)) = '(1 2 3)
;; (sort '(10 -1 10 -20 5)) = (-20 -1 5 10 10)
;; Template Instantiation:
#|
(define (sort a-lon)
(cond
[(empty? a-lon) ...]
[(cons? a-lon) ... (first a-lon) ...
... (sort (rest a-lon)) ... ]))
|#
;; Code:
(define (sort a-lon)
(cond
[(empty? a-lon) empty]
[(cons? a-lon) (insert (first a-lon) (sort (rest a-lon)))]))
;; Tests
(check-expect (sort empty) empty)
(check-expect (sort '(0)) '(0))
(check-expect (sort '(1 2 3)) '(1 2 3))
(check-expect (sort '(3 2 1)) '(1 2 3))
(check-expect (sort '(10 -1 10 -20 5)) '(-20 -1 5 10 10))
;; Auxiliary functions
;; 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:
;; (insert 17 empty) = '(17)
;; (insert 17 '(17)) = '(17 17)
;; (insert 4 '(1 2 3)) = '(1 2 3 4)
;; (insert 0 '(1 2 3)) = '(0 1 2 3)
;; (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))))]))
;; 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))
|
...