CS217 Day 3 Friday, March 31, 2000

Patterns of Recursion

• (remove-first s los) => los with first occurrence of s removed from los, a list-of-symbols

• (remove s los) => los with all occurrences of s removed from los, a list-of-symbols

• (remove s slst) => slst with all occurrences of s removed from slst, an s-list

  > (remove 'a '((a) (c a (t a d)) a b c))
  (() (c (t d)) b c)
  

• (notate-depth slst) => the s-list slst with each symbol s replaced with (s d), where d is the zero-based depth of s in slst.
  

  [s-list] ::= ({s-exp}*)
  [s-exp] ::= [symbol] | [s-list]
  

  Defining the depth of a symbol s relative to d to be (s d-1), we can write notate-depth using notate-depth-in-se.

  (define notate-depth
    (lambda (slst)
      (notate-depth-in-se slst 0)))
  
  (define notate-depth-in-se
    (lambda (se d)
      (if (symbol? se)
  	(list se (- d 1))
  	(map (lambda (se)
  	       (notate-depth-in-se se (+ d 1)))
  	  se))))
  

• (merge pred lon1 lon2) => merge of sorted lists of numbers lon1, lon2, sorted acording to pred
  

  (define merge
    (lambda (pred lon1 lon2)
      (cond ((null? lon1)
  	   lon2)
  	  ((null? lon2)
  	   lon1)
  	  (else
  	    (let ((x1 (car lon1))
  		  (x2 (car lon2)))
  	      (if (pred x1 x2)
  		  (cons x1 (merge pred (cdr lon1) lon2))
  		  (cons x2 (merge pred lon1 (cdr lon2)))))))))
  

• (insert-sort pred lon) => sorted lon according to pred, using merge

• (unzip lst) => unzipping of lst
  (unzip '(1 3 2 8 4)) => ((1 2 4) (3 8))

• (merge-sort pred lon) => merge sort of lon according to pred
  Recursive merge sort using "unzip":

  > (merge-sortr < '(4 3 2 1))
  |(merge-sortr # (4 3 2 1))
  | (merge-sortr # (4 2))
  | |(merge-sortr # (4))
  | |(4)
  | |(merge-sortr # (2))
  | |(2)
  | (2 4)
  | (merge-sortr # (3 1))
  | |(merge-sortr # (3))
  | |(3)
  | |(merge-sortr # (1))
  | |(1)
  | (1 3)
  |(1 2 3 4)
  (1 2 3 4)
  

  Iterative merge sort using mergeing successive pairs of lists:

  > (merge-sorti < '(4 3 2 1))
  |(merge-sort-lists # ((4) (3) (2) (1)))
  |(merge-sort-lists # ((3 4) (1 2)))
  |(merge-sort-lists # ((1 2 3 4)))
  |(1 2 3 4)
  (1 2 3 4)
  

• Some code: cs21d3.scm

Develop programs and proofs of correctness at the same time.

Study examples and finish Assignment 1.
On Monday, we'll do EOPL 1.3.

Problems to think about:

• Given a Scheme program, how would you mark each identifier as to whether it is free (must have a value at the top level) or bound (gets its value from an argument in a procedure call) or a let.
• If a variable is bound, not only mark it, but identify where it is declared -- where in what lambda expression, or where in what let.
• How would you do this on paper, and via a program?

This is what 1.3 is about. In Chapter 2, we'll learn how to make writing such programs easier.