Similarities in Data Definitions

Inspect the following two data definitions:

A list-of-numbers is either empty (cons n l) where n is a number and n is a list-of-numbers.

A list-of-IRs is either empty (cons n l) where n is an IR and n is a list-of-IRs.

Both define a class of lists. The one on the left is the data definition for lists of numbers; the one on the right describes lists of inventory records, which we represent with structures. The necessary structure and data definitions follow:

(define-struct ir (name price))

An IR is a structure: (make-ir n p) where n is a symbol and p is a number.

Given the similarity between the data definitions, functions that consume elements of these classes are similar, too. Take a look at the illustrative example in figure . The function on the left is the function below, which filters numbers from a list of numbers. The one on the right is below-ir, which extracts those inventory records from a list whose prices are below a certain threshold. Except for the name of the function, which is arbitrary, the two definitions differ in only one point: the relational operator.

;; below : number lon -> lon ;; to construct a list of those numbers ;; on alon that are below t (define (below alon t) (cond [(empty? alon) empty] [else (cond [(< (first alon) t) (cons (first alon) (below (rest alon) t))] [else (below (rest alon) t)])])) ;; below-ir : number loIR -> loIR ;; to construct a list of those records ;; on aloir that contain a price below t (define (below aloir t) (cond [(empty? aloir) empty] [else (cond [(<-ir (first aloir) t) (cons (first aloir) (below-ir (rest aloir) t))] [else (below-ir (rest aloir) t)])])) ;; <-ir : IR number -> boolean (define (<-ir ir p) (< (ir-price ir) p)) Figure: Marking the differences in similar functions

If we abstract the two functions, we obviously obtain filter1. Conversely, we can define below-ir in terms of filter1:

(define (below-ir1 aloir t)
  (filter1    aloir t)) 

Indeed, all we need is a function that compares items on the list with the items we pass to filter1 as the second argument. Here is a function that extracts all items with the same label from a list of inventory records:

;; find : loIR symbol -> boolean
;; to determine whether aloir contains a record for t 
(define (find aloir t) 
  (cons? (filter1 eq-ir? aloir t)))

;; eq-ir? : IR symbol -> boolean 
;; to compare ir's name and p 
(define (eq-ir? ir p) 
  (symbol=? (ir-name ir) p)) 

Determine the values of

1. (below-ir1 10 (list (make-ir 'doll 8) (make-ir 'robot 12)))
2. (find 'doll (list (make-ir 'doll 8) (make-ir 'robot 12) (make-ir 'doll 13)))

In short, filter1 uniformly works on many shapes of input data. The word ``uniformly'' means that if filter1 is applied to a list of X, its result is also a list of X--no matter what kind of Scheme data X is. Such functions are called POLYMORPHIC or GENERIC functions.

Of course, filter1 is not the only function that can process arbitrary lists. There are many other functions that process lists independently of what they contain. Here are two functions that determine the length of lists of numbers and IRs:

;; length-lon : lon -> number
(define (length-lon alon) 
  (cond 
    [(empty? alon) empty] 
    [else 
      (+ (length-lon (rest alon)) 1)])) 

;; length-ir : loIR -> number
(define (length-ir alon) 
  (cond 
    [(empty? alon) empty] 
    [else 
      (+ (length-ir (rest alon)) 1)])) 

The two functions differ only in their names. If we had chosen the same name, say, length, the two definitions would be identical.

To write precise contracts for functions such as length, we need data definitions with parameters. We call these PARAMETRIC DATA DEFINITIONS and agree that they do not specify everything about a class of data. Instead they use variables to say that any form of Scheme data can be used in a certain place. Roughly speaking, a parametric data definition abstracts from a reference to a particular collection of data in the same manner as a function abstracts from a particular value.

Here is a parametric definition of lists of ITEMs:

A list of ITEM is either empty or (cons s l) where s is and l is a list of ITEM.

The token ITEM is a TYPE VARIABLE that stands for any arbitrary collection of Scheme data: symbols, numbers, booleans, IRs, etc. By replacing ITEM with one of these names, we get a concrete instance of this abstract data definition for lists of symbols, numbers, booleans, IRs, etc. To make the language of contracts more concise, we introduce an additional abbreviation:

(listof ITEM)

In contracts we use (listof X) to say that a function works on all lists:

;; length : (listof X) -> number
;; to compute the length of a list  
(define (length alon) 
  (cond 
    [(empty? alon) empty] 
    [else (+ (length (rest alon)) 1)])) 

The function length is an example of simple polymorphism. It works on all classes of lists. While there are other useful examples of simple polymorphic functions, the more common cases require that we define functions like filter1, which consume a parametric form of data and functions that work on this data. This combination is extremely powerful and greatly facilitates the construction and maintenance of software systems. To understand it better, we will next discuss a revision of Scheme's grammar and new ways to write contracts.

Show how to use the abstracted version of sort from exercise  to sort a list of IRs in ascending and descending order. Solution

Exercise 19.2.3

Here is a structure definition for pairs

(define-struct pair (left right))

A (pair X Y) is a structure: (make-pair l r) where l is an X and r is a Y.

Using this abstract data definition, we can describe many different forms of pairs:

1. (pair number number), which is the class of pairs that combine two numbers;
2. (pair symbol number), which is the class of pairs that combine a number with a symbol; and
3. (pair symbol symbol), which is the class of pairs that combine two symbols.

By combining the abstract data definition for lists and pairs we can describe lists of parametric pairs with a single line:

(listof (pair X Y)) .

Some concrete examples of this abstract class of data are:

1. (listof (pair number number)), the list of pairs of numbers;
2. (listof (pair symbol number)), the list of pairs of symbols and numbers;
3. (listof (pair symbol symbol)), the list of pairs of symbols.

Develop the function lefts, which consumes a list of (pair X Y) and produces a corresponding list of X's; that is, it extracts the left part of each item in its input. Solution

Exercise 19.2.4

Here is a parametric data definition of non-empty lists:

A (non-empty-listof ITEM) is either (cons s empty), or (cons s l) where l is a (non-empty-listof ITEM) and s is always an ITEM.

Develop the function last, which consumes a (non-empty-listof ITEM) and produces the last ITEM in that list.

Hint: Replace ITEM with a fixed class of data to develop an initial draft of last. When finished, replace the class with ITEM throughout the function development. Solution