Similarities in Functions

The use of our design recipes entirely determines a function's template--or basic organization--from the data definition for the input. Indeed, the template is an alternative method of expressing what we know about the input data. Not surprisingly, functions that consume the same kind of data look alike.

;; contains-doll? : los -> boolean ;; to determine whether alos contains ;; the symbol 'doll (define (contains-doll? alos) (cond [(empty? alos) false] [else (cond [(symbol=? (first alos) ) true] [else (contains-doll? (rest alos))])])) ;; contains-car? : los -> boolean ;; to determine whether alos contains ;; the symbol 'car (define (contains-car? alos) (cond [(empty? alos) false] [else (cond [(symbol=? (first alos) ) true] [else (contains-car? (rest alos))])])) Figure: Two similar functions

Take a look at the two functions in figure , which consume lists of symbols (names of toys) and look for specific toys. The function on the left looks for 'doll, the one on the right for 'car in a list of symbols (los). The two functions are nearly indistinguishable. Each consumes lists of symbols; each function body consists of a cond-expressions with two clauses. Each produces false if the input is empty; each uses a second, nested cond-expression to determine whether the first item is the desired item. The only difference is the symbol that is used in the comparison of the nested cond-expression: contains-doll? uses 'doll and contains-car? uses 'car, of course. To highlight the differences, the two symbols are boxed.

Good programmers are too lazy to define several closely related functions. Instead they define a single function that can look for both a 'doll and a 'car in a list of toys. This more general function consumes an additional piece of data, the symbol that we are looking for, but is otherwise like the two original functions:

;; contains? : symbol los -> boolean
;; to determine whether alos contains the symbol s 
(define (contains? s alos) 
  (cond 
    [(empty? alos) false] 
    [else (cond 
            [(symbol=? (first alos)   ) 
             true] 
            [else 
             (contains? s (rest alos))])])) 

The process of combining two related functions into a single definition is called FUNCTIONAL ABSTRACTION. Defining abstract versions of functions is highly beneficial. The first benefit is that a single function can perform many different tasks. In our first example, contains? can search for many different symbols instead of just one concrete symbol.

;; below : lon number -> 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)])])) ;; above : lon number -> lon ;; to construct a list of those numbers ;; on alon that are above t (define (above alon t) (cond [(empty? alon) empty] [else (cond [( (first alon) t) (cons (first alon) (above (rest alon) t))] [else (above (rest alon) t)])])) Figure: Two more similar functions

In the case of contains-doll? and contains-car?, abstraction is uninteresting. There are, however, more interesting cases: see figure . The function on the left consumes a list of numbers and a threshold and produces a list of all those numbers that are below the threshold; the one on the right produces all those that are above a threshold.

The difference between the two functions is the comparison operator. The left uses <, the right one >. Following the first example, we abstract over the two functions with an additional parameter that stands for the concrete relational operator in below and above:

(define (filter1 rel-op alon t)
  (cond 
    [(empty? alon) empty] 
    [else (cond 
            [(   (first alon) t) 
             (cons (first alon) 
                   (filter1 rel-op (rest alon) t))] 
            [else 
             (filter1 rel-op (rest alon) t)])])) 

Let us see how filter1 works with an example. Clearly, as long as the input list is empty, the result is empty, too, no matter what the other arguments are:

  (filter1 < empty 5)
= empty 

  (filter1 < (cons 4 empty) 5)

The first step of the evaluation is based on the rule of application:

  (filter1 < (cons 4 empty) 5)

= (cond 
    [(empty? (cons 4 empty)) empty] 
    [else (cond 
            [(< (first (cons 4 empty)) 5) 
             (cons (first (cons 4 empty)) 
                   (filter1 < (rest (cons 4 empty)) 5))] 
            [else (filter1 < (rest (cons 4 empty)) 5)])]) 

