;; Sid Stamm
;; C211 lab number 5: More Recursion, And/Or, and Map
;; 10-1-2003

;; Reminder: this can be found at http://www.cs.indiana.edu/~sstamm/c211/

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Recursion Revisited
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Recall that there are two types of recursion: tail recursion
;; and simple recursion.  The main difference is how quickly 
;; the procedure returns.  With simple recursion, after each
;; recursive (or looping) call, the procedure must return to
;; do some more stuff.  With tail recursion, all the other 
;; stuff is done before the recursive call, so Scheme can 
;; throw away the environment and not look back.

;; Try tracing these procedures to see how different the trace
;; patterns are.

;; Factorial (simple recursion)
; n! = n * (n-1)! 
;    = n * (n-1) * (n-2)! 
;    = ... 
;    = n * (n-1) * (n-2) * ... * 1
(define !
  (lambda (n)
    (if (zero? n)
	1
	(* n (! (- n 1))))))

;; Factorial again (tail recursion)
(define !
  (lambda (n)
    (!-helper n 1))) ;start the accumulator at 1  	

(define !-helper
  (lambda (n acc)
    (if (zero? n)
	acc
	(!-helper (- 1 n) (* n acc)))))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Internal Defines
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; WARNING:  You will lose points in this class if you use
;; internal defines for something other than a lambda 
;; expression.  For example:
; (define x 2)
; (define y "hello")

;; Internal defines are useful for:
;; 1.  Hiding a helper inside a procedure (organizing it)
;; 2.  

;; nontail form --most intuitive to write this way
(define subst
  (lambda (old new ls)
    (if (null? ls)
	'()
        (if (equal? (car ls) old)
            (cons new (subst old new (cdr ls)))
            (cons (car ls) (subst old new (cdr ls)))))))

;; nontail with internal define
;; notice how the helper only takes one parameter.
(define subst
  (lambda (old new ls)

    (define subst-help
      (lambda (ls)
      	(if (null? ls)
            '()
            (if (equal? (car ls) old)
                (cons new (subst old new (cdr ls)))
                (cons (car ls) subst old new (cdr ls))))))

     (subst-help ls)))


;; tail recursive
(define subst
  (lambda (old new ls)
    (reverse (subst-helper old new ls '()))))

(define subst-helper
  (lambda (old new ls accum)
    (if (null? ls)
	accum
	(if (equal? (car ls) old)
	    (subst-helper old new (cdr ls) (cons new accum))
	    (subst-helper old new (cdr ls) (cons (car ls) accum))))))



;; tail with internal define: notice we can get rid of 
;; many of the helper's formals
(define subst
  (lambda (old new ls)
    
    (define subst-helper
      (lambda (ls accum)
      	(if (null? ls)
	    accum
            (if (equal? (car ls) old)
                (subst-helper old new (cdr ls) (cons new accum))
                (subst-helper old new (cdr ls) (cons (car ls) accum))))))
    
    (reverse (subst-helper ls '()))))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Away from recursion for a bit: AND/OR
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; and (you guessed it) returns the logical and of its
;; parameters.
(and #t #t)
; #t
(and #t #f)
; #f
(and #f #t)
; #f
(and #f #f)
; #f

;; guess what or does?  It returns the logical or!
(or #t #t)
; #t
(or #t #f)
; #t
(or #f #t)
; #t
(or #f #f)
; #f

;; so now you can string together complex test expressions
(if (and (< 2 4) (or (list? '(x y)) #t))
    'yup
    'nope)


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; MAP
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Map applies a provided procedure to every elemenet in the
;; provided list.  That procedure can be new or previously
;; defined (it can be anonymous) but must take only one 
;; argument.

(map (lambda (n) 
       (+ 1 n)) 
     '(1 2 3 4 5))

;(2 3 4 5 6)

(map (lambda (n) 
       (cons n (cons n '()))) 
     '(1 2 3 4 5))

;((1 1) (2 2) (3 3) (4 4) (5 5))

;; Get it?


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; EXERCISES
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Yay!  Now it's time for your weekly I-hate-Sid session!

;; EXERCISE 1:
;; -----------
;; Rewrite subst as provided in class so that it uses map.
;; Here is a starting point for you:

(define map-subst
  (lambda (old new ls)
    (map (lambda (item)
           ...)
	 ls)))

;; fill in "..." with the procedure definition that will
;; substitute all occurrences of the item old in ls
;; with new. HINT: you shouldn't need to use recursion.

;; Solution:
(define map-subst
  (lambda (old new ls)
    (map (lambda (item)
	   (if (equal? item old)
	       new
	       item))
	 ls)))

;; See how much shorter that is to read?  We could do it 
;; with an internal define too...
(define map-subst
  (lambda (old new ls)
    
    (define subst-help
      (lambda (item)
        (if (equal? item old)
	    new
	    item)))
    
    (map subst-help ls)))


;; EXERCISE 2:
;; -----------
;; Write the all-same? predicate that takes in a list and 
;; returns true if all the elements in the list are the
;; same.  An empty list has all elements the same (none) 
;; so it should also return true for the empty list.  Use
;; "or" once to simplify your code.

;; HINT: use "equal?"

;; Solution:
(define all-same?
  (lambda (ls)
    (if (or (null? ls) (null? (cdr ls))) 
        #t
        (if (equal? (car ls) (car (cdr ls)))
            (all-same? (cdr ls))
            #f))))


;; EXERCISE 3:
;; -----------
;; Write a procedure "swap" that behaves like subst, but
;; also replaces occurrances of new with old:
;; EX:
;;    >(swap 1 2 '(1 2 3 4 3 2 1))
;;    (2 1 3 4 3 1 2)
;; Say whether or not your solution is tail recursive, then
;; explain why you think so.

;; One Solution: (simple recursion)
(define swap
  (lambda (old new ls)
    (if (null? ls)
        '()
        (if (equal? (car ls) old)
	    (cons new (swap old new (cdr ls)))
	    (if (equal? (car ls) new)
		(cons old (swap old new (cdr ls)))
		(cons (car ls) (swap old new (cdr ls))))))))

;; Another: (tail recursion)
(define swap
  (lambda (old new ls)

    (define swap-help
      (lambda (ls accum)
        (if (null? ls)
	    accum
	    (if (equal? (car ls) old)
		(swap-help (cdr ls) (cons new accum))
		(if (equal? (car ls) new)
		    (swap-help (cdr ls) (cons old accum))
		    (swap-help (cdr ls) (cons (car ls) accum)))))))
     
    (reverse (swap-help ls))))