Exercise 194: Identify the values among the following expressions:

Exercise 194: Assume the definitions area in DrRacket contains (define (f x) x). Identify the values among the following expressions:

1. (cons f empty)
2. (f f)
3. (cons f (cons 10 (cons (f 10) empty)))

Explain why they are values and why the remaining expressions are not values.

Answer

I'm not completely confident on this answer - my understanding is that a value is being used in an expression, and a function will be using one (or more or less) values as input.

1.  (cons f empty)

In this case f and empty are values. They are being operated on by the cons.

2. (f f)

In this case the first f is a function, and the second f is a value - it is being operated on f

3. (cons f (cons 10 (cons (f 10) empty)))

In this case all the cons's are functions.  The first f is a value (being operated on by the first cons). The second f is a function (operating on the 10). The remaining 10 and empty are simple values.

Exercise 193: Take a look at this data definition

Exercise 193: Take a look at this data definition:

; A [Bucket ITEM] is

;   (make-bucket N [List-of ITEM])

; interp. the n in (make-bucket n l) is the length of l

;   i.e., (= (length l) n) is always true

When you instantiate Bucket with String, IR, and Posn, you get three different data collections. Describe each of them with a sentence and with two distinct examples.

Now consider this instantiations:

; [Bucket [List-of [List-of String]]]

Construct three distinct pieces of data that belong to this collection.

Answer

String
This is a data structure containing a number and a list of strings, where the number is the same as (length List-of-Strings)

eg (make-bucket 2 (list "The" "cat"))
eg (make-bucket 4 (list "The" "cat" "in" "the" "hat"))

IR
Assuming that 'IR' in this case refers back to the Inventory Records discussed previously, then this is a data structure containing a number and a list of Inventory Records, where the number is the same as (length List-of-IR)

 eg (make-bucket 2 (list (make-ir "widget" 3) (make-ir "gadget" 4)))
 eg (make-bucket 3 (list (make-ir "widget" 3) 
                         (make-ir "gadget" 4) 
                         (make-ir "midget" 9)))

Posn

This is a data structure containing a number and a list of Posns, where the number is the same as (length List-of-Posn)

eg (make-bucket 2 (list (make-posn 1 2) (make-posn 4 2)))
eg (make-bucket 3 (list (make-posn 1 2) (make-posn 4 2) (make-posn 9 1)))



[Bucket [List-of [List-of String]]] 
Construct three distinct pieces of data that belong to this collection.
;
We construct 3 lists here. Note that the number (1 2 and 3) refers to the number of Lists-of-strings we have, *not* the number of strings in the Lists-of-strings.

(make-bucket 1 (list (list "this" "is" "a" "string")))
(make-bucket 2 (list (list "this" "is" "a" "string")
                     (list "this" "is" "another" "string")))
(make-bucket 3 (list (list "this" "is" "a" "string")
                     (list "this" "is" "another" "string")
                     (list "this" "is" "a" "third" "string")
                     ))

Exercise 192: Here are two strange but similar data definitions:

Exercise 192: Here are two strange but similar data definitions:

; A Nested-string is one of: ; – String ; – (make-layer Nested-string)

; A Nested-number is one of: ; – Number ; – (make-layer Nested-number)

Both data definitions exploit this structure type definition:

(define-struct layer (stuff))

Both define nested forms of data’ one is about numbers and the other about strings. Make examples for both. Abstract over the two. Then instantiate the abstract definition to get back the originals.

Answer


A Nested String and Neste Number are data constructs that contain further datastructures of the same time.
This seems very similar to a list, but it's not quite the same...

; Nested-string examples - a simple example and then a nested example

(make-layer "cat")
(make-layer (make-layer "bob"))


; Nested-number examples - a simple example and then a nested example

(make-layer 1)
(make-layer (make-layer 2))

Abstraction of the two - this question seems a little strangely worded. I think it means to define an astract function definition.

; A [Nested ITEM] is one of:
; – empty
; – (make-layer [Nested ITEM])


Instantiate to get back to the originals. This part seems to simple - probably I am overlooking something here. This is just reversing our abstraction for each type

; String

; A Nested-string is one of:
; – empty
; – (make-layer [Nested-string])


; Number

; A Nested-number is one of:
; – empty
; – (make-layer [Nested-number])

Exercise 191: Abstract the following two functions into a single function:

Exercise 191: Abstract the following two functions into a single function:

