Function Simplification

Next: Designing Functions that Consume Up: Processing Two Complex Pieces Previous: Processing Two Lists Simultaneously:

Function Simplification

The list-pick function in figure is more complicated than necessary. Both the first and the second cond-clause produce the same answer: false. In other words, if either

(and (= n 1) (empty? alos))

(and (> n 1) (empty? alos))

evaluates to true, the answer is false. We can translate this observation into a simpler cond-expression:

(define (list-pick n alos)
  (cond 
    [(or (and (= n 1) (empty? alos)) 
         (and (> n 1) (empty? alos))) false] 
    [(and (= n 1) (cons? alos)) (first alos)] 
    [(and (> n 1) (cons? alos)) (list-pick (rest alos) (sub1 n))]))

The new expression is a direct transliteration of our English observation.

To simplify this function even more, we need to get acquainted with an algebraic law concerning booleans:

  (or (and condition1 a-condition) 
      (and condition2 a-condition)) 
= (and (or condition1 condition2) 
       a-condition)

The law is called de Morgan's law of distributivity. Applying it to our function yields the following:

(define (list-pick n alos)
  (cond 
    [(and (or (= n 1) (> n 1)) 
          (empty? alos)) false] 
    [(and (= n 1) (cons? alos)) (first alos)] 
    [(and (> n 1) (cons? alos)) (list-pick (rest alos) (sub1 n))]))

Now consider the second part of the condition: (or (= n 1) (> n 1)). Because n belongs to N[>= 1], the condition is always true. But, if we replace it with true we get

(and (empty? alos)
     true)

which is clearly equivalent to (empty? alos). In other words, the function can be written as

(define (list-pick n alos)
  (cond 
    [(empty? alos) false] 
    [(and (= n 1) (cons? alos)) (first alos)] 
    [(and (> n 1) (cons? alos)) (list-pick (rest alos) (sub1 n))]))

which is already significantly simpler than that in figure

Still, we can do even better than that. The first condition in the latest version of list-pick filters out all those cases when alos is empty. Hence (cons? alos) in the next two clauses is always going to evaluate to true. If we replace the condition with true and simplify the and-expressions, we get the simplest possible version of list-pick, which is displayed in figure . While this last function is simpler than the original, it is important to understand that we designed both the original and the simplified version in a systematic manner and that we can therefore trust both. If we try to find the simple versions directly, we sooner or later fail to consider a case and produce flawed functions.

;; list-pick : list-of-symbols N[>= 1] -> symbol
;; to determine the nth symbol from alos, counting from 1; 
;; signals an error if there is no nth item 
(define (list-pick n alos) 
  (cond 
    [(empty? alos) (error 'list-pick ``list too short'')] 
    [(= n 1) (first alos)] 
    [(> n 1) (list-pick (rest alos) (sub1 n))]))

Figure: The simplified definition of list-pick

Exercises Exercise 17.4.1

Develop the function replace-eol-with following the strategy of section . Then simplify it systematically. Solution

Exercise 17.4.2

Simplify the function list-pick0 from exercise or explain why it can't be simplified. Solution

Next: Designing Functions that Consume Up: Processing Two Complex Pieces Previous: Processing Two Lists Simultaneously:

PLT