The rest of the evaluation is straightforward:

  (cond
    [(empty? (cons 4 empty)) empty] 
    [else (cond 
            [(< (first (cons 4 empty)) 5) 
             (cons (first (cons 4 empty)) 
                   (filter1 < (rest (cons 4 empty)) 5))] 
            [else (filter1 < (rest (cons 4 empty)) 5)])])

= (cond 
    [(< (first (cons 4 empty)) 5) 
     (cons (first (cons 4 empty)) 
           (filter1 < (rest (cons 4 empty)) 5))] 
    [else (filter1 < (rest (cons 4 empty)) 5)])

= (cond 
    [(< 4 5) (cons (first (cons 4 empty)) 
                         (filter1 < (rest (cons 4 empty)) 5))] 
    [else (filter1 < (rest (cons 4 empty)) 5)])

= (cond 
    [true (cons (first (cons 4 empty)) 
                (filter1 < (rest (cons 4 empty)) 5))] 
    [else (filter1 < (rest (cons 4 empty)) 5)])

= (cons 4 (filter1 < (rest (cons 4 empty)) 5)) 
= (cons 4 (filter1 < empty 5)) 
= (cons 4 empty) 

Our final example is an application of filter1 to a list of two items:

  (filter1 < (cons 6 (cons 4 empty)) 5)
= (filter1 < (cons 4 empty) 5) 
= (cons 4 (filter1 < empty 5)) 
= (cons 4 empty) 

Verify the equation

  (filter1 < (cons 6 (cons 4 empty)) 5)
= (filter1 < (cons 4 empty) 5) 

Exercise 19.1.2

Evaluate the expression

  (filter1 > (cons 8 (cons 6 (cons 4 empty))) 5)

The calculations show that (filter1 < alon t) computes the same result as (below alon t), which is what we expected. Similar reasoning shows that (filter1 > alon t) produces the same output as (above alon t). So suppose we define the following:

;; below1 : lon number -> lon
(define (below1 alon t) 
  (filter1 < alon t)) 

;; above1 : lon number -> lon
(define (above1 alon t) 
  (filter1 > alon t)) 

Clearly, below1 produces the same results as below when given the same inputs, and above1 is related to above in the same manner. In short, we have defined below and above as one-liners using filter1.

Better yet: once we have an abstract function like filter1, we can put it to other uses, too. Here are three of them:

1. (filter1 = alon t): This expression extracts all those numbers in alon that are equal to t.
2. (filter1 <= alon t): This one produces the list of numbers in alon that are less than or equal to t.
3. (filter1 >= alon t): This last expression computes the list of numbers that are greater than or equal to the threshold.

In general, filter1's first argument need not even be one of Scheme's predefined operations; it can be any function that consumes two numbers and produces a boolean value. Consider the following example:

;; squared>? : number number -> boolean
(define (squared>? x c) 
  (> (* x x) c)) 

(filter1 squared>? (list 1 2 3 4 5) 10)

Here is the beginning of a simple hand-evaluation:

  (filter1 squared>? (list 1 2 3 4 5) 10)
= (cond 
    [(empty? (list 1 2 3 4 5)) empty] 
    [else (cond 
            [(squared>? (first (list 1 2 3 4 5)) 10) 
             (cons (first (list 1 2 3 4 5)) 
               (filter1 squared>? (rest (list 1 2 3 4 5)) 10))] 
            [else 
              (filter1 squared>? (rest (list 1 2 3 4 5)) 10)])]) 

= (cond
    [(squared>? 1 10) 
     (cons (first (list 1 2 3 4 5)) 
       (filter1 squared>? (rest (list 1 2 3 4 5)) 10))] 
    [else 
     (filter1 squared>? (rest (list 1 2 3 4 5)) 10)]) 

= (cond
    [false 
     (cons (first (list 1 2 3 4 5)) 
       (filter1 squared>? (rest (list 1 2 3 4 5)) 10))] 
    [else 
     (filter1 squared>? (rest (list 1 2 3 4 5)) 10)]) 

