How to do your Racket expository and programming problems

Expository problems

    1. Beginning each line in the answer to an expository question with the comment escape character ; (semicolon) ; or
    2. Enclosing the entire expository answer in a Racket comment box created using Racket block comment brackets #| and |# (sometimes called bookends). 

Hand evaluation problems

Warning: supporting functions as values introduces an extra wrinkle in the reduction process which we will discuss in Lecture 7 and beyond.   The wrinkle is conceptually simple but notationally tedious.

Programming problems

Requirements

You must include a data definition and corresponding template for each form of data processed used in your homework submissions unless instructed otherwise. You only need to include a data definition and corresponding template once for an assignment, not once for every problem that uses that data definition.

Data Definitions and Templates:

You need to devise (and document) your data design before you start writing functions that process this data. Data definitions should be documented as follows:

Basic form of a function definition

Sample Solution to a Programming Problem

The following text is a good solution to the problem of sorting a list of numbers into ascending order; it pulls together all of the specific pieces of design documentation, code documentation, and testing mentioned above. It would be better if it included a few more appropriately chosen tests.

;; 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
   (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))

Note: the Examples and Tests for each function above can be collapsed into a single entry by cutting out each Tests block and pasting it over the corresponding Examples block. Forward references in check-expect invocations work because the execution of check-expect code is deferred to the end of the contents of the definitions pane. For example, the Auxiliary function part can be rewritten as follows:

;; 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
   (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 the quote character ' , which appears in tests.


;; 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
   (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)

If the template does not guarantee that a function terminates, you are required to explain why that function will terminate for all possible inputs.  The standard structural recursion templates guarantee termination.  All instantiations of basic data definition templates are guaranteed to terminate.