Equality and Testing

Many of the functions we designed produce lists. When we test these functions, we must compare their results with the predicted value, both of which are lists. Comparing lists by hand is tedious and error-prone. Let's develop a function that consumes two lists of numbers and determines whether they are equal:

;; list=? : list-of-numbers list-of-numbers -> boolean
;; to determine whether a-list and another-list  
;; contain the same numbers in the same order 
(define (list=? a-list another-list) ...) 

Comparing two lists means looking at each item in both lists. This rules out designing list=? along the lines of replace-eol-with in section . At first glance, there is also no connection between the two lists, which suggests that we should use the modified design recipe.

Let's start with the table:

It has four cells, which implies that we need (at least) four tests and four cond-clauses in the template.

Here are five tests:

(list=? empty empty) 

(not 
  (list=? empty (cons 1 empty))) 

(not 
  (list=? (cons 1 empty) empty)) 

(list=? (cons 1 (cons 2 (cons 3 empty))) 
        (cons 1 (cons 2 (cons 3 empty)))) 

(not 
  (list=? (cons 1 (cons 2 (cons 3 empty))) 
          (cons 1 (cons 3 empty)))) 

Three of the template's four cond-clauses contain selector expressions and one contains natural recursions:

(define (list=? a-list another-list)
  (cond 
    [(and (empty? a-list) (empty? another-list)) ...] 
    [(and (cons? a-list) (empty? another-list)) 
     ... (first a-list) ... (rest a-list) ...] 
    [(and (empty? a-list) (cons? another-list)) 
    ... (first another-list) ... (rest another-list) ...] 
    [(and (cons? a-list) (cons? another-list)) 
     ... (first a-list) ... (first another-list) ... 
     ... (list=? (rest a-list) (rest another-list)) ... 
     ... (list=? a-list (rest another-list)) ... 
     ... (list=? (rest a-list) another-list) ...])) 

From the template to the complete definition is only a small step. Two lists can contain the same items only if they are both empty or constructed. This immediately implies true as the answer for the first clause and false for the next two. In the last clause, we have two numbers, the first of both lists, and three natural recursions. We must compare the two numbers. Furthermore, (list=? (rest a-list) (rest another-list)) computes whether the rest of the two lists are equal. The two lists are equal if, and only if, both conditions hold, which means we must combine them with an and:

(define (list=? a-list another-list)
  (cond 
    [(and (empty? a-list) (empty? another-list)) true] 
    [(and (cons? a-list) (empty? another-list)) false] 
    [(and (empty? a-list) (cons? another-list)) false] 
    [(and (cons? a-list) (cons? another-list)) 
     (and (= (first a-list) (first another-list)) 
          (list=? (rest a-list) (rest another-list)))])) 

Let us now take a second look at the connection between the two parameters. The first development suggests that the second parameter must have the same shape as the first one, if the two lists are to be equal. Put differently, we could develop the function based on the structure of the first parameter and check structure of the other one as needed.

The first parameter is a list of numbers, so we can reuse the template for list-processing functions:

(define (list=? a-list another-list)
  (cond 
    [(empty? a-list) ...] 
    [(cons? a-list) 
     ... (first a-list) ... (first another-list) ... 
     ... (list=? (rest a-list) (rest another-list)) ...])) 

Filling the gaps in this template is more difficult than for the first development of list=?. If a-list is empty, the answer depends on another-list. As the examples show, the answer is true if, and only if, another-list is also empty. Translated into Scheme this means that the answer in the first cond-clause is (empty? another-list).

If a-list is not empty, the template suggests that we compute the answer from

1. (first a-list), the first number of a-list;
2. (first another-list), the first number on another-list; and
3. (list=? (rest a-list) (rest another-list)), which determines whether the rest of the two lists are equal.

(and (= (first a-list) (first another-list))
     (list=? (rest a-list) (rest another-list))) 

We can overcome this problem with an additional condition:

(define (list=? a-list another-list)
  (cond 
    [(empty? a-list) (empty? another-list)] 
    [(cons? a-list) 
     (and (cons? another-list) 
          (and (= (first a-list) (first another-list)) 
               (list=? (rest a-list) (rest another-list))))])) 

In summary, list=? shows that, on occasion, we can use more than one design recipe to develop a function. The outcomes are different, though closely related; indeed, we could prove that the two always produce the same results for the same inputs. Also, the second development benefited from the first one.

Test both versions of list=?. Solution

Exercise 17.8.2

Simplify the first version of list=?. That is, merge neighboring cond-clauses with the same result by combining their conditions in an or-expression; switch cond-clauses as needed; and use else in the last clause of the final version. Solution

Exercise 17.8.3

Develop sym-list=?. The function determines whether two lists of symbols are equal. Solution

Exercise 17.8.4

Develop contains-same-numbers. The function determines whether two lists of numbers contain the numbers, regardless of the ordering. Thus, for example,

(contains-same-numbers (list 1 2 3) (list 3 2 1))

Exercise 17.8.5

The class of numbers, symbols, and booleans are sometimes called atoms:

