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.