...
| 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))))]))
|
Updated Sample Program
A function named sort is included in the core library for most (all?) of the Racket dialects supported by DrRacket. The following revision (with no changes to the code other than the name of the sort function) should run in all of the HTDP student languages except Beginner which excludes abbreviated list notation using '.
| Code Block |
|---|
;; COMP 311 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 (some written as binding of variable names to values)
;; empty
;; (cons 10 (cons -1 (cons 5 empty))) = '(10 -1 5)
(define l0 (cons 0 empty)) ;; '(0)
(define l123 (cons 1 (cons 2 (cons 3 empty)))) ;; '(1 2 3)
(define l321 (list 3 2 1)) ;; '(3 2 1)
#| Template for the data type list-of-numbers (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_ (the name sort is already defined in the library)
;; 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 (written as executable tests)
;; Named values which make the executable tests more concise
;; Executable tests (most using named values define as list-of-numbers examples)
(check-expect (_sort_ empty) empty)
(check-expect (_sort_ l0) l0)
(check-expect (_sort_ l123) l123)
(check-expect (_sort_ l321) l123)
(check-expect (_sort_ '(10 -1 10 -20 5)) '(-20 -1 5 10 10))
;; Tests already set up as executable examples
#| Template Instantiation for _sort_ function:
(define (_sort_ a-lon)
(cond
[(empty? a-lon) ...]
[(cons? a-lon) ... (first a-lon) ...
... (_sort_ (rest a-lon)) ... ]))
|#
;; Code (using not yet defined auxiliary function insert)
(define (_sort_ a-lon)
(cond
[(empty? a-lon) empty]
[(cons? a-lon) (insert (first a-lon) (_sort_ (rest a-lon)))]))
;; 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:
(check-expect (insert 17 empty) '(17))
(check-expect (insert 17 '(17)) '(17 17))
(check-expect (insert 4 l123) '(1 2 3 4))
(check-expect (insert 0 l123) '(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))))]))
;; Tests already set up as executable examples
|
Termination Argument: (Only programs using generative forms of recursion given in Chapter 23 and beyond)
...