An atom is either a number a boolean a symbol

Develop the function list-equal?, which consumes two lists of atoms and determines whether they are equal. Solution

A comparison between the two versions of list=? suggests that the second one is easier to understand than the first. It says that two compound values are equal if the second is made from the same constructor and the components are equal. In general, this idea is a good guide for the development of other equality functions.

Let's look at an equality function for simple Web pages to confirm this conjecture:

;; web=? : web-page web-page -> boolean
;; to determine whether a-wp and another-wp have the same tree shape 
;; and contain the same symbols in the same order 
(define (web=? a-wp another-wp) ...) 

A Web-page (short: WP) is either empty; (cons s wp) where s is a symbol and wp is a Web page; or (cons ewp wp) where both ewp and wp are Web pages.

The data definition has three clauses, which means that if we were to develop web=? with the modified design recipe, we would need to study nine cases. By using the insight gained from the development of list=? instead, we can start from the plain template for Web sites:

(define (web=? a-wp another-wp)
  (cond 
    [(empty? a-wp) ...] 
    [(symbol? (first a-wp)) 
     ... (first a-wp) ... (first another-wp) ... 
     ... (web=? (rest a-wp) (rest another-wp)) ...] 
    [else 
     ... (web=? (first a-wp) (first another-wp)) ... 
     ... (web=? (rest a-wp) (rest another-wp)) ...])) 

As we refine this template into a full definition now, we must again add conditions on another-wp to ensure that the selector expressions are justified:

(define (web=? a-wp another-wp)
  (cond 
    [(empty? a-wp) (empty? another-wp)] 
    [(symbol? (first a-wp)) 
     (and (and (cons? another-wp) (symbol? (first another-wp))) 
          (and (symbol=? (first a-wp) (first another-wp)) 
               (web=? (rest a-wp) (rest another-wp))))] 
    [else 
     (and (and (cons? another-wp) (list? (first another-wp))) 
          (and (web=? (first a-wp) (first another-wp)) 
               (web=? (rest a-wp) (rest another-wp))))])) 

Draw the table based on the data definition for simple Web pages. Develop (at least) one example for each of the nine cases. Test web=? with these examples. Solution

Exercise 17.8.7

Develop the function posn=?, which consumes two binary posn structures and determines whether they are equal. Solution

Exercise 17.8.8

Develop the function tree=?, which consumes two binary trees and determines whether they are equal. Solution

Exercise 17.8.9

Consider the following two, mutually recursive data definitions:

A Slist is either empty (cons s sl) where s is a Sexpr and sl is a Slist. A Sexpr is either a number a boolean a symbol a Slist

Develop the function Slist=?, which consumes two Slists and determines whether they are equal. Like lists of numbers, two Slists are equal if they contain the same item at analogous positions. Solution

Now that we have explored the idea of equality of values, we can return to the original motivation of the section: testing functions. Suppose we wish to test hours->wages from section :

  (hours->wages (cons 5.65 (cons 8.75 empty)) 
                      (cons 40 (cons 30 empty))) 
= (cons 226.0 (cons 262.5 empty)) 

Using equality functions like list=?, we can greatly reduce the need for manual inspection of test results. In our running example, we can add the expression

(list=? 
  (hours->wages (cons 5.65 (cons 8.75 empty)) 
                      (cons 40 (cons 30 empty))) 
  (cons 226.0 (cons 262.5 empty))) 

;; test-hours->wages : list-of-numbers list-of-numbers list-of-numbers -> test-result ;; to test hours->wages (define (test-hours->wages a-list another-list expected-result) (cond [(list=? (hours->wages a-list another-list) expected-result) true] [else (list ``bad test result:'' a-list another-list expected-result)])) Figure: A test function

Indeed, we can go even further. We can write a test function like the one in figure . The class of test-results consists of the value true and lists of four items: the string ``bad test result:'' followed by three lists. Using this new auxiliary function, we can test hours->wages as follows:

(test-hours->wages 
                        (cons 5.65 (cons 8.75 empty)) 
                        (cons 40 (cons 30 empty)) 
                        (cons 226.0 (cons 262.5 empty))) 

Testing with equal?: The designers of Scheme anticipated the need of a general equality procedure and provide:

;; equal? : any-value any-value -> boolean
;; to determine whether two values are structurally equivalent  
;; and contain the same atomic values in analogous positions  

Guideline on Testing

Use equal? for testing (when comparisons of values are necessary).

Unordered Lists: On some occasions, we use lists even though the ordering of the items doesn't play a role. For those cases, it is important to have functions such as contains-same-numbers (see exercise ) if we wish to determine whether the result of some function application contains the proper items. 

Define a test function for replace-eol-with from section  using equal? and formulate the examples as test cases using this function. Solution

Exercise 17.8.11

Define the function test-list-pick, which manages test cases for the list-pick function from section . Formulate the examples from the section as test cases using test-list-pick. Solution

Exercise 17.8.12

Define test-interpret, which tests interpret-with-defs from exercise , using equal?. Reformulate the test cases using this function. Solution