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)
             

Exercise 189: Evaluate the expression

Exercise 189: Evaluate the expression
(extract < (cons 8 (cons 6 (cons 4 empty))) 5)

;extract function from question(define (extract R l t)
  (cond    [(empty? l) empty]    [else (cond            [(R (first l) t)             (cons (first l) (extract R (rest l) t))]            [else             (extract R (rest l) t)])]))

 Answer

(extract < (cons 8 (cons 6 (cons 4 empty))) 5)

=  
(cond
  [(empty? (cons 8 (cons 6 (cons 4 empty))) empty]
  [else (cond
          [(< (first (cons 8 (cons 6 (cons 4 empty))) 5)
           (cons (first (cons 8 (cons 6 (cons 4 empty))))
                 (extract < (rest (cons 8 (cons 6 (cons 4 empty)))) 5))]
          [else (extract < (rest (cons 8 (cons 6 (cons 4 empty)))) 5)])])

=   
(cond
  [false empty]
  [else (cond
          [(< (first (cons 8 (cons 6 (cons 4 empty))) 5)
           (cons (first (cons 8 (cons 6 (cons 4 empty))))
                 (extract < (rest (cons 8 (cons 6 (cons 4 empty)))) 5))]
          [else (extract < (rest (cons 8 (cons 6 (cons 4 empty)))) 5)])])


=  
(cond
  [else (cond
          [(< 8 5)
           (cons (first (cons 8 (cons 6 (cons 4 empty))))
                 (extract < (rest (cons 8 (cons 6 (cons 4 empty)))) 5))]
          [else (extract < (rest (cons 8 (cons 6 (cons 4 empty)))) 5)])])

=   
(cond
  [else (cond
          [false
           (cons (first (cons 8 (cons 6 (cons 4 empty))))
                 (extract < (rest (cons 8 (cons 6 (cons 4 empty)))) 5))]
          [else (extract < (rest (cons 8 (cons 6 (cons 4 empty)))) 5)])])

=   
 (extract < (rest (cons 8 (cons 6 (cons 4 empty)))) 5)


=   
 (extract <  (cons 6 (cons 4 empty)) 5)


This takes us right back to the problem from the last exercise and we can use the rest of the solution from there.

Exercise 188: Check step 1 of the last calculation

Exercise 188: Check step 1 of the last calculation
 
Show every step.

(extract < (cons 6 (cons 4 empty)) 5)

= (extract < (cons 4 empty) 5)

Answer

; extract function in question.
(define (extract R l t)
  (cond
    [(empty? l) empty]
    [else (cond
            [(R (first l) t)
             (cons (first l) (extract R (rest l) t))]
            [else
             (extract R (rest l) t)])]))


I have answered this as a series of steps. This anwer is a bit verbose, but I have shown each change an a seperate step.

=  
(cond
  [(empty? (cons 6 (cons 4 empty))) empty]
  [else (cond
          [(< (first (cons 6 (cons 4 empty))) 5)
           (cons (first (cons 6 (cons 4 empty)))
                 (extract < (rest (cons 6 (cons 4 empty))) 5))]
          [else (extract < (rest (cons 6 (cons 4 empty))) 5)])])


=   
(cond
  [false empty]
  [else (cond
          [(< (first (cons 6 (cons 4 empty))) 5)
           (cons (first (cons 6 (cons 4 empty)))
                 (extract < (rest (cons 6 (cons 4 empty))) 5))]
          [else (extract < (rest (cons 6 (cons 4 empty))) 5)])])


=  
(cond
  [else (cond
          [(< (first (cons 6 (cons 4 empty))) 5)
           (cons (first (cons 6 (cons 4 empty)))
                 (extract < (rest (cons 6 (cons 4 empty))) 5))]
          [else (extract < (rest (cons 6 (cons 4 empty))) 5)])])


=   
(cond
  [else (cond
          [(< 6 5)
           (cons (first (cons 6 (cons 4 empty)))
                 (extract < (rest (cons 6 (cons 4 empty))) 5))]
          [else (extract < (rest (cons 6 (cons 4 empty))) 5)])])

=  
(cond
  [else (cond
          [true
           (cons (first (cons 6 (cons 4 empty)))
                 (extract < (rest (cons 6 (cons 4 empty))) 5))]
          [else (extract < (rest (cons 6 (cons 4 empty))) 5)])])

=   
 (cons (first (cons 6 (cons 4 empty)))
       (extract < (rest (cons 6 (cons 4 empty))) 5))]

=  
 (cons  6 (extract < (rest (cons 6 (cons 4 empty))) 5))


=   ; step seven - and we get the result we are looking for
 (cons  6 (extract < (cons 4 empty)) 5)


*******
=  ; recursing now...
  (cond
    [(empty? (cons 4 empty)) empty]
    [else (cond
            [(< (first  (cons 4 empty)) 5)
             (cons (first  (cons 4 empty))
                   (extract < (rest  (cons 4 empty)) 5))]
            [else (extract < (rest  (cons 4 empty)) 5)])])

= 
  (cond
    [false empty]
    [else (cond
            [(< (first  (cons 4 empty)) 5)
             (cons (first  (cons 4 empty))
                   (extract < (rest  (cons 4 empty)) 5))]
            [else (extract < (rest  (cons 4 empty)) 5)])])

= 
  (cond
    [else (cond
            [(< (first  (cons 4 empty)) 5)
             (cons (first  (cons 4 empty))
                   (extract < (rest  (cons 4 empty)) 5))]
            [else (extract < (rest  (cons 4 empty)) 5)])])
= 
  (cond
    [else (cond
            [(<  4 5)
             (cons (first  (cons 4 empty))
                   (extract < (rest  (cons 4 empty)) 5))]
            [else (extract < (rest  (cons 4 empty)) 5)])])

= 
  (cond
    [else (cond
            [(<  4 5)
             (cons (first  (cons 4 empty))
                   (extract < (rest  (cons 4 empty)) 5))]
            [else (extract < (rest  (cons 4 empty)) 5)])])

Exercise 187: Create test suites for the following two functions:

Exercise 187: Create test suites for the following two functions:

; Lon -> Lon ; add 1 to each number on l (define (add1* l)   (cond     [(empty? l) false]     [else      (cons (add1 (first l))            (add1* (rest l)))]))

; Lon -> Lon ; add 5 to each number on l (define (plus5 l)   (cond     [(empty? l) false]     [else      (cons (+ (first l) 5)            (plus5 (rest l)))]))

Then abstract over them. Define above two functions in terms of the abstraction as one-liners and use the existing test suites to confirm that the revised definitions work properly. Finally, design a function that subtracts 2 from each number on a given list.

I had to fix the above functions to do this exercise - the empty case is returning false in the book which will make the cons fail as you can't cons a list to false.

Test Cases

; simple happy test - all numbers should be increased by one
(check-expect (add1* '(1 2 3))
              '(2 3 4))

; test empty list returns empty
(check-expect (add1* empty)
              empty)


; simple happy test - all numbers should be increased by five
(check-expect (plus5 '(1 2 3))
              '(6 7 8))

; test empty list returns empty
(check-expect (plus5 empty)
              empty)


; My abstraction - allow them to pass in the size of the increment
; Number, Lon -> Lon
(define (inc* amount l)
  (cond
    [(empty? l) empty]
    [else
     (cons (+ (first l) amount)
           (inc* amount (rest l) ))]))


; Lon -> Lon
; add 1 to each number on l
(define (add1* l)
   (inc* 1 l))

; Lon -> Lon
; add 5 to each number on l
(define (plus5 l)
  (inc* 5 l))

Part Two

 Define a function that subtracts 2 from each member of a list.

; a function that subtracts 2 from each member of a list
; Lon -> Lon
(define (minus2 l)
  (inc* -2 l))

; happy test
(check-expect (minus2 '(5 7 9))
              '(3 5 7))

Exercise 186: Use contains? to define functions that search for "atom", "basic", and "zoo", respectively

Exercise 186: Use contains? to define functions that search for "atom", "basic", and "zoo", respectively.

The contains function is supplied by the text

; String Los -> Boolean

; to determine whether l contains the string s

(define (contains? s l)

(cond

[(empty? l) false]

[else (or (string=? (first l) s)

(contains? s (rest l)))]))

Answer 

; String Los -> Boolean
; to determine whether l contains the string s
(define (contains? s l)
  (cond
    [(empty? l) false]
    [else (or (string=? (first l) s)
              (contains? s (rest l)))]))

; Los -> Boolean
; to determine whether l contains the string "atom"
(define (contains-atom l)
  (contains? "atom" l))


; Los -> Boolean
; to determine whether l contains the string "basic"
(define (contains-basic l)
  (contains? "basic" l))


; Los -> Boolean
; to determine whether l contains the string "zoo"
(define (contains-zoo l)
  (contains? "zoo" l))