; Nelon -> Number ; to determine the smallest ; number on l (define (inf l)   (cond     [(empty? (rest l))      (first l)]     [else      (cond        [(< (first l) (inf (rest l)))         (first l)]        [else         (inf (rest l))])]))

; Nelon -> Number ; to determine the largest ; number on l (define (sup l)   (cond     [(empty? (rest l))      (first l)]     [else      (cond        [(> (first l) (sup (rest l)))         (first l)]        [else         (sup (rest l))])]))

Both consume non-empty lists of numbers (Nelon) and produce a single number. The left one produces the smallest number in the list, the right one the largest.

Define inf-1 and sup-1 in terms of the abstract function. Test each of them with these two lists:

(list 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1)

(list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25)

Why are these functions slow on some of the long lists?

Answer

This is the same type of function as on the last question - to abstract it we can just pass in the conditional operator that we need.

; Condition, Nelon -> Number
; to determine the smallest/largest
; number on l
(define (function c l)
  (cond
    [(empty? (rest l))
     (first l)]
    [else
     (cond
       [(c (first l) (function c (rest l)))
        (first l)]
       [else
        (function c (rest l))])]))


; Nelon -> Number
; to determine the largest
; number on l
(define (sup-1 l)
  (function > l))

; Nelon -> Number
; to determine the smallest
; number on l
(define (inf-1 l)
  (function < l))

; some happy tests
(check-expect (inf-1 (list 1 2 3)) 1)
(check-expect (sup-1 (list 1 2 3)) 3)


Why do these take so long to process some of the lists?
This is dependent on the operator and the order of the list passed in. The function as given above will recurse to the end of the list or until the condition passed in is met. At each point that it recurses (with a slightly smaller list), that list will also require to be fully recursed all the way down. This leads to an exponential increase in the number of function calls as the list size increases.

Part Two - rewrite using min/max

; Condition, comparator, Nelon -> Number
; to determine the smallest/largest
; number on l
; c is < / >
; m is min / max
(define (function-2 c m l)
  (cond
    [(empty? (rest l))
     (first l)]
    [else
     (cond
       [(c (first l) (m (first (rest l))))
        (first l)]
       [else
        (function-2 c m (rest l))])]))

; Nelon -> Number
; to determine the largest
; number on l
(define (sup-2 l)
  (function-2 > max l))

; Nelon -> Number
; to determine the smallest
; number on l
(define (inf-2 l)
  (function-2  < min l))

; some happy tests
(check-expect (inf-2 (list 1 2 3)) 1)
(check-expect (sup-2 (list 1 2 3)) 3)

I'm not 100% happy with these definitions - it feels like I shouldn't need to be passing in both the min/max function name and the comparator (less-than and greater-than) but I cant see a better way of structuring these.

Why is this so much faster? If you turn on tracing within racket you can get a visual representation of what's going on - you can see that the number of function calls is not increasing exponentially with the size of the list. As min/max  take in only two numbers, and don't require recursion through the entire list to get the next result the function is only called a maximum of 25 times.

Exercise 190: Evaluate (squared>? 3 10), (squared>? 4 10), and (squared>? 5 10) by hand

Exercise 190: Evaluate (squared>? 3 10), (squared>? 4 10), and (squared>? 510) by hand. Then show that

(extract squared>? (list 3 4 5) 10)

evaluates to (list 4 5).

; Number Number -> Boolean

; is the area of a square with side x larger than c

(define (squared>? x c)

(> (* x x) c))

(squared>? 3 10)

(squared>? 3 10)
=
 (> (* 3 3) 10)
=
 (> 9 10)
= false

(squared>? 4 10)

(squared>? 4 10)
=
 (> (* 4 4) 10)
=
 (> 16 10)
= true

(squared>? 5 10)

(squared>? 5 10)
=
 (> (* 5 5) 10)
=
 (> 15 10)
= true

Part Two

Show that (extract squared>? (list 3 4 5) 10) evaluates to (list 4 5)

This exercise I found very long winded but it was very useful to step through and see how the recursion built up the final result. Even though I am comfortable using recursion, it's not often you step through it like this.

(extract squared>? (list 3 4 5) 10)
=
(cond
  [(empty? (list 3 4 5)) empty]
  [else (cond
          [(squared>? (first (list 3 4 5) 10))
           (cons (first (list 3 4 5)
                 (extract squared>? (rest (list 3 4 5)) 10)))]
          [else (extract squared>? (rest (list 3 4 5)) 10)])])

