...
- The basic form for each function that you write is shown below:
Example 5. Function definition for computing product of list-of-number:
Code Block ;; product-of-lon : list-of-numbers -> number ;; to compute the product of numbers in a list ;; assuming product of empty list is 1 ;; Examples: ;; (product-of-lon empty) => 1 ;; (product-of-lon (cons 2 empty)) => 2 ;; (product-of-lon (cons 3 (cons 2 empty))) => 6 ;; Template instantiation for product-of-lon #| (define (product-of-lon a-lon) (cond [(empty? a-lon) ...] [(cons? a-lon) ... (first a-lon) ... ... (product-of-lon (rest a-lon)) ... ])) |# ;; Code (define (product-of-lon a-lon) (cond [(empty? a-lon) 1] [(cons? a-lon) (* (first a-lon) (product-of-lon (rest a-lon)))])) ;; Test Examples: (check-expect (product-of-lon empty) 1) (check-expect (product-of-lon (cons 2 empty)) 2) (check-expect (product-of-lon (cons 3 (cons 2 empty))) 6) ;; Provide enough examples and tests to show you tested thoroughly
- Remember to follow the design recipe.
- It is important that things are presented in this order, so that is clear that you know the correct order for doing things.
- Be careful with regard to using the
equal?operation in the program code that you write because the worst case running time is the size of the smaller of its two inputs (on inputs that are equal or nearly equal). Of course, theequal?operation and operations that callequal?(like check-expect) are extensively used in test code. - If your examples get too big, then simply
definea name for that big argument somewhere before you use it. You can use this name both in your comments in the example section and in the test cases in the Tests section. - Be sure to test your code thoroughly. Corner cases and edge cases should be tested. When dealing with numerical functions,
0and1are often important test inputs. - When testing lists, make sure you test the following cases:
- empty list:
empty - list with one element: ex:
(cons 3 empty) - list with more than one element: ex:
(cons 1 (cons 3 (cons 3 (cons 7 empty))))
- empty list:
- Local functions cannot be tested individually, so specific tests are not required for them. However, you main function's tests need to be comprehensive enough to test the local functions.
...
| 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:
;; empty
;; (cons 10 (cons -1 (cons 5 empty))) = '(10 -1 5)
;; (cons 1 (cons 2 (cons 3 empty))) = '(1 2 3)
;; (cons 3 (cons 2 (cons 1 empty))) = '(3 2 1)
#| 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
;; Signature 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 for the sort function:
(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 function
;; Signature and Purpose
;; insert: number list-of-numbers -> list-of-numbers
;; Purpose: (insert n alon), where alon is in ascending 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 for insert
(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))
|
...
| Code Block |
|---|
;; Auxiliary function
;; Signature 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 for insert
(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))))]))
|
...
| 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)
;; Signature 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))
;; Note: the preceding ests are already set up as executable examples
#| Template Instantiation for _sort_ function:
(define (_sort_ a-lont)
(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
;; Signature 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 for insert
(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
|
...