Page History

;; 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 '(cons0)) 1= '(cons 2 (cons 3 empty))))0)
;; (sort '(1 2 3)) = '(cons 1 (cons 2 (cons 3 empty)))
;; (sort '(cons 3 (cons 2 (cons 1 empty)))) = '(cons 1 (cons 2 (cons 3 empty)))
;; (sort '(cons 10 (cons -1 (cons 10 (cons-20 5 empty))))) = (cons-20 -1 (cons 5 (cons 10 (cons 10 empty))))

;; 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)) (cons 1 (cons'(0))
(check-expect (sort '(1 2 (cons 3 empty)))) '(cons 1 (cons 2 (cons 3 empty))))
(check-expect (sort '(cons 3 (cons 2 (cons 1 empty)))) '(cons 1 (cons 2 (cons 3 empty))))
(check-expect (sort '(cons 10 (cons -1 (cons 10 (cons-20 5 empty))))) '(cons-20 -1 (cons 5 (cons 10 (cons 10 empty)))))

;; 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) = (cons 17 empty'(17)
;;  (insert 17 '(17)) = '(17 17)
;;  (insert 4 '(cons 1 (cons 2 (cons 3 empty)))) = '(cons 1 (cons 2 (cons 3 (cons 4 empty))))3 4)
;;  (insert 0 '(cons 1 (cons 2 (cons 3 empty)))) = '(cons 0 (cons 1 (cons 2 (cons 3 empty))))
;;  (insert 1.52 '(cons 1 (cons 1 (cons 2 (cons 3 empty4))))) = '(cons 1 (cons 1 (cons 1.5 (cons 2 (cons 3 empty)))))

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) '(cons 17 empty))
(check-expect (insert 4 '(cons 1 (cons 2 (cons 3 empty)))) '(cons 1 (cons 2 (cons 3 (cons 4 empty)))))
(check-expect (insert 0 '(cons 1 (cons 2 (cons 3 empty)))) '(cons 0 (cons 1 (cons 2 (cons 3 empty)))))
(check-expect (insert 1.52 '(cons 1 (cons 1 (cons 2 (cons 3 empty)))4)) '(cons 1 (cons 1 (cons 1.5 (cons 2 (cons 3 empty))))))
(define (down-to n)
    (if (< n 0) empty (cons n (down-to (sub1 n)))4))