Exercise 164: Argue why it is acceptable to use last on Polygons.

Exercise 164: Argue why it is acceptable to use last on Polygons. Also argue why you may reuse the template for  connect-dots for last:

; NELoP -> Posn

; to extract the last Posn on p

(define (last p)

(first p))

If we go back to the definition of a Polygon we can see that it consists of either a list of three Posns, or

a Posn cons'd with another (valid) Polygon.  It is acceptable to use last on a polygon as it will always consist of  at least three valid Posn's and so a Posn will always be able to be safely returned. 

This question confused me at first, at in the stub function, the first p in the Polygon is returned. This is to make the stub valid as it can't just return P as then it would be returning a Polygon, rather than a Posn. However, reading a bit further it is clear that this is just a stub and not the complete function!

We are told we can re-use the template we used for the connect-dots:

(define (last p)

(cond

[(empty? (rest p)) (... (first p) ...)]

[else (... (first p) ... (last (rest p)) ...)]))

The reason we can use this template is that the definition of Polygon guarantees that this will be a Non empty list of Posns.

; a Polygon is one of:; 

; – (list Posn Posn Posn); 

; – (cons Posn Polygon)

Even though we're not asked to implement the function last I thought I would have a go before reading on further.


First create some simple tests:


; Check a list of 3 posns (a triangle) correctly returns the 
; last point
(check-expect (last (list (make-posn 10 10)
                          (make-posn 60 60)
                          (make-posn 10 60)))
              (make-posn 10 60))


; Check a list of 4 posns (a square) correctly returns the 
; last point
(check-expect (last (list (make-posn 10 10)
                          (make-posn 60 10)
                          (make-posn 60 60)
                          (make-posn 10 60)))
              (make-posn 10 60))

              

I chose just to use the length of the list rather than getting the rest of the list three times.  Both of these

definitions pass the tests, but looking back on the text we find this quote:

"Since all Polygons consist of at least three Posns, using rest three times is legal. Unlike length, rest is also a primitive, easy-to-understand operation with a clear operational meaning. It selects the second field in a cons structure and that is all it does."

I'm not going to argue with the author, but from my perspective, using a primitive operator is not neccessarily better than a higher level operator - especially when the latter is shorter and easier to read.

; NELoP -> Posn
; to extract the last Posn on p
(define (my_last p)
  (cond
    [(= (length p) 3) (third p)]
    [else (last (rest p))]))


; NELoP -> Posn
; extract the last Posn from p
(define (last p)
  (cond
    [(empty? (rest (rest (rest p)))) (third p)]
    [else (last (rest p))]))

Exercise 163: Adapt the second example for render-poly to connect-dots.

Exercise 163: Adapt the second example for render-poly to connect-dots.

I was unable to answer this question.  We needed to take the supplied render-poly function and convert it to use connect-dots.

This was the best I was able to come up with

; Polygon -> Image
; to render the given polygon p into MT
(define (render-poly p)
  (cond ((empty? p) p)
        (else (
               (connect-dots (first p))
               (render-poly (rest p))  
               ))))

The issue with this is that you can't call two functions in a row like that. (At least not with the knowledge we have right now)

If you try and run this, you will get an error:

function call: expected a function after the open parenthesis, but received #<image>

I don't think there is a way to do this without changing render-poly or connect-dots signatures.

Finally I had to sneak a peak at the answer... (which is luckily given shortly further down in the text)

; Polygon -> Image

; add the Polygon p into an image in MT

(define (render-polygon p)

(render-line (connect-dots p) (first p) (last p)))

In hind-sight this is fairly obvious - or at least the part about using render-line. connect-dots is going to draw the actual polygon for us and return our image. What I don't understand is why we need to draw a line between (first p) and (last p).

Presumably the function connect-dots is going to draw all but this last line (due to the bug in the first implementation given) and we are filling in this last line manually at the end.

This is not very well explained - but hopefully it will become clear as we progress on to question 164. Either I missed something obvious in the text, or I'm not sure how we could have answered this given the information we had.

Exercise 162: Here is the function 'search'...

Exercise 162: Here is the function search:

; Number List-of-numbers -> Boolean

(define (search n alon)

(cond

[(empty? alon) false]

[else (or (= (first alon) n) (search n (rest alon)))]))

It determines whether some number occurs in a list of numbers. The function may have to traverse the entire list to find out that the number of interest isn’t contained in the list.
Develop the function search-sorted, which determines whether a number occurs in a sorted list of numbers. The function must take advantage of the fact that the list is sorted.

The function we are developing here is quite similar to the last two questions. The only real difference is that we are starting to look at trying to optimise list traversal. This is simple enough to do as the list is already sorted and we can easily check where we are in the list and return as soon as we know the number can't be in the list (as we have gone past the place where the number would have to be).

Firstly we need (or desire) to include racket/base. This will give us access to fprintf - a function that can print out some diagnostic information so that we prove that we are taking advantage of the fact that the list is sorted. This is absolutely not required for the question.


(require racket/base)


; this testlist is just for ease of testing.
(define TESTLIST (list 100 80 45 23 22 20 3 1))


; tests are pretty straight forward - either the number in the list is there or it is not.
(check-expect (search-sorted 100 TESTLIST) true)
(check-expect (search-sorted 1 TESTLIST) true)
(check-expect (search-sorted 50 TESTLIST) false)




This is the search-sorted function. This is fairly straight forward. First I display some information as to what the current state of the list is and where we are at, then I recurse further down the list. If the first item on the list is larger than where we are at, then the list can't contain the n we are searching for and we immediately return false.


; Number List-of-numbers -> Boolean
(define (search-sorted n alon)
  (fprintf (current-output-port) 
           "searching for ~a First of alon: ~a. Alon is ~a \n" n (first alon) alon)
  (cond
    [(or (empty? alon)
         (> n (first alon))) false]
    [else (or (= (first alon) n) (search-sorted n (rest alon)))]))

This is the output from running out test cases on the above function. As you can see the first test case (where the n is not present in the list) iterates thru the entire list. For the second test case, as soon as we find the head of the list is less than 50, we stop recursing and return false.

Test Case 1

searching for 100 First of alon is 100.     Alon is (100 80 45 23 22 20 3 1) 
searching for 1 First of alon is 100.     Alon is (100 80 45 23 22 20 3 1) 
searching for 1 First of alon is 80.     Alon is (80 45 23 22 20 3 1) 
searching for 1 First of alon is 45.     Alon is (45 23 22 20 3 1) 
searching for 1 First of alon is 23.     Alon is (23 22 20 3 1) 
searching for 1 First of alon is 22.     Alon is (22 20 3 1) 
searching for 1 First of alon is 20.     Alon is (20 3 1) 
searching for 1 First of alon is 3.     Alon is (3 1) 
searching for 1 First of alon is 1.     Alon is (1) 

Test Case 2

searching for 50 First of alon is 100.     Alon is (100 80 45 23 22 20 3 1) 
searching for 50 First of alon is 80.     Alon is (80 45 23 22 20 3 1) 
searching for 50 First of alon is 45.     Alon is (45 23 22 20 3 1)