CS257 lecture notes - 02/19/1999 
By :  Jason R Mastaler <mastaler@unm.edu>

Topics:
- working with lists
- procedures to sort lists
- association lists
- timing program execution
- next lecture

;;; INSERTION SORT

;;; sort a list of numbers
;;; (sortn '(7 1 6 2 5 3 4) => (1 2 3 4 5 6 7)

(define sortn
  (lambda (lis)
    (if (or (null? lis)
	    (null? (cdr lis)))
	lis
	(insertn (car lis)
		 (sortn (cdr lis))))))

;;; sortn helper functions - insertn

;;; (insertn 5 '()) => (5)
;;; (insertn 5 '(6 ...)) => (5 6 ...)
;;; (insertn 5 '(3 ...)) => (3 ?)

(define insertn
  (lambda (x lis)
    (cond ((null? lis) (list x))
	  ((<= x (car lis)) (cons x lis))
	  (else (cons (car lis)
		      (insertn x (cdr lis)))))))

;;; insertn and sortn test cases

> (insertn 3 '(4 5))
(3 4 5)
> (sortn '(7 1 6 2 5 3 4))
(1 2 3 4 5 6 7)
> (sortn '(2 2 2 2 ))
(2 2 2 2)
> (sortn '(7 1 2 6 2 5 3 2 4 11))
(1 2 2 2 3 4 5 6 7 11)
> (sortn '())
()

;;; MERGE SORT 
;;; represents a more effecient algorithm than INSERTION SORT

(define sortm
  (lambda (lis)
    (cond ((or (null? lis)
	       (null? (cdr lis))) lis)
	  (else (merge (sortm (half-of lis))
		       (sortm (other-half-of lis)))))))

;;; sortm helper functions - merge, half-of, other-half-of

;;; (merge '(1 3 5) '(2 7 9)) => (1 2 3 5 7 9)
;;; (merge '() X) => X
;;; (merge X '() => X
;;; (merge '(1...) '(2 ...)) => (1 ...)
;;; (merge '(2...) '(1 ...)) => (1 ...)

(define merge
  (lambda (lis1 lis2)
    (cond ((null? lis1) lis2)
	  ((null? lis2) lis1)
	  ((<= (car lis1) (car lis2))
	   (cons (car lis1) (merge (cdr lis1) lis2)))
	  (else
	   (merge lis2 lis1)))))

;;; merge test case

> (merge '(1 1 3 3 5 5 ) '(2 2 4 4 6 6 ))
(1 1 2 2 3 3 4 4 5 5 6 6)

;;; (half-of '(a b c d e f)) => (a c e)
;;;   = (cons 'a (other-half-of '(b c d e f)))
;;; (other-half-of '(a b c d e f)) => (b d f)
;;;      = (half-of '( b c d e f)) 

(define half-of
  (lambda (lis)
    (if (null? lis)
	lis
	(cons (car lis)
	      (other-half-of (cdr lis))))))

(define other-half-of
  (lambda (lis)
    (if (null? lis)
	lis
	(half-of (cdr lis)))))

;;; sortm test cases

> (sortm '())
()
> (sortm '(3))
(3)
> (sortm '(7 1 2 6 2 5 3 2 4 11))
(1 2 2 2 3 4 5 6 7 11)

;;; Association lists (alists)

;;; global definition of an association list
(define utensil-alist
  '((chinese chopsticks)
    (vietnamese chopsticks)
    (french fork)
    (british fork)
    (etheopian fingers)
    (prison spork)
    (k12 spork)))

;;; function to lookup a matching key in the alist
(define lookup
  (lambda (key alist)
    (cond ((null? alist) #f)
	  ((equal? (caar alist) key)
	   (cadar alist))
	  (else (lookup key (cdr alist))))))

;;; lookup test cases
> (lookup 'k12 utensil-alist)
spork
> (lookup 'german utensil-alist)
#f
> (lookup 'french utensil-alist)
fork
> (lookup 'chinese utensil-alist)
chopsticks

;;; (time expr) times the evaluation of expr, and prints timing
;;; information incliding the number of milliseconds of CPU time
;;; required to obtain this result, the number of ``real''
;;; milliseconds required for the result, and the amount of time spent
;;; in garbage-collection. The result of the time expression is the
;;; result of expr.  
;;;
;;; For more information on Timing Execution in MzScheme, see:
;;; http://www.cs.rice.edu/CS/PLT/packages/doc/mzscheme/node140.htm

> (time (sortm '(6 6 6 77 108 10 8 33 8 888 8)))
cpu time: 0 real time: 0 gc time: 0
(6 6 6 8 8 8 10 33 77 108 888)

Topics for next lecture:
- using lists to implement a tiny language