MUTATIVE PROGRAMMING, CONTINUED

REVIEW

We have learned:

  1. use of set! command to mutate variable values
  2. use of begin to evaluate a sequence of expressions, rather than a single expression

We have applied these new mechanisms on problems of traffic lights, and address book management.

Review example: timing a command

Following are the code for insertion sort and merge sort algorithms we have developed before. We now want to compare running time performances of the two sorting methods.

    ;;; CREATE RANDOM LIST
    ;Function n:number k:number -> list
    ;Returns a list of size n, containin random numbers each between 0 and k
    (define (makeRandomList n k)
      (cond
        ((or (< n 0) (< k 0)) (error "invalid input"))
        ((= n 0) empty)
        (else (cons (random k) (makeRandomList (- n 1) k)))))

    ;;; INSERTION SORT
    ;Function number ascending-sorted-list -> sorted-list
    ;Returns a version of the list where the vlue is inserted in proper order
    (define (insert value sortedList)
        (cond
          ((empty? sortedList) (cons value empty))
          ((< value (first sortedList)) (cons value sortedList))
          (else (cons (first sortedList) (insert value (rest sortedList))))))

    ;Function list ascending-sorted-list -> sorted-list
    ;returns a list obtained by inserting each of the values in the list into sorted list in proper order
    (define (insertAll unsortedList sortedList)
        (cond
          ((empty? unsortedList) sortedList)
          (else 
           (insertAll 
            (rest unsortedList) 
            (insert (first unsortedList) sortedList)))))

    (define (insertionSorter unsortedList)
        (insertAll unsortedList empty))

    ;;;MERGE SORT
    ;Function that splits the given list into two equal size halves
    (define (split list)
        (splitAccumulator empty empty list))
    ;helper function
    (define (splitAccumulator half1 half2 originalList)
        (cond 
            ((empty? originalList) (list half1 half2))
            (else (splitAccumulator half2 (cons (first originalList) half1) (rest originalList)))))

    (define (sortHalvesHelper halves)
        (list (merge-sort (first halves)) (merge-sort (first (rest halves)))))

    (define (mergeHalvesHelper halves)
        (mergeHalves (first halves) (first (rest halves))))

    (define (mergeHalves half1 half2)
        (cond
            ((empty? half1) half2)
            ((empty? half2) half1)
            ((< (first half1) (first half2)) (cons (first half1) (mergeHalves (rest half1) half2)))
            (else (cons (first half2) (mergeHalves half1 (rest half2))))))

    (define (merge-sort unsorted)
        (cond
            ((or (empty? unsorted) (empty? (rest unsorted))) unsorted)
            (else (mergeHalvesHelper (sortHalvesHelper (split unsorted))))))

For measuring the time performance, we can use (current-inexact-milliseconds) function in Racket. For example:

    (define startTime (current-milliseconds))
    (merge-sort (makeRandomList 1000 1000))
    (- (current-milliseconds) startTime)

More versatile timer

    (define startTime void)
    (define (sortTimer sortFunction length)
        (begin
            (set! startTime (current-milliseconds))
            (sortFunction (makeRandomList length 1000))
            (- (current-milliseconds) startTime)))

    (sortTimer merge-sort 1000)
    (sortTimer insertionSorter 1000)

Using local variables and scope

Use of the global variable named startTimer is both misplaced and confusing, as apparent in its initialization. What we need instead is mutative variable which is valid within the local scope of the function only. The local command (somewhat similar to begin command) provides the mechanism for this:

        <exp>   =   (local (<def-1> ...<def-n>) <exp>)

i.e. the local function allows you to precede an expression with several variable definitions local to the scope. These variables are created everytime the function is evaluated.

    (define (sortTimer sortFunction length)
        (local ((define startTime (current-milliseconds)))
            (begin
                (sortFunction (makeRandomList length 1000))
                (- (current-milliseconds) startTime))))

    (sortTimer merge-sort 1000)
    (sortTimer insertionSorter 1000)

Exercise: Find maximum value in a list

Remember that finding the maximum in a list had a double recursion problem, and one needs a helper function to avoid this. Helper functions are a form of "litter" whose presence in the global scope is unnecessary. Thus one can use a local definiton to avoid such a situation. Solve the find-max problem using local definitions.

Exercise solution

    (define (maxOfList list)
      (cond
        ((empty? (rest list)) (first list))
        (else (local ((define maxtemp (maxOfList (rest list))))
                (cond 
                  ((> maxtemp (first list)) maxtemp)
                  (else (first list)))))))

Exercise: Fibonacci numbers

Apply the above pattern to solution of Fibonacci numbers. i.e. write a function which uses a locally defined accumulator.

Example: Reporting debug info

One can print messages on screen using (printf ...) function in Racket. For example:

    (printf "hello")

or if you want to produce combined messages, by using placeholders ~a, and/or newlines ~n:

    (printf "Result of ~a times ~a is ~a ~n" 4 5 (* 4 5))

The following program to compute factorials reports what it is doing:

    (define (factorial n)
      (cond
        ((< n 0) (error "invalid"))
        ((<= n 1) 1)
        (else (begin
                (printf "Computing factorial of ~a ~n" n)
                (* n (factorial (- n 1)))))))

    (check-expect (factorial 4) 24)