Generalizing Problems, Generalizing Functions

Next: Extended Exercise: Rearranging Words Up: Composing FunctionsRevisited Again Previous: Recursive Auxiliary Functions

Generalizing Problems, Generalizing Functions

Consider the problem of drawing a polygon, that is, a geometric shape with an arbitrary number of corners. A natural representation for a polygon is a list of posn structures:

A list-of-posns is either

the empty list, empty, or
(cons p lop) where p is a posn structure and lop is a list of posns.

Each posn represents one corner of the polygon. For example,

(cons (make-posn 10 10)
  (cons (make-posn 60 60) 
    (cons (make-posn 10 60) 
      empty)))

represents a triangle. The question is what empty means as a polygon. The answer is that empty does not represent a polygon and therefore shouldn't be included in the class of polygon representations. A polygon should always have at least one corner, and the lists that represent polygons should always contain at least one posn. This suggest the following data definition:

A polygon is either

(cons p empty) where p is a posn, or
(cons p lop) where p is a posn structure and lop is a polygon.

In short, a discussion of how the chosen set of data (lists of posns) represents the intended information (geometric polygons) reveals that our choice was inadequate. Revising the data definition brings us closer to our intentions and makes it easier to design the program.

Because our drawing primitives always produce true (if anything), it is natural to suggest the following contract and purpose statement:

;; draw-polygon : polygon -> true
;; to draw the polygon specified by a-poly  
(define (draw-polygon a-poly) ...)

In other words, the function draws the lines between the corners and, if all primitive drawing steps work out, it produces true. For example, the above list of posns should produce a triangle.

Although the data definition is not just a variant on our well-worn list theme, the template is close to that of a list-processing function:

 
;; draw-polygon : polygon -> true 
;; to draw the polygon specified by a-poly  
(define (draw-polygon a-poly) 
  (cond 
    [(empty? (rest a-poly)) ... (first a-poly) ...] 
    [else ... (first a-poly) ... 
        ... (second a-poly) ... 
        ... (draw-polygon (rest a-poly)) ...]))

Given that both clauses in the data definition use cons, the first condition must inspect the rest of the list, which is empty for the first case and non-empty for the second one. Furthermore, in the first clause, we can add (first a-poly); and in the second case, we not only have the first item on the list but the second one, too. After all, polygons generated according to the second clause consist of at least two posns.

Now we can replace the ``...'' in the template to obtain a complete function definition. For the first clause, the answer must be true, because we don't have two posns that we could connect to form a line. For the second clause, we have two posns, we can draw a line between them, and we know that (draw-polygon (rest a-poly)) draws all the remaining lines. Put differently, we can write

(draw-solid-line (first a-poly) (second a-poly))

in the second clause because we know that a-poly has a second item. Both (draw-solid-line ...) and (draw-poly ...) produce true if everything goes fine. By combining the two expressions with and, draw-poly draws all lines.

Here is the complete function definition:

 
(define (draw-polygon a-poly) 
  (cond 
    [(empty? (rest a-poly)) true] 
    [else (and (draw-solid-line (first a-poly) (second a-poly)) 
               (draw-polygon (rest a-poly)))]))

Unfortunately, testing it with our triangle example immediately reveals a flaw. Instead of drawing a polygon with three sides, the function draws only an open curve, connecting all the corners but not closing the curve:

Mathematically put, we have defined a more general function than the one we wanted. The function we defined should be called ``connect-the-dots'' and not draw-polygon.

To get from the more general function to what we want, we need to figure out some way to connect the last dot to the first one. There are several ways to accomplish this goal, but all of them mean that we define the main function in terms of the function we just defined or something like it. In other words, we define one auxiliary function in terms of a more general one.

One way to define the new function is to add the first position of a polygon to the end and to have this new list drawn. A symmetric method is to pick the last one and add it to the front of the polygon. A third alternative is to modify the above version of draw-polygon so that it connects the last posn to the first one. Here we discuss the first alternative; the exercises cover the other two.

To add the last item of a-poly at the beginning, we need something like

(cons (last a-poly) a-poly)

where last is some auxiliary function that extracts the last item from a non-empty list. Indeed, this expression is the definition of draw-polygon assuming we define last: see figure

Formulating the wish list entry for last is straightforward:

;; last : polygon -> posn
;; to extract the last posn on a-poly 
(define (last a-poly) ...)

And, because last consumes a polygon, we can reuse the template from above:

 
(define (last a-poly) 
  (cond 
    [(empty? (rest a-poly)) ... (first a-poly) ...] 
    [else ... (first a-poly) ... 
        ... (second a-poly) ... 
        ... (last (rest a-poly)) ...]))

Turning the template into a complete function is a short step. If the list is empty except for one item, this item is the desired result. If (rest a-poly) is not empty, (last (rest a-poly)) determines the last item of a-poly. The complete definition of last is displayed at the bottom of figure .

;; draw-polygon : polygon -> true
;; to draw the polygon specified by a-poly  
(define (draw-polygon a-poly) 
  (connect-dots (cons (last a-poly) a-poly)))

;; connect-dots : polygon -> true 
;; to draw connections between the dots of a-poly 
(define (connect-dots a-poly) 
  (cond 
    [(empty? (rest a-poly)) true] 
    [else (and (draw-solid-line (first a-poly) (second a-poly) RED) 
               (connect-dots (rest a-poly)))]))

;; last : polygon -> posn 
;; to extract the last posn on a-poly 
(define (last a-poly) 
  (cond 
    [(empty? (rest a-poly)) (first a-poly)] 
    [else (last (rest a-poly))]))

Figure: Drawing a polygon

In summary, the development of draw-polygon naturally led us to consider a more general problem: connecting a list of dots. We solved the originally problem by defining a function that uses (a variant of) the more general function. As we will see again and again, generalizing the purpose of a function is often the best method to simplify the problem.

Exercises

Exercise 12.3.1

Modify draw-polygon so that it adds the first item of a-poly to its end. This requires a different auxiliary function: add-at-end. Solution

Exercise 12.3.2

Modify connect-dots so that it consumes an additional posn structure to which the last posn is connected.

Then modify draw-polygon to use this new version of connect-dots.

Accumulator: The new version of connect-dots is a simple instance of an accumulator-style function. In part we will discuss an entire class of such problems. Solution

Next: Extended Exercise: Rearranging Words Up: Composing FunctionsRevisited Again Previous: Recursive Auxiliary Functions

PLT