Exercise 196: Develop a-function=.

Exercise 196: Develop a-function=. The function determines whether two functions from numbers to numbers produce the same results for 1.2, 3, and -5.775.

Can we hope to define function=?, which determines whether two functions from numbers to numbers are equal?

Answer

; returns true if the functions supplied return the same value for 3
; different numbers
; Function, Function -> Booleas
(define (a-function= x y)
  (and (a-helper x y 1.2) (a-helper x y 3) (a-helper x y -5.775)))
   

; tests if the two functions supplied return the same number
; Function, Function, Number -> Boolean
(define (a-helper x y number)
  (= (x number) (y number)))



; some test functions - both 1 and 3 should return the same value, 2 should not.
(define (test1 x) (* 2 x))
(define (test2 x) (* 3 x))
(define (test3 x) (+ x x))

; and some tests
(check-expect (a-function= test1 test2) false)
(check-expect (a-function= test1 test3) true)



Can we hope to define function=?, which determines whether two functions from numbers to numbers are equal?

We cannot (depending on how you define 'equal functions'). We can check to see the return value of the functions are equal for a specified set of arguments, but without the code introspection offered by languages such as Ruby, you can't see what is inside these black box functions.  

Exercise 195: Argue why the following sentences are now legal definitions

Exercise 195: Argue why the following sentences are now legal definitions:

1. (define (f x) (x 10))
2. (define (f x) (x f))
3. (define (f x y) (x 'a y 'b))

Explain your reasoning.

1)  (define (f x) (x 10))

We are now allowed to:

1. include the names of functions and primitive operations in the definition. 
2. use variables and function parameters in the first position in a definition

In this case the parameter x is a function that will have the value 10 applied to it.  As we can include functions in a function definition this is legal.

2) (define (f x) (x f))

In this case, both x and f are functions. This function will call the function x passing in the value of itself (ie f). As we can include functions in function definitions, this is now legal.

3) (define (f x y) (x 'a y 'b))

In this case f and x are functions, and y is a value (that could potentially be a function!). The function x will be called, with the values 'a, y and 'b being passed into it. At this point y could either be a value, or a function and provided that the function x is expected the actual item in, this code is legal.

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.