Recursive Auxiliary Functions

People need to sort things all the time. Investment advisors sort portfolios by the profit each holding generates. Doctors sort lists of transplant patients. Mail programs sort messages. More generally, sorting lists of values by some criteria is a task that many programs need to perform.

Here we study how to sort a list of numbers not because it is important for many programming tasks, but also because it provides a good case study of the design of auxiliary programs. A sorting function consumes a list and produces one. Indeed, the two lists contain the same numbers, though the output list contains them in a different order. This is the essence of the contract and purpose statement:

 
;; sort : list-of-numbers -> list-of-numbers  
;; to create sorted list of numbers from all the numbers in alon 
(define (sort alon) ...) 

Here is one example per clause in the data definition:

(sort empty)
;; expected value:  
empty 

(sort (cons 1297.04 (cons 20000.00 (cons -505.25 empty))))
;; expected value:  
(cons 20000.00 (cons 1297.04 (cons -505.25 empty))) 

Next we must translate the data definition into a function template. Again, we have dealt with lists of numbers before, so this step is easy:

(define (sort alon)
  (cond 
    [(empty? alon) ...] 
    [else ... (first alon) ... (sort (rest alon)) ...])) 

Using this template, we can finally turn to the interesting part of the program development. We consider each case of the cond-expression separately, starting with the simple case. If sort's input is empty, then the answer is empty, as specified by the example. So let's assume that the input is not empty. That is, let's deal with the second cond-clause. It contains two expressions and, following the design recipe, we must understand what they compute:

1. (first alon) extracts the first number from the input;
2. (sort (rest alon)) produces a sorted version of (rest alon), according to the purpose statement of the function.

Let's look at the second example in this context. When sort consumes (cons 1297.04 (cons 20000.00 (cons -505.25 empty))), then

1. (first alon) evaluates to 1297.04,
2. (rest alon) is (cons 20000.00 (cons -505.25 empty)), and
3. (sort (rest alon)) produces (cons 20000.00 (cons -505.25 empty)).

Inserting a number into a sorted list isn't a simple task. We may have to search through the entire list before we know what the proper place is. Searching through a list, however, can be done only with a function, because lists are of arbitrary size and processing such values requires recursive functions. Thus we must develop an auxiliary function that consumes the first number and a sorted list and create a sorted list from both. Let us call this function insert and let us formulate a wish-list entry:

;; insert : number list-of-numbers -> list-of-numbers
;; to create a list of numbers from n and the numbers on alon  
;; that is sorted in descending order; alon is already sorted 
(define (insert n alon) ...) 

Using insert, it is easy to complete the definition of sort:

(define (sort alon)
  (cond 
    [(empty? alon) empty] 
    [else (insert (first alon) (sort (rest alon)))])) 

Of course, we are not really finished until we have developed insert. We already have a contract, a header, and a purpose statement. Next we need to make up function examples. Since the first input of insert is atomic, let's make up examples based on the data definition for lists. That is, we first consider what insert should produce when given a number and empty. According to insert's purpose statement, the output must be a list, it must contain all numbers from the second input, and it must contain the first argument. This suggests the following:

(insert 5 empty)
;; expected value:  
(cons 5 empty) 

The second example must use a non-empty list, but then, the idea for insert was suggested by just such an example when we studied how sort should deal with non-empty lists. Specifically, we said that sort had to insert 1297.04 into (cons 20000.00 (cons -505.25 empty)) at its proper place:

(insert 1297.04 (cons 20000.00 (cons -505.25 empty)))
;; expected value:  
(cons 20000.00 (cons 1297.04 (cons -505.25 empty))) 

In contrast to sort, the function insert consumes two inputs. But we know that the first one is a number and atomic. We can therefore focus on the second argument, which is a list of numbers and which suggests that we use the list-processing template one more time:

(define (insert n alon)
  (cond 
    [(empty? alon) ...] 
    [else  ...  (first alon) ... (insert n (rest alon)) ...])) 

To fill the gaps in the template of insert, we again proceed on a case-by-case basis. The first case concerns the empty list. According to the purpose statement, insert must now construct a list with one number: n. Hence the answer in the first case is (cons n alon).

The second case is more complicated than that. When alon is not empty,

1. (first alon) is the first number on alon, and
2. (insert n (rest alon)) produces a sorted list consisting of n and all numbers on (rest alon).

(insert 3 (cons 4 (cons 5 (cons 6 empty))))

(insert 3 (cons -1 (cons 1 (cons 2 (cons 6 empty)))))

1. (first alon) is -1
2. (insert n (rest alon)) is (cons 1 (cons 2 (cons 3 (cons 6 empty)))).

Here is how we generalize from these examples. The problem requires a further case distinction. If (first alon) is smaller than (or equal to) n, all the items in alon are smaller than n; after all, alon is already sorted. The result is (cons n alon) for this case. If, however, (first alon) is larger than n, then we have not yet found the proper place to insert n into alon. We do know that the first item of the result must be the (first alon) and that n must be inserted into (rest alon). The final result in this case is

(cons (first alon) (insert n (rest alon)))

The translation of this discussion into Scheme requires the formulation of a conditional expression that distinguishes between the two possible cases:

(cond
  [(<= (first alon) n) ...] 
  [(> (first alon) n) ...]) 

;; sort : list-of-numbers -> list-of-numbers ;; to create a list of numbers with the same numbers as ;; alon sorted in descending order (define (sort alon) (cond [(empty? alon) empty] [(cons? alon) (insert (first alon) (sort (rest alon)))])) ;; insert : number list-of-numbers (sorted) -> list-of-numbers ;; to create a list of numbers from n and the numbers on ;; alon that is sorted in descending order; alon is sorted (define (insert n alon) (cond [(empty? alon) (cons n empty)] [else (cond [(<= (first alon) n) (cons n alon)] [(> (first alon) n) (cons (first alon) (insert n (rest alon)))])])) Figure: Sorting lists of numbers

Terminology: This particular program for sorting is known as INSERTION SORT in the programming literature. 

Exercise 12.2.1

Develop a program that sorts lists of mail messages by date. Mail structures are defined as follows:

(define-struct mail (from date message))

A mail-message is a structure: (make-mail name n s) where name is a string, n is a number, and s is a string.

Also develop a program that sorts lists of mail messages by name. To compare two strings alphabetically, use the string<? primitive. Solution

Exercise 12.2.2

Here is the function search:

;; search : number list-of-numbers -> boolean
(define (search n alon) 
  (cond 
    [(empty? alon) false] 
    [else (or (= (first alon) n) (search n (rest alon)))])) 

Develop the function search-sorted, which determines whether a number occurs in a sorted list of numbers. The function must take advantage of the fact that the list is sorted.

Terminology: The function search-sorted conducts a LINEAR SEARCH. Solution