CS 5010: Guided Practice 4.5 — Solution

    Consider the following function, defined on ListOfNumbers:
    
    ;; odd-elements : ListOfNumbers -> ListOfNumbers
    (define (odd-elements lst)
      (cond
        [(empty? lst) empty]
        [(empty? (rest lst)) (first lst)]
        [else (cons (first lst)
                    (odd-elements (rest (rest lst))))]))
    
    Which of the following are valid halting measures for odd-elements ?
    
    a) when lst is empty
    b) when lst has one or fewer elements
    c) the length of lst
    d) the number of elements of lst
    e) the largest element of lst
    
    Solution:
    
    (a) and (b) are not halting measures.  They are halting _conditions_.
    The point of a halting measure is to guarantee that the function
    eventually reaches the halting condition.
    
    (c) is a halting measure:  the length of any list is always a
    non-negative integer.  If (length lst) is k, then
    (length (rest (rest lst))) is k-2, which is always less than k.
    
    (d) is also a halting measure: the number of elements of lst is the
    same as its length
    
    (e) is not a halting measure.  Consider lst = (list 11 22 33 44). Its
    largest element is 44.  (rest (rest lst)) = (list 33 44), so its
    largest element is still 44.
    
    Next, consider the data type
    
    An AltList is one of
    -- empty
    -- (list Number AltList)
    
    and the function
    
    alt-odd-elements : AltList -> AltList
    (define (alt-odd-elements x)
      (cond
        [(empty? x) empty]
        [(empty? (second x)) (list (first x) empty)]
        [else (list (first x)
                    (alt-odd-elements (second (second x))))]))
    
    Which of the following are valid halting measures for odd-elements ?
    
    a) when lst is empty
    b) when lst has one or fewer elements
    c) the length of lst
    d) the number of elements of lst
    e) the largest element of lst
    
    All the answers are the same as for the previous example, except for
    (c).  The length of any AltList is either 0 or 2.   But the number of
    elements in the AltList still works as a halting measure.
    
    Halting measures for functions that follow the template from a data
    definition will almost always be very simple, like the ones considered
    here.  In Module 8 we will see more complicated halting measures.