= (filter1 squared>? (list 2 3 4 5) 10)
= (filter1 squared>? (list 3 4 5) 10) 
= (filter1 squared>? (list 4 5) 10) 

Show that

  (filter1 squared>? (list 4 5) 10)
= (cons 4 (filter1 squared>? (list 5) 10)) 

Exercise 19.1.4

The use of squared>? also suggests that the following function will work, too:

;; squared10? : number number -> boolean
(define (squared10? x c) 
  (> (square x) 10)) 

This, in turn, implies another simplification of the function:

 
(define (filter predicate alon) 
  (cond 
    [(empty? alon) empty] 
    [else (cond 
            [(predicate (first alon)) 
             (cons (first alon) 
               (filter predicate (rest alon)))] 
            [else 
             (filter predicate (rest alon))])])) 

Show how to use filter to define functions that are equivalent to below and above. Test the definitions. Solution

So far we have seen that abstracted function definitions are more flexible and more widely usable than specialized definitions. A second, and in practice equally important, advantage of abstracted definitions is that we can change a single definition to fix and improve many different uses. Consider the two variants of filter1 in figure . The first variant flattened the nested cond-expression, something that an experienced programmer may wish to do. The second variant uses a local-expression that makes the nested cond-expression more readable.

(define (filter1 rel-op alon t) (cond [(empty? alon) empty] [(rel-op (first alon) t) (cons (first alon) (filter1 rel-op (rest alon) t))] [else (filter1 rel-op (rest alon) t)])) (define (filter1 rel-op alon t) (cond [(empty? alon) empty] [else (local ((define first-item (first alon)) (define rest-filtered (filter1 rel-op (rest alon) t))) (cond [(rel-op first-item t) (cons first-item rest-filtered)] [else rest-filtered]))])) Figure: Two modifications of filter1

Although both of these changes are trivial, the key is that all uses of filter1, including those to define the functions below1 and above1, benefit from this change. Similarly, if the modification had fixed a logical mistake, all uses of the function would be improved. Finally, it is even possible to add new tasks to abstracted functions, for example, a mechanism for counting how many elements are filtered. In that case all uses of the function would benefit from the new functionality. We will encounter this form of improvement later.

Abstract the following two functions into a single function:

;; min : nelon -> number
;; to determine the smallest number 
;; on alon 
(define (min alon) 
  (cond 
    [(empty? (rest alon)) (first alon)] 
    [else (cond 
            [(< (first alon) 
                      (min (rest alon))) 
             (first alon)] 
            [else 
             (min (rest alon))])])) 

;; max : nelon -> number
;; to determine the largest number 
;; on alon 
(define (max alon) 
  (cond 
    [(empty? (rest alon)) (first alon)] 
    [else (cond 
            [(> (first alon) 
                      (max (rest alon))) 
             (first alon)] 
            [else 
             (max (rest alon))])])) 

Both consume non-empty lists of numbers and produce a single number. The left one produces the smallest number in the list, the right one the largest.

Define min1 and max1 in terms of the abstracted function. Test each of them with the following two lists:

1. (list 3 7 6 2 9 8)
2. (list 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1)
3. (list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)

Improve the abstracted function. First, introduce a local name for the result of the natural recursion. Then introduce a local, auxiliary function that picks the ``interesting'' one of two numbers. Test min1 and max1 with the same inputs again. Solution

Exercise 19.1.6

Recall the definition of sort, which consumes a list of numbers and produces a sorted version:

;; sort : list-of-numbers -> list-of-numbers
;; to construct a list with all items from alon in descending order 
(define (sort alon) 
  (local ((define (sort alon) 
            (cond 
              [(empty? alon) empty] 
              [else (insert (first alon) (sort (rest alon)))])) 
          (define (insert an alon) 
            (cond 
              [(empty? alon) (list an)] 
              [else (cond 
                      [(> an (first alon)) (cons an alon)] 
                      [else (cons (first alon) (insert an (rest alon)))])]))) 
    (sort alon)))