=
(cond
  [false empty]
  [else (cond
          [(squared>? (first (list 3 4 5) 10))
           (cons (first (list 3 4 5)
                 (extract squared>? (rest (list 3 4 5)) 10)))]
          [else (extract squared>? (rest (list 3 4 5)) 10)])])
=
  (cond
          [(squared>? (first (list 3 4 5) 10))
           (cons (first (list 3 4 5)
                 (extract squared>? (rest (list 3 4 5)) 10)))]
          [else (extract squared>? (rest (list 3 4 5)) 10)])
=
  (cond
          [(squared>? 3 10)
           (cons (first (list 3 4 5)
                 (extract squared>? (rest (list 3 4 5)) 10)))]
          [else (extract squared>? (rest (list 3 4 5)) 10)])
=
   (cond
          [false
           (cons (first (list 3 4 5)
                 (extract squared>? (rest (list 3 4 5)) 10)))]
          [else (extract squared>? (rest (list 3 4 5)) 10)])

=
  (extract squared>? (rest (list 3 4 5)) 10)

=
  ; time to recurse
  (extract squared>? (list 4 5) 10)
=
    (cond
      [(empty? (list  4 5)) empty]
      [else (cond
              [(squared>? (first (list 4 5) 10))
               (cons (first (list 4 5)
                            (extract squared>? (rest (list 4 5)) 10)))]
              [else (extract squared>? (rest (list 4 5)) 10)])])
=
    (cond
      [false empty]
      [else (cond
              [(squared>? (first (list 4 5) 10))
               (cons (first (list 4 5)
                            (extract squared>? (rest (list 4 5)) 10)))]
              [else (extract squared>? (rest (list 4 5)) 10)])])
=
    (cond
      [(squared>? 4 10))
       (cons (first (list 4 5)
                    (extract squared>? (rest (list 4 5)) 10)))]
      [else (extract squared>? (rest (list 4 5)) 10)])])  

=
    (cond
      [true
       (cons (first (list 4 5)
                    (extract squared>? (rest (list 4 5)) 10)))]
      [else (extract squared>? (rest (list 4 5)) 10)])])  

=

       (cons (first (list 4 5)
                    (extract squared>? (rest (list 4 5)) 10)))
     
=
      (cons  4  (extract squared>? (rest (list 4 5)) 10)))
; recurse again.  
=
      (cons  4  (extract squared>? (list  5)) 10)

=
      (cons  4
             (cond
               [empty? (list 5) empty]
               [else (cond
                       [(squared>? (first (list  5) 10))
                        (cons (first (list  5)
                                     (extract squared>? (rest (list  5)) 10)))]
                       [else (extract squared>? (rest (list  5)) 10)])]))

=
      (cons  4
             (cond
               [false empty]
               [else (cond
                       [(squared>? (first (list  5) 10))
                        (cons (first (list  5)
                                     (extract squared>? (rest (list  5)) 10)))]
                       [else (extract squared>? (rest (list  5)) 10)])]))


=
      (cons  4
             (cond
               [(squared>? (first (list  5) 10))
                (cons (first (list  5)
                             (extract squared>? (rest (list  5)) 10)))]
               [else (extract squared>? (rest (list  5)) 10)]))

=
      (cons  4
             (cond
               [(squared>? (  5 10))
                (cons (first (list  5)
                             (extract squared>? (rest (list  5)) 10)))]
               [else (extract squared>? (rest (list  5)) 10)]))

=
      (cons  4
             (cond
               [true
                (cons (first (list  5)
                             (extract squared>? (rest (list  5)) 10)))]
               [else (extract squared>? (rest (list  5)) 10)]))

=
      (cons  4
             (cons (first (list  5)
                          (extract squared>? (rest (list  5)) 10))))
             
=
      (cons  4
             (cons  5
                    (extract squared>? (rest (list  5)) 10)))

=
      (cons  4
             (cons  5
                    (extract squared>? empty 10)))

; recurse again
=
    (cons  4
           (cons  5
                  (cond
                    [empty? empty] empty)
                  [else (cond
                          [(squared>? (first empty 10))
                           (cons (first empty
                                        (extract squared>? (rest empty) 10)))]
                          [else (extract squared>? (rest empty) 10)])])))

=
      (cons  4
             (cons  5
                    (cond
               [true empty]
               [else (cond
                       [(squared>? (first empty 10))
                        (cons (first empty
                                     (extract squared>? (rest empty) 10)))]
                       [else (extract squared>? (rest empty) 10)])])))


=
      (cons  4
             (cons  5
                    empty))

= (list 4 5)