Processing Two Lists Simultaneously: Case 1

Next: Processing Two Lists Simultaneously: Up: Processing Two Complex Pieces Previous: Processing Two Complex Pieces

Processing Two Lists Simultaneously: Case 1

Consider the following contract, purpose statement, and header:

;; replace-eol-with : list-of-numbers list-of-numbers -> list-of-numbers
;; to construct a new list by replacing empty in alon1 with alon2 
(define (replace-eol-with alon1 alon2) ...)

The contract says that the function consumes two lists, which we haven't seen in the past. Let's see how the design recipe works in this case.

First, we make up examples. Suppose the first input is empty. Then replace-eol-with should produce the second argument, no matter what it is:

  (replace-eol-with empty L) 
= L

In this equation, L stands for an arbitrary list of numbers. Now suppose the first argument is not empty. Then the purpose statement requires that we replace empty at the end of alon1 with alon2:

(replace-eol-with (cons 1 empty) L) 
;; expected value: 
(cons 1 L)

(replace-eol-with (cons 2 (cons 1 empty)) L) 
;; expected value: 
(cons 2 (cons 1 L))

(replace-eol-with (cons 2 (cons 11 (cons 1 empty))) L) 
;; expected value:  
(cons 2 (cons 11 (cons 1 L)))

Again, L stands for any list of numbers in these examples.

;; replace-eol-with : list-of-numbers list-of-numbers -> list-of-numbers
;; to construct a new list by replacing empty in alon1 with alon2 
(define (replace-eol-with alon1 alon2) 
  (cond 
    ((empty? alon1) alon2) 
    (else (cons (first alon1) (replace-eol-with (rest alon1) alon2)))))

Figure: The complete definition of replace-eol-with

The examples suggest that it doesn't matter what the second argument is--as long as it is a list; otherwise, it doesn't even make sense to replace empty with the second argument. This implies that the template should be that of a list-processing function with respect to the first argument:

(define (replace-eol-with alon1 alon2)
  (cond 
    ((empty? alon1) ...) 
    (else ... (first alon1) ... (replace-eol-with (rest alon1) alon2) ... )))

The second argument is treated as it were an atomic piece of data.

Let's fill the gaps in the template, following the design recipe and using our examples. If alon1 is empty, replace-eol-with produces alon2 according to our examples. For the second cond-clause, when alon1 is not empty, we must proceed by inspecting the available expressions:

(first alon1) evaluates to the first item on the list, and
(replace-eol-with (rest alon1) alon2) replaces empty in (rest alon1) with alon2.

To gain a better understanding of what this means, consider one of the examples:

(replace-eol-with (cons 2 (cons 11 (cons 1 empty))) L) 
;; expected value:  
(cons 2 (cons 11 (cons 1 L)))

Here (first alon1) is 2, (rest alon1) is (cons 11 (cons 1 empty)), and (replace-eol-with (rest alon1) alon2) is (cons 11 (cons 1 alon2)). We can combine 2 and the latter with cons and can thus obtain the desired result. More generally,

(cons (first alon1) (replace-eol-with (rest alon1) alon2))

is the answer in the second cond-clause. Figure

contains the complete definition.

Exercises Exercise 17.1.1

In several exercises, we have used the Scheme operation append, which consumes three lists and juxtaposes their items:

(append (list 'a) (list 'b 'c) (list 'd 'e 'f))
;; expected value:  
(list 'a 'b 'c 'd 'e 'f)

Use replace-eol-with to define our-append, which acts just like Scheme's append. Solution

Exercise 17.1.2

Develop cross. The function consumes a list of symbols and a list of numbers and produces all possible pairs of symbols and numbers.

Example:

(cross '(a b c) '(1 2))
;; expected value:  
(list (list 'a 1) (list 'a 2) (list 'b 1) (list 'b 2) (list 'c 1) (list 'c 2))

Solution

Next: Processing Two Lists Simultaneously: Up: Processing Two Complex Pieces Previous: Processing Two Complex Pieces

PLT